Theoretische informatica

De theoretische informatica is het vakgebied binnen de informatica dat de logische en wiskundige grondslagen van de informatica bestudeert. De nadruk ligt op wiskundige formaliseringen en bewijzen.

Onderwerpen die binnen de theoretische informatica worden bestudeerd, zijn onder andere:^[1]

• formele talen en automatentheorie,
• berekenbaarheids- en complexiteitstheorie,
• algoritmen en datastructuren,
• semantiek en formele methoden,
• gelijktijdigheidstheorie (concurrency theory) en
• informatietheorie en cryptografie.

Er werd al over computers en hun mogelijkheden nagedacht voordat zij in de praktijk werden gebruikt. Computers werden daarbij als abstracte machines weergegeven. Alan Turing bedacht in 1936 de turingmachine.^[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.

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