Algoritmi e Strutture Dati

Dato un problema, come troviamo un algoritmo efficiente per la sua risoluzione? Una volta trovato l'algoritmo, come possiamo paragonarlo con un altro algoritmo che risolve il medesimo problema? Come possiamo giudicare la bontà di un algoritmo? Domande di questo genere sono di interesse comune per i programmatori e per gli scienziati orientati alla teoria dei computer.
Considereremo diversi modelli di computer: la macchina ad accesso random, la macchina ad accesso random dei programmi memorizzati, e la macchina di Turing. Confronteremo questi modelli sulla base della loro abilità nel riflettere la complessità di un algoritmo, e derivare da questi diversi e più specializzati modelli di computazione: in maniera nominale, sequenze aritmetiche lineari, computazioni bitwise, computazioni con vettori di bit, e alberi di decisione.

1.1 Gli algoritmi e la loro complessità
1.2 Macchine ad accesso random (RAM – Random Access Machines)
1.3 Complessità computazionale dei programmi RAM
1.6 Un modello di computazione primitivo: la Macchina di Turing (TM - Turing Machine)
1.7 Relazione tra Macchina di Turing e modelli RAM

---

Torna alla categorie delle materie