Si vogliono studiare:

• Significato di un algoritmo (semantica operazionale)
• Valutazione della sua complessità

Entrambi dipendono da una descrizione formale del modello su cui l'algoritmo viene eseguito

Il modello di riferimento è quello della **Macchina RAM (**Random Access Machine)

Il modello RAM

Caratteristiche:

• Memoria ad accesso casuale formata da registri che possono contenere un intero qualsiasi
• Istruzioni di un linguaggio macchina elementare
  • Input e Output
  • Operazioni aritmetiche
  • Accesso e modifica registri
  • Salti condizionati e incondizionati

La richiesta 1 è irrealistica (intero qualsiasi) → Criterio di costo logaritmico

Semplicità e trasparenza → valutazione diretta delle prestazioni (tempo e spazio)

Struttura

• Programma: è fissato e composto da istruzioni indicizzate che ricordano il linguaggio assembly
• Location Counter (lc): contiene l'etichetta dell'istruzione da eseguire
• Nastro di lettura (sopra): è dotato di una testina di sola lettura che legge le infinite celle a partire dalla prima. Ogni cella può contenere un intero
• **Natro di scrittura (**sotto): ****è dotato di una testina di sola scrittura che scrive a partire dalla prima. Ogni cella può contenere un intero
• Registri: sono infiniti (?) e possono contenere interi di qualsiasi (?) dimensione. Ognuno è identificato da un indirizzo (intero) k
• Accumulatore: il registro R0 è l'unico sul quale si possono svolgere operazioni aritmetiche