Riassunto esame Informatica, prof. Console, libro consigliato Manuale di Informatica

STRUTTURAZIONE LOGICA DEI DATI: I FILE

Un file è una struttura lineare costituita da una sequenza di record, ciascuno formato da una sequenza di campi, ovvero da una sequenza di byte.

Un file è un meccanismo di strutturazione delle informazioni che permette di aggregare informazioni elementari in strutture più complesse. È l'entità fondamentale per l'organizzazione logica delle informazioni in un sistema di elaborazione. Essi possono essere:

• strutturati, sono effettivamente sequenze di record
• non strutturati, l'informazione è una sequenza di caratteri (byte) che costituiscono un testo; si può pensare che il record coincida con il singolo carattere e non sia possibile suddividerlo ulteriormente in campi.

Un file è costituito da una sequenza di record.

Un campo è costituito da un insieme di byte e serve per codificare una singola informazione, che può essere: numerica, alfabetica o un'immagine.

per separare i campi all'interno di ogni record. Questo tipo di formattazione permette di risparmiare spazio, ma può rendere più complessa la gestione dei dati. Ecco come potrebbe essere formattato il testo utilizzando tag html:

Un suono. Un record è costituito da un insieme di campi logicamente correlati tra loro e che costituiscono un'informazione complessa.

I record di un file possono essere:

• A lunghezza costante: tutti i record sono formati dallo stesso numero di byte, hanno lo stesso insieme di campi e ogni campo ha la stessa dimensione, indipendentemente dall'informazione che dovrà contenere. Deve essere precisato il numero di byte destinato a ciascun campo. Comporta uno spreco di spazio, in quanto ogni campo deve essere stimato a priori sufficientemente grande da poter occupare la più lunga informazione. L'informazione, in molti casi, occupa meno spazio di quello a disposizione.
• A lunghezza variabile: la lunghezza varia in funzione dell'informazione contenuta. In tal caso è richiesto un carattere speciale nella sequenza di byte che possa separare le varie informazioni. Occorre un carattere speciale per separare i record tra loro e un carattere speciale per separare i campi all'interno di ogni record. Questo tipo di formattazione permette di risparmiare spazio, ma può rendere più complessa la gestione dei dati.

per separare i campi all'interno di ciascun record. Esempio: OS di una banca

Esistono tre metodi di reperimento e accesso alle informazioni:

1. sequenziale: la ricerca dei record avviene a partire dall'inizio del file, leggendo tutti i record l'uno dopo l'altro, fino a quando non si arriva a quello desiderato. L'unico vantaggio è che è applicabile sia ai record a lunghezza costante che a lunghezza variabile. In un file con record a dimensione costante, ad ogni passo nella ricerca, invece di cercare i simboli di separazione tra record e campi, si avanza di un numero di byte prestabilito.
2. Diretto: il primo campo all'interno di un file prende il nome di indirizzo del record. Poiché un file è un insieme di byte, possiamo definire come indirizzo di un byte il numero che corrisponde alla posizione del byte nella sequenza (il primo byte ha indirizzo 0, il secondo 1, ...). L'indirizzo di un campo è l'indirizzo del primo

byte nel campo e l'indirizzo di un record è l'indirizzo del primo campo del record. Se l'indirizzo di un record è noto, è possibile posizionarsi direttamente in quel punto ed accedere alle informazioni in modo diretto, senza considerare quelle precedenti. L'accesso diretto ai record non è possibile con quelli a lunghezza variabile, poiché non è possibile calcolare l'indirizzo di un record non sapendo l'esatta posizione nella sequenza. Se l'indirizzo non è disponibile l'accesso diretto non è possibile.

Accesso con chiave: permette di mantenere le informazioni sugli indirizzi al di fuori del file. Occorre individuare il campo chiave che è presente in tutti i record e fornisce un riferimento univoco ai record stessi, come se fosse il nome del record. Il campo chiave sarà inserito in un nuovo file, il file delle chiavi, che è costituito da record a dimensione costante formati

Due campi: un campo per il valore della chiave, e l'altro per l'indirizzo del record nel file. Il file delle chiavi ha tanti record quanti sono quelli del file originario. Pertanto il metodo d'accesso prevede prima che si acceda al file delle chiavi per cercare la chiave, e poi si accederà in modo diretto al record nel file delle informazioni. Esso è la combinazione di due accessi diretti. L'unico svantaggio è la memorizzazione ulteriore di una tabella delle chiavi. Nei casi in cui un singolo campo non svolga il ruolo di chiave univoca, possono essere presenti due se non tre campi che potranno identificare in modo univoco un record.

Le strategie di ricerca sono le seguenti:

• Sequenziale - ricerca binaria, che richiede che le chiavi siano mantenute ordinate. Viene preso il record che si trova a metà della tabella (posizione N/2) e si legge il valore della chiave. Se k* = k, ossia l'elemento cercato è quello a metà

abbiamo terminato la ricerca. Se k<k* allora l'elemento cercato è nella prima metà della tabella, e si prosegue la ricerca ripartendo ma considerando solo la tabella che contiene N/2 -1 elementi. Se k>k* allora l'elemento cercato è nella seconda metà della tabella, e si prosegue ripartendo dall'inizio ma considerando la tabella che contiene solo gli elementi N/2 +1 fino alla fine. Con questa tecnica la ricerca di un elemento richiede un numero di passi logaritmici in N, dove N è il numero delle chiavi. Funzione di Hash: l'inserimento degli elementi nelle righe avviene utilizzando la funzione di hash che deve essere definita per tutti i possibili lavori del campo chiave e deve avere la proprietà che, quando applicata ad una chiave k, restituisce sempre un valore compreso tra 0 ≤ α ≤ Ν-1 e N-1: hash(k)= a con 0 ≤ α ≤ Ν-1. Per inserire nella tabella delle chiavi il record della chiave k bisogna valutare.

hash(k). Supponendo che il valore sia a, si inserisce il record corrispondente alla chiave k nella riga a-esima della tabella, se questa è libera, oppure nella prima riga libera successiva a quella a-esima. La funzione di hash deve avere le seguenti caratteristiche: i suoi valori devono esser sparsi uniformemente nell'intervallo tra 0 e N-1; la probabilità che la funzione assuma lo stesso valore per due chiavi deve essere bassa. La sua valutazione deve essere fatta velocemente. Una funzione usata nel caso di chiavi a valori numerici è il resto della divisione intera della chiave per il numero di righe nella tabella. Nel caso in cui la funzione di hash fornisca lo stesso valore per due chiavi diverse, la seconda chiave sarà inserita in quella libera subito a seguire.

CAP 3: ARCHITETTURA HARDWARE

Ogni elaboratore è racchiuso in un contenitore (CASE) che garantisce la corretta circolazione dell'aria. All'interno hanno un alimentatore e la Scheda

madre motherboard ospita i circuiti integrati CHIP. Sottili fili in rame collegano tra loro i chip BUS. Scheda madre: all'interno vi sono alcuni alloggiamenti detti slot che permettono di espandere la memoria inserendo nuove componenti di memoria. Chip, circuiti integrati, consiste nell'impiego di un certo numero di componenti che forniscono tutte le funzionalità di base dell'elaboratore. Unità centrale → processore → memoria principale, sequenza di celle, ciascuna formata da 8 bit, caratterizzate da un indirizzo che ne detta la posizione all'interno della sequenza stessa. Gli indirizzi sono espressi mediante numeri interi in notazione esadecimale. La RAM (random access memory) permette un accesso diretto alle celle ed è lo stesso indipendentemente dalla posizione della cella nella sequenza. Il processore effettua sulla RAM operazioni di lettura e scrittura di informazioni nelle celle. Per far ciò occorre specificare l'indirizzo.

Il numero di bit utilizzati per scrivere gli indirizzi o l'insieme delle celle indirizzabili prende il nome di spazio di indirizzamento. Utilizzando 32 bit è possibile indirizzare 2 alla 32 = 4GB di memoria. I processori moderni lavorano con celle a 64 bit, in tal modo è possibile indirizzare un numero di celle superiore a quelle fisicamente esistenti.

Una parola di memoria è un aggregato di 2 o 4 byte sul quale si può operare come su un blocco unico, pertanto il processore può scegliere di operare su un byte o su una parola di memoria.

Il tempo di accesso, ossia il tempo che occorre per leggere o scrivere una informazione in una cella nota il suo indirizzo, è il tempo che intercorre tra il momento in cui il processore specifica l'indirizzo della cella su cui si vuole leggere e dà il comando di lettura e il momento in cui l'operazione è terminata e il dato letto è disponibile.

oppure il dato scritto è in memoria. Il tempo di accesso è dell'ordine dei nanosecondi. Un byte memorizza un carattere. I server per la gestione di reti locali possono arrivare a 32 o 64 GB di memoria principale.

Tipi di Memorie RAM:

1. SRAM (Ram statiche): usate per le Cache, tempi di accesso inferiori ai 2 nanosecondi
2. DRAM (Ram dinamiche): tempi di accesso di 40-60 nanosecondi, sono utilizzate per la RAM.
3. VRAM (Ram video): sono usate dagli adattatori video per la gestione delle immagini.

La ram è volatile, ossia perde informazioni quando si spegne il pc. Deve contenere le istruzioni che il processore deve svolgere e i dati su cui le istruzioni devono operare.

PROCESSORE: CPU (Central Processing Unit)

Il processore è la componente dell'unità centrale che elabora le informazioni contenute nella memoria principale. Esegue ad ogni ciclo un'istruzione prelevata dalla memoria principale. L'elaborazione avviene in accordo a sequenze di

istruzioni dette programmi. Per ogni tipo di processore è definito un insieme di istruzioni in linguaggio macchina ognuna delle quali corrisponde ad un'operazione elementare che il processore è in grado di svolgere.

Il ruolo del processore è quello di eseguire i programmi scritti in linguaggio macchina.

Le componenti del processore sono collegate tra loro mediante i BUS, "fili" usati per trasferire i dati tra le componenti. Esistono tre tipi di bus di base:

• Bus dati: trasporta le informazioni da e verso il processore
• Bus indirizzi: trasporta gli indirizzi dei dati che devono essere letti o scritti
• Bus di controllo: trasporta i segnali di controllo usati dal processore e dalle altre componenti.

La dimensione di un bus, detta ampiezza, determina la quantità di informazione trasferita contemporaneamente.

UNITA DI CONTROLLO (UC): Coordina le diverse attività all'interno del processore, il quale svolge la sua attività in modo

ruzione letta3- Si aggiorna il valore dei registri e delle variabili4- Si controlla se è necessario un salto condizionato5- Si incrementa il contatore del programma per passare alla prossima istruzione6- Si ripete il ciclo dalla fase 1 Il testo formattato con i tag html sarà:

ciclico. La UC ad ogni ciclo controlla e coordina:

1. Si legge dalla memoria principale la prossima istruzione da eseguire
2. Si esegue l'istruzione letta
3. Si aggiorna il valore dei registri e delle variabili
4. Si controlla se è necessario un salto condizionato
5. Si incrementa il contatore del programma per passare alla prossima istruzione
6. Si ripete il ciclo dalla fase 1