Informatica si teoria computationala

4.Informatica si teoria computationala
 
Wikipedia, enciclopedia libera defineste Informatica asa:"Termenul informatică desemnează știința procesării sistematice a informației, în special a procesării cu ajutorul calculatoarelor. Termenul englez corespunzător este Computer Science (stiința calculatoarelor).Istoric, informatica s-a dezvoltat ca știință din matematică, în timp ce dezvoltarea primelor calulatoare își are originea în electrotehnică și telecomunicații. De aceea, calculatorul reprezintă doar dispozitivul pe care sunt implementate conceptelor teoretice. Informaticianul olandez Edsger Dijkstra afirma: "În informatică ai de-a face cu calculatorul, așa cum ai în astronomie cu telescopul".
 
Etimologie și istorie
 
Termenul informatică provine din alăturarea cuvintelor informație și matematică. Alte surse susțin că provine din combinația informație și automatică.
 Automat cu memorie.
Eingabeband=Banda de intrare
Lesekopf=Capul de citire
Keller=stivă
Pentru a putea accepta limbaje complicate, este nevoie de alte modele de automate, care în primul rând trebuie sa dispună de capacitate de memorare. Mulțimea tuturor cuvintelor care se compun dintr-o secvență care conține un număr egal de litere "a" și de litere "b" constituie un așa numit limbaj independente de context, pentru care este nevoie de un "automat cu memorie" (numit și "automat push-down"). Un astfel de automat are la dispoziție o stivă de memorii, cu posibilitatea de a sesiza de câte ori litera "a" a fost citită și încă neasociată - și deci de câte ori trebuie să mai apară litera "b".
Lingvistul Noam Chomsky a clasificat limbajele formale într-o ierarhie după cum urmează:
Limbaje regulate (engl.: Regular Language)
Limbaje independente de context (engl.: Context-free Language)
Limbaje dependente de context (engl.: Context-sensitive Language)
Limbaje recursiv enumerabile (engl.: Recursively enumerable Language)
 
Teoria computațională
 


În teoria computațională, informatica teoretică studiază posibilitățile de rezolvare a unei probleme cu o anumită mașină. Teza Curch-Turing susține că orice problemă intuitivă care poate avea o soluție, deci computabilă, poate fi rezolvată de o mașină MAA - mașină cu acces aleator sau și de mașina Turing, prin urmare neexistând o mașină care să fie limitată computațional. Aceasta teză nu este demonstrabilă în mod formal, fiind totuși universal acceptată. Se spune că un model de sistem computațional, respectiv un limbaj de programare, este "Turing complet compatibil", dacă cu acesta se poate simula mașina universală Turing. Toate computerele actuale sunt "Turing complet compatibile", aceasta însemnând că se poate găsi o soluție pentru orice problemă decidabilă. Termenul de decidabilitate poate fi descris ca o întrebare dacă o problemă anume este rezolvabilă algoritmic sau nu. Astfel, de exemplu, problema celui mai mic multiplu comun a două numere este o problemă decidabilă. O problemă nedecidabilă este de exemplu întrebarea dacă un computer, dându-i-se anumiți parametri de intrare, va ajunge vreodată la rezultat, fapt cunoscut sub numele de problema Halt. In teoria computațională se cercetează ce mașini se pot utiliza pentru efectuarea unei funcții date. Astfel funcția Ackermann de exemplu este rezolvată nu prin clasa programelor de tip loop, ci prin mai eficienta clasă a programelor de tip while".(ro.wikipedia.org)