Calcolabilità

Concetti di Informatica

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Cos'è la calcolabilità?

Problema calcolabile

  • Esistenza di algoritmo: Esiste una procedura chiara.
  • Tempo finito: Produce output in passi limitati.

Problema non calcolabile

  • Assenza di algoritmo: Non risolvibile su tutti gli input possibili.
  • Computazione infinita: Potrebbe non concludere mai.
1 Problemi non calcolabili possono diventare calcolabili quando troviamo un algoritmo e/o facciamo terminare in tempo finito un algoritmo noto.
Concetti di Informatica

Automi

Definizione di automi

  • Macchine immaginarie
  • Aiutano a capire come funziona il calcolo
  • Hanno stati
  • Hanno regole di transizione tra stati

Immagine di un semaforo come analogia che rappresenta gli automi

Concetti di Informatica

Automi finiti (FA)

Automi finiti (FA)

  • Macchine semplici
  • Numero di stati fisso
  • Nessuna memoria oltre lo stato corrente

Immagine di un semaforo e stati come analogia degli automi finiti

Concetti di Informatica

Automi a pila (PDA)

Automi a pila (PDA)

  • Più potenti
  • Hanno stati
  • Memoria a pila per decisioni più complesse

Immagine di un semaforo e stati come analogia degli automi a pila

Concetti di Informatica

Riepilogo

Automi finiti (FA)

  • Utili per compiti semplici

Automi a pila (PDA)

  • Più potenti per problemi complessi

Importanza

  • Se un problema è modellabile con automi, POSSIAMO implementare un algoritmo per risolverlo
Concetti di Informatica

Passiamo alla pratica !

Concetti di Informatica

Preparing Video For Download...