Informatică Alte teme
Informatica teoretica
Informatica teoretică studiază fundamentele matematice ale calculului și algoritmilor, fără focus pe aplicații practice. Aceasta include domenii precum teoria automatelor, complexitatea computațională și teoria grafurilor. De exemplu, problema P versus NP este o întrebare deschisă în acest domeniu.
Subdomenii cheie
- Teoria automatelor Analizează mașini abstracte care procesează inputuri, cum ar fi automate finite sau pushdown.
- Complexitatea algoritmilor Studiază eficiența algoritmilor prin notatii Big O, de exemplu O(n^2) pentru sortarea bubble sort.
- Teoria grafurilor Explorează proprietățile grafurilor, folosind algoritmi ca Dijkstra pentru drumuri minime.
Concepte importante
- Problema opririi Demonstrează că nu există un algoritm care să decidă dacă un program se va opri întotdeauna.
- Clase de complexitate Clasifică problemele în categorii ca P (rezolvabile în timp polinomial) sau NP (verificabile rapid).
- Teorema lui Cook Arată că problema satisfiabilității booleene (SAT) este NP-completă, fundament pentru teoria complexității.
Începe cu cărți de bază precum "Introduction to the Theory of Computation" de Sipser.