Vypočitatelnost

Koncepty v informatice

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Co je vypočitatelnost?

Vypočitatelný problém

  • Existence algoritmu: Existuje jasný postup.
  • Konečný čas: Výsledek v omezeném počtu kroků.

Nevypočitatelný problém

  • Neexistence algoritmu: Nelze vyřešit pro všechny možné vstupy.
  • Nekonečný výpočet: Nemusí nikdy dospět k závěru.
1 Nevypočitatelné problémy se mohou stát vypočitatelnými, jakmile najdeme algoritmus nebo zajistíme, že se známý algoritmus dokončí v konečném čase.
Koncepty v informatice

Automaty

Definice automatu

  • Imaginární stroje
  • Pomáhají porozumět výpočtům
  • Mají stavy
  • Mají pravidla pro přechody mezi stavy

Obrázek semaforu jako analogie automatu

Koncepty v informatice

Konečný automat (FA)

Konečný automat (FA)

  • Jednoduché stroje
  • Pevný počet stavů
  • Žádná paměť mimo aktuální stav

Obrázek semaforu a stavů jako analogie konečného automatu

Koncepty v informatice

Zásobníkový automat (PDA)

Zásobníkový automat (PDA)

  • Výkonnější
  • Má stavy
  • Má paměť zásobníku pro složitější rozhodování

Obrázek semaforu a stavů jako analogie zásobníkového automatu

Koncepty v informatice

Shrnutí

Konečný automat (FA)

  • Vhodný pro jednoduché úlohy

Zásobníkový automat (PDA)

  • Výkonnější pro složitější problémy

Důležitost

  • Pokud lze problém modelovat automatem, LZE implementovat algoritmus pro jeho řešení
Koncepty v informatice

Pojďme procvičovat!

Koncepty v informatice

Preparing Video For Download...