Beräkningsbarhet

Grundläggande datavetenskap

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Vad är beräkningsbarhet?

Beräkningsbart problem

  • Algoritm finns: En tydlig procedur existerar.
  • Ändlig tid: Producerar ett resultat på begränsat antal steg.

Icke-beräkningsbart problem

  • Ingen algoritm finns: Kan inte lösas för alla möjliga indata.
  • Oändlig beräkning: Kanske når aldrig ett svar.
1 Icke-beräkningsbara problem kan bli beräkningsbara när vi hittar en algoritm och/eller får en känd algoritm att avslutas på ändlig tid.
Grundläggande datavetenskap

Automater

Definition av automater

  • Tänkta maskiner
  • Hjälper oss förstå hur beräkning fungerar
  • Har tillstånd
  • Har regler för att växla mellan tillstånd

En bild av ett trafikljus som en analogi för automater

Grundläggande datavetenskap

Ändliga automater (FA)

Ändliga automater (FA)

  • Enkla maskiner
  • Fast antal tillstånd
  • Inget minne utöver aktuellt tillstånd

En bild av ett trafikljus och tillstånd som en analogi för ändliga automater

Grundläggande datavetenskap

Stackautomater (PDA)

Stackautomater (PDA)

  • Kraftfullare
  • Har tillstånd
  • Har stackbaserat minne för mer komplexa beslut

En bild av ett trafikljus och tillstånd som en analogi för stackautomater

Grundläggande datavetenskap

Sammanfattning

Ändliga automater (FA)

  • Användbara för enkla uppgifter

Stackautomater (PDA)

  • Kraftfullare för mer komplexa problem

Betydelse

  • Om ett problem kan modelleras med automater KAN vi implementera en algoritm för att lösa det
Grundläggande datavetenskap

Nu kör vi en övning!

Grundläggande datavetenskap

Preparing Video For Download...