Fondamenti di informatica

2.1 Componenti principali

1.​ Nastro infinito → diviso in celle, ogni cella contiene un simbolo (da un

alfabeto finito).

2.​ Testina di lettura-scrittura → può leggere e scrivere simboli sul nastro e

muoversi a destra o sinistra.

3.​ Stato interno → la macchina ha un numero finito di stati.

4.​ Tabella delle istruzioni → definisce come la macchina reagisce in base al

simbolo letto e allo stato corrente.

2.2 Funzionamento

●​ La macchina legge un simbolo sul nastro.

●​ Consulta la tabella delle istruzioni.

●​ Esegue azioni: scrive un simbolo, si muove a destra o sinistra, cambia

stato.

●​ Continua fino a raggiungere uno stato finale (halt) o procede

indefinitamente.

2.3 Importanza

●​ Definisce formalmente cosa significa “calcolabile”.

●​ Concetto di decidibilità: alcuni problemi possono essere risolti da una

macchina di Turing, altri no.

●​ Base teorica per tutti i moderni computer.

3. Concetti fondamentali della teoria della computazione

3.1 Problemi decisionali

●​ Problemi che hanno risposta sì/no.

●​ Esempio: “Un numero è primo?” → sì/no.

●​ Una macchina di Turing può decidere alcuni problemi, ma non tutti (es.

problema della fermata).

3.2 Problema della fermata (Halting Problem)

●​ Turing dimostrò che non esiste un algoritmo generale che determini se

una macchina di Turing si fermerà per ogni input.

●​ Implica che alcuni problemi non sono risolvibili da nessun computer.

3.3 Complessità computazionale

●​ Analizza quanto tempo o spazio serve per risolvere un problema.

●​ Classi principali:​

○​ P → problemi risolvibili in tempo polinomiale.

○​ NP → problemi la cui soluzione può essere verificata in tempo

polinomiale.

●​

●​ Concetto di efficienza: non basta risolvere un problema, serve farlo in

maniera pratica.

4. Linguaggi formali e automi

4.1 Alfabeto e stringhe

●​ Alfabeto (Σ): insieme finito di simboli (es. {0,1}).

●​ Stringa: sequenza finita di simboli dell’alfabeto.

●​ Linguaggio: insieme di stringhe valide su un alfabeto.

4.2 Automi finiti

●​ Modelli semplificati rispetto alla macchina di Turing.

●​ Usati per riconoscere linguaggi regolari.

●​ Hanno un numero finito di stati e transizioni basate sugli input.

4.3 Relazione con la macchina di Turing

●​ Tutti i linguaggi riconoscibili dagli automi finiti sono anche riconoscibili

da una macchina di Turing.

●​ La macchina di Turing può riconoscere linguaggi molto più complessi.

5. Introduzione ai linguaggi di programmazione

●​ La macchina di Turing è teorica; i computer moderni usano linguaggi di

programmazione per implementare algoritmi.

●​ Classi principali:​

○​ Linguaggi di basso livello: vicini all’hardware (assembly).

○​ Linguaggi di alto livello: più leggibili per gli esseri umani (Python,

Java, C++).

●​

●​ La logica è la stessa della macchina di Turing: input → elaborazione →

output.

6. Modello logico e rappresentazione delle informazioni

6.1 Bit e byte

●​ Bit: unità minima di informazione (0 o 1).

●​ Byte: gruppo di 8 bit, rappresenta caratteri o numeri.

6.2 Sistemi di numerazione

●​ Binario: base 2, usato dai computer.

●​ Decimale: base 10, usato dagli esseri umani.

●​ Conversione tra sistemi fondamentale per capire l’elaborazione digitale.

6.3 Codifica dei dati

●​ Testo: ASCII, Unicode.

●​ Numeri: binario o complementi a due.

●​ Immagini e suoni: sequenze di byte secondo formati specifici.

7. Teoria della computazione e limiti

●​ Alcuni problemi non sono calcolabili (es. problema della fermata).

●​ La teoria della computazione studia anche quanto è efficiente calcolare

qualcosa.

●​ Concetti chiave: decidibilità, complessità, riducibilità.

8. Applicazioni pratiche

●​ Fondamenti teorici → basi dei linguaggi di programmazione.

●​ Comprendere limiti e potenzialità → progettare algoritmi efficienti.