Calculabilitate

Concepte în Informatică

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Ce este calculabilitatea?

Problemă calculabilă

  • Existența algoritmului: Există o procedură clară.
  • Timp finit: Produce un rezultat în număr limitat de pași.

Problemă necalculabilă

  • Absența algoritmului: Nu poate fi rezolvată pentru toate intrările posibile.
  • Calcul infinit: Poate să nu ajungă niciodată la o concluzie.
1 Problemele necalculabile pot deveni calculabile odată ce găsim un algoritm și/sau facem un algoritm cunoscut să se termine într-un timp finit.
Concepte în Informatică

Automate

Definiția automatelor

  • Mașini imaginare
  • Ne ajută să înțelegem cum funcționează calculul
  • Au stări
  • Au reguli de tranziție între stări

O imagine cu un semafor ca analogie pentru automate

Concepte în Informatică

Automate finite (FA)

Automate finite (FA)

  • Mașini simple
  • Număr fix de stări
  • Fără memorie dincolo de starea curentă

O imagine cu un semafor și stări ca analogie pentru automatele finite

Concepte în Informatică

Automate cu stivă (PDA)

Automate cu stivă (PDA)

  • Mai puternice
  • Au stări
  • Folosesc memorie de tip stivă pentru decizii complexe

O imagine cu un semafor și stări ca analogie pentru automatele cu stivă

Concepte în Informatică

Rezumat

Automate finite (FA)

  • Utile pentru sarcini simple

Automate cu stivă (PDA)

  • Mai puternice pentru probleme complexe

Importanță

  • Dacă o problemă poate fi modelată prin automate, PUTEM implementa un algoritm pentru a o rezolva
Concepte în Informatică

Să exersăm!

Concepte în Informatică

Preparing Video For Download...