Theoretische informatica

De theoretische informatica is het vakgebied binnen de informatica, dat de logische en wiskundige grondslagen van de informatica bestudeert. De theoretische informatica is dus minder empirisch van aard dan de informatica in het algemeen. Onderwerpen die daarbij worden bestudeerd, zijn: berekenbaarheids- en complexiteitstheorie, algoritmen, formele semantiek en formele systemen en logica. De theoretische informatica biedt hiermee een fundament voor het maken van compilers van programmeertalen en de wiskundige formalisering van probleemstellingen, dus voor de informatica.

De Association for Computing Machinery ACM is een wetenschappelijk genootschap in de Verenigde Staten gericht op computers en de informatica. De ACM definieert de theoretische informatica door een groot aantal vakgebieden binnen de informatica te noemen, die zij daarbinnen vinden vallen.[1] Er werd al over computers en hun mogelijkheden nagedacht voordat zij in de praktijk werden gebruikt. Computers werden daarbij als abstracte machines, als eindigetoestandsautomaten weergegeven. AM Turing bedacht zijn turingmachine in 1936.[2] De informatietheorie[3] kon in de praktijk eerder worden toegepast dan dat er computers waren, omdat er eerder met elektronische middelen informatie kon worden verzonden. De informatietheorie sloot nauw bij wat later de theoretische informatica werd aan.

Bekende theoretisch informatici zijn Alan Turing, Edsger Dijkstra en Donald Knuth.