Algoritmi e Istruzioni di Assegnamento

Finitezza e Terminazione

• Non confondere finitezza (si riferisce alle istruzioni dell'algoritmo) e terminazione (si riferisce alla quantità di passi del processo).

Algoritmi

• Un algoritmo è una sequenza di istruzioni contenenti variabili.
• Le istruzioni possono essere di tre tipologie: elaborazione, input/output, controllo.
• Le variabili hanno specifiche caratteristiche, tra cui: nome, locazione di memoria, tipo, valore assegnato, variabilità, struttura, origine, visibilità del codice e visibilità nel flusso di esecuzione.

Istruzioni di Assegnamento/Elaborazione

• La notazione xy indica l'assegnamento di un valore alla variabile x.
• Un'operazione può essere eseguita sul lato destro della freccia (es. y+1).

Istruzioni Aritmetico-Logiche

• Le espressioni aritmetiche coinvolgono operatori come somma (+), sottrazione (-), moltiplicazione (*), divisione intera (/) e resto (%).
• Le espressioni relazionali coinvolgono operatori di confronto come uguaglianza (==), diversità (!=), minoranza (<) tra numeri.
• Le espressioni logiche e predicati logici utilizzano operatori come congiunzione (AND), disgiunzione (OR) e negazione (NOT).

Algebra di Boole

• Gli operatori logici possono essere unari (negazione) o binari (tutti gli altri).
• Gli operatori logici hanno specifiche proprietà: identità, elemento nullo, idempotenza, inverso, commutativa, associativa, distributiva, teorema di assorbimento, teorema di De Morgan.

Schemi a Blocchi

• Gli schemi a blocchi rappresentano graficamente gli algoritmi.
• I blocchi elementari sono: inizio, input/output, fine, elaborazione, selezione a 2 vie, sottoprogramma.
• I blocchi sono collegati da archi.

Memorie

• La memoria centrale è suddivisa in parole (blocchi di memoria fisica).
• Il tempo di accesso alla memoria dipende dalla tecnologia utilizzata.
• Il sovraccarico di lavoro per la CPU è mitigato da dispositivi come DMA (data memory access).

CPU

• La CPU è composta da unità di controllo e data path.
• L'unità di controllo comanda tutti i dispositivi del calcolatore.
• Il data path include ALU (unità aritmetico-logica) e registri.

Ciclo di Istruzione

• Il ciclo di istruzione prevede le fasi di fetch, decode ed execution.
• L'istruzione viene prelevata dalla memoria (fetch), decodificata (decode) ed eseguita (execution).
• Le istruzioni sono organizzate in campi: codice operativo, operandi sorgente e destinazione.
• I tipi di operandi sono: immediato, a registro, a memoria.

Indirizzamento in Memoria

• L'indirizzamento in memoria permette di localizzare dati in memoria.
• I tipi di indirizzamento sono: diretto, indiretto, relativo, relativo con auto incremento o auto decremento.

Linguaggio Assembly

• Il linguaggio assembly rappresenta simbolicamente il linguaggio macchina (binario).
• Il programma assemblatore traduce da linguaggio assembly in linguaggio macchina.
• Il linguaggio assembly è più leggibile rispetto al linguaggio macchina.
• Il linguaggio assembly utilizza nomi simbolici per codici di operazioni, indirizzi di registri, variabili ed etichette.

Memorie Flash

• Le memorie flash sono memorie elettroniche riscrivibili e non volatili che sono state sviluppate negli anni '80.
• Il loro costo è diminuito significativamente nel tempo, portando alla loro diffusione in dispositivi come tablet e lettori MP3.
• Le memorie flash possono essere utilizzate sia come memorie di massa relativamente piccole ma veloci, sia come memorie centrali relativamente lente ma adatte per esigenze di prestazioni limitate.
• rispetto alle memorie elettroniche tradizionali, le memorie flash offrono il vantaggio di combinare la riscrivibilità con la non volatilità, ma hanno tempi di accesso, soprattutto di scrittura, più lenti.
• Il tempo di lettura per le memorie flash varia tra circa 100 nanosecondi per gli accessi sequenziali e alcuni microsecondi per gli accessi casuali.

Gerarchia delle Memorie

• La memoria interna include registri, memoria cache e memoria centrale (RAM). Questa tipologia di memoria ha un'interazione intensa con la CPU. Caratteristiche: capacità inferiore, tempo di accesso minore, frequenza di accesso maggiore.
• I dischi magnetici come hard disk, CD e DVD sono considerati memoria esterna online. Caratteristiche: capacità medie, tempo di accesso medio, frequenza di accesso medio.
• I dischi ottici come CD-ROM, CD-RW, DVD e nastri sono considerati memoria offline. Caratteristiche: capacità elevate, tempo di accesso alto, frequenza di accesso minore (esterne).

Collocazione Fisica delle Memorie

• Registri, cache di livello I, cache di livello II e chip sono elementi chiave all'interno di un calcolatore per la gestione della memoria.

Caratteristiche dei Livelli di Gerarchia di Memoria

• Registri: capacità 1 KB, tempo di accesso 1 ns (ordine del ciclo di clock).
• Cache: capacità 1-10 MB, tempo di accesso 10 ns, velocità di trasferimento 100 GB/s.
• RAM: capacità 1-10 GB, tempo di accesso 100 ns, velocità di trasferimento 10 GB/s.
• SSD: capacità 100-1000 GB, tempo di accesso 100 microsecondi, velocità di trasferimento < 1 GB/s.
• Hard Disk: capacità 100-1000 GB, tempo di accesso 10 ms, velocità di trasferimento 0.1 GB/s.
• Nastri, CD: capacità GB per unità (senza limite di capienza), tempo di accesso 100 ms, velocità di trasferimento 0.01 GB/s.
• Obiettivo delle memorie centrali: velocità (memorie volatili).
• Obiettivo delle memorie di massa: capienza (memorie non volatili).

Principio di Località e Cache

• La memoria cache è meno capiente della RAM (mille volte più piccola).
• Per migliorare le prestazioni, la cache controlla se un dato è presente al suo interno prima di accedere alla RAM.
• Il principio di località spaziale afferma che un programma spesso accede ad elementi con indirizzi vicini a quello dell'elemento corrente.
• Il principio di località temporale afferma che un programma spesso accede allo stesso elemento in un breve intervallo di tempo.
• Quando la CPU richiede un'istruzione o un dato non presente nella cache, vengono prelevati dalla RAM e trasferiti nella cache insieme alle celle adiacenti.
• Se la cache è già piena, un nuovo blocco sostituisce un blocco vecchio, solitamente quello meno utilizzato di recente, seguendo una politica di sostituzione LRU (least recently used).
• La combinazione di cache e RAM offre il vantaggio della capacità elevata e dei bassi costi della RAM e dell'alta velocità della cache.

Memoria Cache (Informazioni Aggiuntive ed Esempi)

• La memoria cache è suddivisa in blocchi di parole consecutive, ciascuno con una propria etichetta associata.
• L'etichetta identifica un blocco di parole nella memoria centrale, mentre l'offset identifica la posizione specifica di una parola all'interno del blocco.
• L'accesso alla cache avviene in base agli indirizzi della memoria RAM.
• I confronti tra l'indirizzo della RAM e le etichette dei blocchi in cache vengono eseguiti in parallelo.
• Se un confronto è positivo, il dato è già presente nella cache e l'accesso è rapido.
• Se tutti i confronti sono negativi, il dato non è presente nella cache e viene prelevato dalla RAM.
• I caricamenti dalla RAM alla cache non limitano la parola cercata, ma includono anche le celle adiacenti.
• La velocità degli accessi alla cache è costante grazie all'esecuzione parallela dei confronti e all'accesso diretto alla parola desiderata all'interno del blocco.

Dispositivi per le Memorie di Massa

• Le memorie di massa devono essere non volatili e avere una grande capacità.
• Le tecnologie principali per le memorie di massa sono quella magnetica e quella ottica, con le memorie flash che stanno diventando sempre più diffuse.

Dischi e Nastri Magnetici

• I dispositivi di memorizzazione magnetici utilizzano uno strato sottile di materiale magnetico per memorizzare dati, codificati in base allo stato di magnetizzazione.
• Le testine di lettura/scrittura rilevano e modificano lo stato di magnetizzazione della superficie.
• I nastri magnetici erano i primi dispositivi di memoria di massa, ma sono stati sostituiti da altre tecnologie.
• L'accesso alle informazioni su un nastro è sequenziale, il che significa che per leggere un dato specifico è necessario scorrere attraverso i dati precedenti.
• I dischi magnetici memorizzano dati su dischi circolari, suddivisi in tracce concentriche, settori e blocchi di dati.
• Ogni settore contiene un blocco di dati, che rappresenta l'unità minima di trasferimento tra il disco e la RAM.
• La densità di memorizzazione è maggiore verso il centro del disco rispetto alla periferia.
• La formattazione organizza la superficie del disco in tracce e settori, identificando la posizione specifica di ogni settore.
• Il tempo di accesso a un dato sul disco magnetico è composto da tempo di ricerca (seek time), tempo di rotazione (latency time) e tempo di trasferimento effettivo.
• Gli hard disk moderni sono più veloci e hanno una capacità maggiore rispetto ai modelli precedenti.
• I floppy disk erano un formato comune negli anni scorsi ma sono stati sostituiti dalle memorie flash.

Dischi Ottici

• I dischi ottici, come CD e DVD, sono un'alternativa ai dischi magnetici.
• Hanno una capacità più elevata rispetto ai dischi magnetici, con i CD che offrono circa 600 MB e i DVD fino a 17 GB.
• I dischi ottici sono stati ampiamente utilizzati per memorizzare grandi quantità di dati, come enciclopedie, legislazioni e sistemi operativi.

Questo quiz esamina i concetti chiave degli algoritmi, come finitezza e terminazione, insieme alle diverse tipologie di istruzioni. Si approfondiscono in particolare le istruzioni di assegnamento ed elaborazione, nonché le operazioni aritmetico-logiche. Testa la tua comprensione di queste basi dell'informatica.