1900, evoluzioni e catastrofi tesina

Parati Danilo A.S. 2013-2014

VB

I.T.I.S. U. Midossi Civita Castellana

Indice

• Informatica - Strutture dati a Alberi ……………………………………….. Pag 4
• Sistemi - Storia dei Sistemi Operativi ………………………………………….. Pag 7
• Italiano - Primo Levi ……………………………………………………………… Pag 12
• Storia - Seconda Guerra Mondiale ……………………………………………… Pag 13
• Inglese - World War II ……………………………………………………………… Pag 15
• Elettronica - La storia dei transistor ………………………………………… Pag 17
• Calcolo delle probabilità - Ricerca Operativa …………………………… Pag 19

Gli alberi

Un albero è un insieme non vuoto di elementi, chiamati nodi, collegati tra di loro da archi organizzati in modo che ogni coppia di nodi sia unita da un solo arco. Un albero di N nodi contiene N-1 archi, e rimuovendo un arco dall’albero, si ottengono più alberi. Ogni nodo di un albero ha N-1 campi puntatori dove N è il numero di campi totali. L’albero è una struttura dati non lineare cioè un elemento può avere un solo predecessore ma più successori. L’uso della struttura è molto usata per gestire il File System nei sistemi operativi a Kernel.

Questo è l’esempio di un nodo di un albero.

In un albero si possono distinguere tre livelli fondamentali:

A è la radice, e padre di B

B e C sono fratelli tra di loro e figli di A

D, E, F sono figli di C, e discendenti di A e di C.

Nell’albero in figura si può fare una distinzione gerarchica:

A è la radice che non discende da nessuno e che ha priorità massima sugli altri nodi;

C è un nodo intermedio, cioè ha un predecessore e almeno un successore;

B, D, E e F sono foglie, cioè hanno un predecessore e nessun successore.

Si noti che il nodo B, fratello di C, non ha successori, cioè non è detto che se un nodo ha un fratello che ha successori deve averne anche il nodo stesso. 4

Classificare un albero significa definirne i seguenti parametri:

Grado di un nodo: è il numero di sottoalberi; in questo caso il grado di A è 2, di B è 0 e di C è 3

Grado di un albero: è il grado maggiore dei suoi nodi; in questo caso 3

Livello di un nodo: è il numero di nodi attraversati da un cammino che parte dalla radice e arriva al nodo stesso; in questo caso il livello di A è 1, di C è 2

Altezza di un albero: è il numero di archi che separano la radice dalla foglia più lontana; in questo caso è 2.

Albero binario

Un albero è binario se ogni nodo ha al massimo due figli.

La visita di un albero binario

Visitare un albero consiste nell’analizzare tutti i suoi nodi una sola volta. La visita di un albero si dice ricorsiva in quanto, si analizza il nodo controllando se non esistono figli, se ne esistono si analizzano i figli per poi tornare ad analizzare il nodo. Esistono tre modalità di visita di un albero, che è caratterizzata dalla posizione del nodo nella visita.

Visita in preordine (N,FS,FD)

Visita in ordine (FS,N,FD)

Visita in postordine (FS,FD,N)

Visita in preordine dell’albero in figura = A FS FD = A B FS * C FS FD = A B D * * * C E * FD F * FD = A B D * *

* C E * G * * F * H * *

Visita in ordine dell’albero in figura = FS A FD = FS B * A FS C FD = * D * B * A * E FD C * F FD = * D * B * A *

E * G * C * F * H *

Visita in postordine dell’albero in figura = FS FD A = FS * B FS FD C A = * * D * B * FD E * FD F C A =* * D * B

* * * G E * * * H F C A 5

Albero binario di ricerca (ABR)

Un albero binario si dice di ricerca quando:

Per ogni nodo dell'albero il campo informativo è maggiore dei campi informativi del sottoalbero sinistro e minore delle informazioni che si trovano nel sottoalbero destro

La visita in ordine di un ABR produce le chiavi in modo ordinato

Albero Binario Di Ricerca

All'interno dei nodi dell'albero è indicato solo il valore del campo informativo ipotizzando che esso sia di tipo numerico. 6

La storia dei sistemi operativi

Dagli anni 40 a oggi

Anni 40-50: elaborazione seriale

I calcolatori venivano realizzati con le valvole elettroniche quindi avevano dimensioni e prezzi grandissimi, tanto da scoraggiare l’uso se non per usi di ricerca come nelle università o per usi bellici (come la Seconda Guerra Mondiale). Erano lentissimi rispetto alla velocità d’esecuzione dei giorni d’oggi, tipicamente 5.000 istruzioni al secondo. Erano così costosi e complessi che erano fatti su ordinazioni e ognuno era diverso e finalizzato solo allo scopo per cui era stato progettato, realizzato e venduto. Ma la differenza più evidente tra i calcolatori di questi anni e quelli odierni è l’assenza del concetto di Sistema Operativo. Quando questi calcolatori venivano venduti, venivano associati dei tecnici in grado di fare manutenzione e capaci ad usarli.

Metà anni 50: elaborazione a batch

In questi anni vennero applicati i Transistor all’informatica, che rivoluzionarono notevolmente il mondo dei calcolatori, riducendone di molto le dimensioni e il prezzo, aumentando così la velocità d’esecuzione. In questi anni nascono i primi linguaggi di programmazione ad alto livello come l’Assembler, iniziarono così anche le produzioni standard aumentando le vendite. La fase di esecuzione comprendeva: la predisposizione del compilatore adeguato, l’inserimento del codice sorgente, compilazioni con eventuale uso di librerie o moduli esterni ed esecuzione del codice prodotto dall’elaboratore. Il problema di fondo è che ad ogni operazione richiedeva un operatore che preparava ogni fase. Così per ridurre i tempi e il personale, vennero raggruppati tutti i programmi con caratteristiche simili (stesso compilatore, stesse librerie, stessi moduli) in lotti detti Batch, che venivano eseguiti sequenzialmente per risparmiare i tempi di impostazione del calcolatore, fu sviluppato un modulo software specifico, chiamato Monitor, capace di interpretare un numero ristretto di istruzioni utilizzate dai calcolatori per automatizzare i meccanismi di esecuzione di un programma, come: il caricamento dei compilatori e dei moduli, l’avvio delle fasi 7

di esecuzione, la memorizzazione del codice prodotto, l’esecuzione del programma stesso, la gestione dell’input e dell’output e la ricerca di eventuali errori. I dispositivi d’input tipici erano i lettori dei schede perforate, quindi l’ordine delle istruzioni era l’ordine in cui le schede erano fisicamente inserite nel lettore, mentre dispositivi d’uscita tipici erano le stampanti. Si può quindi affermare che il monitor è il precursore dei moderno Sistemi Operativi. Ma questa tecnica aveva uno svantaggio, visto l’elevato costo di una CPU non ci si poteva permetter di non sfruttarla a pieno, infatti durante l’input e l’output rimaneva inattiva aumentando il tempo d’esecuzione.

Fine anni 50 (Batch multitasking)

Il problema del poco uso della CPU è stato risolto con la tecnica dello spolling. Lo spolling prevedeva che la CPU prendesse dati in input dal disco e l’output fosse fatto su disco così da velocizzare le operazioni, era poi compito di un secondo calcolatore mettere a disposizione sul disco i dati in input e a stampare i dati in output. Ma per essere funzionale il secondo calcolatore deve fornire i dati prima di quando la CPU ne abbia bisogno, usando anche più periferiche contemporaneamente. Ma questa tecnica non basta a velocizzare abbastanza i processi, così vengono aggiunte nuove funzioni al monitor, viene programmato in modo da riuscire a portare avanti più programmi contemporaneamente. Per far ciò la CPU eseguiva il codice di un solo programma quando il programma aveva bisogno di una periferica di input o di output il monitor attivava il secondo calcolatore lasciando così che la CPU continuasse l’esecuzione di altri programmi. Ma questa tecnica funziona solo nel caso in cui più programmi non richiedano contemporaneamente l’uso dello stesso dispositivo di input o output. Questa architettura è detta batch multitasking 8

Il termine calcolatore viene sostituito col termine mainframe. Nel monitor vengono aggiunte funzioni ancora oggi importanti come la gestione condivisa della memoria che permette l’allocazione in memoria di più programmi contemporaneamente. All’inizio era possibile adottando partizioni di memoria, ma successivamente furono adottate partizioni di memorie virtuali, creando spazi logici, uno per ogni programma in esecuzione, tutti riferiti a spazi di memoria disponibili. Un’altra funzione importante implementata nel monitor è il meccanismo di protezione che garantisce che i vari programmi non interferiscano col Sistema Operativo, o tra di loro; era implementato a livello hardware progettando due utenze diverse con privilegi diversi: modalità utente in cui il programma ha accesso solo al suo spazio su dico e modalità protetta (Kernel) in cui il monitor, ha accesso a tutte le aree di memoria e può cambiare modalità operativa.

Primi anni 60 (elaborazione a divisione del tempo)

Benché il multitasking desse grandi vantaggi in ambito di velocità d’esecuzione, aveva ancora degli svantaggi come la mancanza di interattività tra utente e programma, e soprattutto i programmi che usavano più frequentemente i dispositivi di input e output erano svantaggiati. Per questo problema il monitor (diventato a tutti gli effetti un Sistema Operativo) lascia al programma l’utilizzo della CPU per una frazione di tempo, quando questa frazione di tempo si esaurisce o il programma ha bisogno di un dispositivo di input o di output il controllo della CPU torna al Sistema Operativo, se il tempo non è sufficiente per la completa esecuzione del programma il Sistema Operativo riprende il controllo della CPU e l’esecuzione del programma viene momentaneamente bloccata.