Storia dell’informatica - Appunti lezioni

STRUTTURE DI DATI

Per poter operare sui dati codificati bisogna interpretarli. Quindi bisogna strutturare i dati per potervi operare con opportuni algoritmi.

Strutture Lineari

Per esempio vogliamo aggiungere una persona in mezzo ad una fila. Per farlo ci sono dei problemi, per esempio bisogna riuscire a ricavare spazio escogitando un procedimento per fare spazio. Si può iniziare (non dal centro) dall'estrema destra o dall'estrema sinistra spostando gli omini per ricavare lo spazio.

La Struttura di Array

Analogamente se volessimo aggiungere una pagina nel mezzo di un libro, dovremmo rinumerare tutte le pagine.

Astrattamente, la struttura di un libro o della fila di persone è rappresentata da quello che si chiama array. È una struttura lineare dove gli elementi hanno una posizione. È una sequenza di celle di lunghezza prefissata, dove ogni cella può contenere un elemento di ognuna delle celle, con il relativo contenuto, è direttamente accessibile.

più astratto di un indirizzo. Quando non c’è un elemento successivo, si segna un valore che serve a terminare la lista. Non c’è un accesso diretto alle celle successive se non passando dai precedenti. È possibile aggiungere elementi o eliminarli all’interno delle liste.

Una Lista È una struttura lineare di dati molto più flessibile rispetto ad aggiunte o eliminazioni di elementi. Anche in questo caso gli elementi sono omogenei. Ogni elemento di una lista associa l'elemento successivo. Gli elementi di una lista sono accessibili mediante RIFERIMENTI. C’è un riferimento al primo elemento, la testa della lista. Il primo elemento contiene un riferimento al secondo e così via. ➞ Quindi ogni elemento di una lista è descritto da una coppia valore e riferimento al prossimo elemento.

Quando non esiste un prossimo elemento, il riferimento ha valore quindi l’ultimo elemento è descritto da ➞

(valore, Viene chiamato Null cioè nullo. Quale sia la natura di un riferimento dipende dalla sua rappresentazione. Per il momento immaginiamo che un elemento a = (v, b) di una lista abbia riferimento a, e contenga il valore v e un riferimento b al prossimo elemento.

Rebecca Francesca La Marmora 20È comodo visualizzare i riferimenti agli elementi di una lista come frecce. Per esempio, la lista che ha come testa l’elemento a = (“bim”,b) e prosegue con b =(“bum”,c), c = (“bam”,◼) diventa:

In questo caso l’accesso agli elementi di una lista non è diretto, ma piuttosto sequenziale: per accedere al terzo elemento della lista questa volta devo passare attraverso la testa, a, per accedere al riferimento al secondo elemento, b; passare attraverso b per accedere al riferimento al terzo elemento, c.

Tuttavia, in questo caso non ci sono i problemi che abbiamo visto prima ad estendere una lista con un nuovo elemento.

Abbiamo la

Possibilità di introdurre un nuovo elemento con valore "paf" al terzo posto della lista. L'elemento sarà x = (paf, c) e basta modificare i riferimenti. Si può fare anche per eliminare un elemento all'interno di una lista. L'attività di programmazione ➞ Esempio Vogliamo programmare i movimenti di un robot in una stanza in modo che vada a prendere un oggetto che ci interessa. Un sistema coordinante definisce le posizioni entro la stanza. Bisogna dare dei comandi, quelli che il robot può eseguire sono: ↑ un passo avanti ↓ un passo indietro → un passo a destra ← un passo sinistra La combinazione di questi passi crea un programma. ↑ ↑ → → ↓ ↓ ↓ sono delle istruzioni elementari che concatenate una dopo l'altra si ha una sequenza d'azione. La sequenza d'azione può essere alterata. LA PROGRAMMAZIONE DI UN COMPUTER Un modello del computer Si tratta della architettura

Suggerita da John von Neumann, contenuta nel documento First Draft of a Report on the EDVAC, 30 Giugno 1945.

Ci sono due blocchi:

A destra abbiamo la memoria che tiene i dati durante l'elaborazione. E' una memoria rapida e capiente e va persa nel momento in cui non c'è più alimentazione elettrica. Si chiama infatti memoria volatile. E' una memoria RAM (random access memory) l'accesso non è casuale ma è un accesso diretto.

La parte sinistra si chiama CPU unità centrale di programmazione. All'interno della CPU ci sono il registro dati e il registro indirizzi. Le due parti del pc sono collegate dal bus di sistema sono collegate perché la CPU elabora i dati che contiene la memoria.

La memoria passa dati a CPU, poi i dati dopo essere stati elaborati tornano nella memoria. Il bus di sistema trasporta questi dati da un blocco all'altro. Ci sono dati, ma anche indirizzi. Nella memoria troviamo

I dati, ma attraverso la posizione dei dati abbiamo degli indirizzi.

Modello della Memoria del Computer

Il modello della memoria del Computer è un modello in cui abbiamo delle celle di memoria con ciascuna il loro indirizzo.

Un array di celle contigue della memoria.

Utilizzando l'indirizzo delle celle che compongono l'array, accediamo direttamente alle celle ed ai dati contenuti nelle celle. Un array è quindi una struttura che meglio rappresenta una porzione della memoria ad accesso diretto del computer, sia che sia lineare, sia che noi prendiamo una porzione bidimensionale della memoria (un rettangolo di celle).

La lunghezza degli indirizzi è calcolata in base al numero di celle disponibili nella memoria.

Nel caso di bit gli indirizzi sono composti da 8 celle.

Collegamento tra celle ??

Esistono altre strutture lineari possibili. Una lista è una struttura di base lineare, sopra la quale possiamo sovrapporre altre strutture lineari che si comportano in

maniere caratteristiche relativamente all'immissionedi dati e al loro recupero.

• La Coda è una struttura lineare dove la gestione dell'ingresso e dell'uscita degli elementi è data dal fatto che il primo elemento ad entrare, è il primo ad uscire (first in, first out - FIFO).
• La Pila è una sequenza di elementi dove la gestione dell'ingresso e dell'uscita degli elementi è data dal fatto che l'ultimo elemento ad entrare, è il primo elemento ad uscire (last in, first out - LIFO). Si ha un accesso immediato all'ultimo elemento che è stato impilato (pila di libri...). La pila ha un'importanza storica ed è collegata ad altre strutture (albero, espressioni aritmetiche...). La pila è chiusa da una parte, ovvero il fondo.

Esercitazione

Supponiamo di avere una pila vuota in cui posso inserire elementi. Ho quindi una struttura sequenziale, per cui inserisco un

elemento alla volta. Oltre ad inserire posso però anche togliere. Allocare un elemento nella pila si dice "push", mentre togliere si dice "pop" (ovviamente posso togliere solo l'ultimo dato immesso).

Supponiamo di eseguire sulla pila le seguenti operazioni:

push 2 - push 6 - pop

push 7 - push 9 - pop

Che cosa resta nella pila dopo l'esecuzione di queste operazioni? Risposta: sequenza vuota

push 2 - push a - push l - push b - push a

pop ! esce a - pop ! esce b - pop ! esce l - pop ! esce a

Risposta: sequenza vuota

Rebecca Francesca La Marmora 22

DOUGLAS CARL ENGELBART (30 gennaio 1925 – 2 luglio 2013)

Gli studi di Engelbart:

➞1948 B.S. in Electrical Engineering

➞1955 PhD e alcuni brevetti su "bi-stable gaseous plasma digital devices"

Eventi fondamentali

➞Settembre 1945 Legge per la prima volta "As we may think" di Bush

➞1957 Entra allo Stanford Research Institute (SRI)