Appunti di Introduzione alla Programmazione (corso Informatica UniGe) PDF

Preview

Summary

Dario Olianas A.A. 2012/2013 Appunti di Introduzione alla Programmazione (IP) 1. Introduzione ai concetti base (prima lezione) 2. Macchina di von Neumann 2.1 Programmazione della macchina di von Neumann 2.2 Bootstrap 2.3 Estensione procedurale 3. Codifica delle informazioni 3.1 Rappresentazione di i...

Description

Dario Olianas

A.A. 2012/2013

Appunti di Introduzione alla Programmazione (IP)

1. Introduzione ai concetti base (prima lezione) 2. Macchina di von Neumann 2.1 Programmazione della macchina di von Neumann 2.2 Bootstrap 2.3 Estensione procedurale 3. Codifica delle informazioni 3.1 Rappresentazione di interi con segno 3.1.1 Rappresentazione in modulo e segno 3.1.2 Rappresentazione in complemento a 1 3.1.3 Rappresentazione in complemento a 2 3.2 Rappresentazione di numeri razionali 3.2.1 Rappresentazione in virgola fissa (fixed point) 3.2.2 Rappresentazione in virgola mobile (floating point) 4. Macchina convenzionale a stack 5. Principi di programmazione 5.1 Istruzioni di I/O 5.2 Variabili e tipi 5.2.1 Tipi base 5.2.2 Dichiarazione di variabili 5.2.3 Assegnazione 6. Controlli di flusso 6.1 L’istruzione condizionale if 6.1.1 Istruzioni condizionali concatenate (if-else if) 6.2 L’istruzione switch 6.3 Cicli 6.3.1 Ciclo for 7. Struttura dei programmi C/C++ 7.1 Sintassi di una funzione 7.2 Main 7.3 Programma che fa la somma di due numeri e stampa il risultato in output 7.4 Utilizzo di librerie 8. Esercizi di programmazione sui cicli 8.1 Operatore condizionale 9. Funzioni 9.1 Definizione e chiamata di funzioni 9.2 Esempio di funzione per l’elevamento a potenza 9.3 Istruzioni di uscita 9.4 Passaggio di parametri 9.4.1 Modi di passaggio di parametri in C++ 10. Memoria 10.1 Casting 10.2 Gestione della memoria nelle chiamate a funzione

10.3 Operatori di dereferenziazione 11. Array 11.1 Array come parametri di funzioni 11.2 Operazioni sugli array 11.2.1 Inserimento in coda 11.2.2 Eliminazione di un elemento in coda 11.2.3 Inserimento in ordine 12. Algoritmi di ordinamento 12.1 Insertion sort 12.2 Selection sort 12.3 Bubble sort 12.4 Ricerca per bisezione in un’array ordinato 13. Complessità computazionale 13.1 Analisi di complessità dell’algoritmo di insertion sort 13.2 Proprietà degli ordini di complessità 13.3 Tabella degli ordini di complessità in ordine crescente 13.4 Stima della complessità dell’algoritmo di insertion sort 13.4.1 Regola dell’operazione dominante 13.5 Stima della complessità dell’algoritmo di selection sort 13.6 Stima della complessità dell’algoritmo di ricerca binaria 13.7 Stime di complessità di altri algoritmi 14. Stringhe (del C) 15. Array bidimensionali (tabelle) 16. Il tipo string 16.1 Operare sulle stringhe e funzioni del tipo string 17. Flussi (stream) e operazioni sui file 17.1 Operare sui file 17.2 Esercizio sui file 17.3 Text processing e gestione bufferizzata 17.4 Stringstream 18. Visibilità degli identificatori (scope) e namespace 18.1 Regole di scope 18.1.1 Principali scope 18.2 Namespace 19. Progettazione di tipi di dato 19.1 Stack 19.2 Queue 20. Gestione dinamica della memoria 20.1 Puntatori 20.2 Gestione dello heap 20.2.1 Memory leak 20.3 Array dinamici

21. Vector 21.1 Primitive del tipo vector 21.2 Queue usando vector e template 22. Liste 22.1 Definizione del tipo cell 22.2 Inserimento in testa ad una lista 22.3 Inserimento in coda ad una lista 22.4 Inserimento in mezzo ad una lista 22.5 Copia di liste 22.6 Stack e queue implementati con liste 22.6.1 Stack implementato con lista 22.6.2 Queue implementata con lista 22.7 Tipo di dato insieme 22.7.1 Inserimento ordinato 22.7.2 Cancellazione 22.7.3 Unione 22.8 Liste circolari e liste doppie 22.8.1 Inserimento e cancellazione da liste doppie 22.8.2 Liste circolari (semplici e doppie) 23. Ricorsione 23.1 Principio di induzione 23.2 Definizione induttiva 23.2.1 Definizione induttiva di lista 23.3 Esempi di funzioni ricorsive 23.3.1 Funzione ricorsiva per il calcolo del fattoriale 23.3.2 Funzione ricorsiva per il calcolo dei coefficienti binomiali 23.4 Liste implementate ricorsivamente 23.4.1 Inserimento in liste implementate ricorsivamente 23.4.2 Rovesciamento di liste 23.5 Approccio divide et impera 23.5.1 Mergesort (approccio divide et impera applicato al problema del sort) 24. Complessità degli algoritmi ricorsivi 24.1 Analisi tramite albero della ricorsione 24.2 Complessità dell’algoritmo ricorsivo di ricerca binaria 24.3 Analisi degli algoritmi mergesort e coefficienti binomiali 25. Ricorsione mutua e ricorsione ciclica 25.1 Generazione del codice Gray 26. Parsing, linguaggi formali e grammatiche 26.1 Grammatica generativa 26.2 Parsing di espressioni aritmetiche (semplificate)

27. Incapsulamento delle informazioni nei tipi di dato (information hiding) 27.1 Struct e class 27.2 Campi e metodi 27.3 Esempio: tipo di dato orologio 27.4 Costruttori e distruttori

Laboratori: A B

Laboratorio 1 Laboratorio 4 B.1 Direttive per il preprocessore B.2 Operatore virgola B.3 Operatore condizionale B.4 Generazione di numeri pseudocasuali

C Laboratorio 5 (codice modulare)

1. Introduzione ai concetti base (prima lezione) Approcci alla progettazione: • •

top-down bottom-up

L'approccio top-down parte da un livello di astrazione alto e scompone il problema in parti più semplici da risolvere, che poi vanno collegate. L'approccio bottom-up ragiona al contrario: partendo dalle componenti base si arriva a risolvere il problema principale. L'approccio top-down è quello di un ingegnere che progetta un palazzo, l'approccio bottom-up è quello del muratore che lo costruisce. La chiave di entrambi gli approcci è di avere diversi livelli di astrazione. Programmazione strutturata: funziona per livelli di astrazione diversi e per ogni livello assume di disporre degli strumenti per risolvere i sottoproblemi dei livelli sottostanti. Ad esempio, per scrivere non serve sapere come si fabbrica una penna o un foglio di carta, sono cose che si hanno e sono date per scontate. Concetti di input/output: ogni pezzo di software: • •

riceve dati in input produce dati in output

L'input/output è alla base del concetto di astrazione: se ho una scatola nera che svolge un determinato compito non importa che io ne sappia il funzionamento, se le fornisco un certo input otterrò l'output corrispondente. Se invece non ho la scatola nera che mi serve devo scendere al livello di astrazione inferiore e progettare un sistema che svolga il compito richiesto. Concetti chiave: • • • •

macchina virtuale linguaggio/alfabeto/comandi interpretazione estensione procedurale

Si usa il termine macchina virtuale perché non è riferito per forza ad una macchina fisica: una macchina vituale è qualunque cosa, software o hardware, che riceva un input e produca un output. È la scatola nera di prima. Il linguaggio è lo strumento con il quale comandiamo la macchina virtuale. Una macchian virtuale può anche servirsi di altre macchine virtuali per eseguire compiti più complessi: in questo caso si parla di estensione procedurale. Vedendo una pizzeria come una macchina virtuale, la macchina virtuale cameriere prende l'ordinazione, ma deve utilizzare la macchina virtuale pizzaiolo per avere una pizza da portare. A sua volta il pizzaiolo deve servirsi di chi ha prodotto gli ingredienti.

I calcolatori sono strutturati su diversi livelli di astrazione:

• •

• • •

Linguaggi di alto livello: linguaggi formali e non ambigui, tuttavia "facilmente" comprensibili dall'uomo. Assembler e librerie: un linguaggio fatto di poche e semplici istruzioni, inadatto per svolgere compiti complessi (anche un programma molto semplice in linguaggio di alto livello richiede migliaia di istruzioni assembler Kernel (nucleo del sistema operativo): il programma che gestisce tutti gli altri programmi e si interfaccia direttamente con l'hardware Macchina convenzionale Microarchitettura { ibrido hardware-firmware

• •

Logica circuitale Elettronica

{

{ questi ultimi due livelli riguardano solo l'hardware

•

Fisica dello stato solido {

2. Macchina di von Neumann Composta da RAM e Control Unit. La RAM serve a conservare informazioni per due scopi: o dati che il calcolatore sta elaborando o istruzioni da eseguire. È organizzata in forma di vettore: un elenco di valori dello stesso tipo in sequenza numerata. Nel nostro modello di macchina di von Neumann la RAM è composta da 1000 elementi numerati da 0 a 999 e ciascuna cella di memoria contiene un numero intero in base 10 di massimo 4 cifre. Si chiama Random Access Memory perché si può accedere direttamente a qualunque cella di memoria. Sulla RAM possono essere svolte solo due operazioni: lettura e scrittura.

Control Unit La control unit è composta da: • • •

ALU (Arithmetic Logic Unit): l'unità che si occupa di calcoli e operazioni logiche. Nel caso della macchina di von Neumann sa fare solo somme e sottrazioni Decoder: si occupa di decodificare le istruzioni Registri PC, IR, ACC

I registri sono come celle di memoria: possono contenere numeri di massimo 4 cifre.

Istruzioni della macchina di von Neumann 0 (con parametro N): somma due numeri 1 (con parametro N): sottrae due numeri 2 (senza parametro): leggi un numero da input e mettilo in ACC 3 (senza parametro): scrivi un numero in output (il numero presente in quel momento nell'accumulatore) 4 (con parametro N): scrivi un numero nella cella di memoria N 5 (con parametro N): leggi un numero dalla cella di memoria N 6 (con parametro N): salto incondizionato 7 (con parametro N): salto condizionato 8 (senza parametro): arresto L'accumulatore contiene i risultati delle operazioni svolte dalla ALU o i numeri letti dall'input. Come le celle di RAM può contenere un solo valore alla volta. Ciclo di funzionamento della MVN La macchina di von Neumann ha quattro stati, che vengono ripetuti in ciclo finché non viene eseguita l'istruzione 8 (arresto): 1. reset: scrive 0 nel program counter 2. fetch: prende un'istruzione dalla cella di RAM indicata dal PC e la scrive nell'IR, incrementa di 1 il valore del PC IR X u {errore} La funzione di decodifica ritorna da una stringa di elementi di A* a un elemento dell'insieme di valori da rappresentare. L'errore è quello a cui portano le stringhe che non codificano niente. Codifica e decodifica servono per poter rappresentare qualunque dominio finito in simboli comprensibili alla macchina.

Codifica posizionale a lunghezza fissa I calcolatori usano codifiche a lunghezza fissa: 1 rappresentato in una codifica ad 8 bit sarà 00000001.

Con numeri binari di n cifre rappresentiamo fino a 2^n elementi diversi. Se X ha M elementi per codificarli in binario dovrò usare codici di almeno log2M cifre.

Somma di numeri interi positivi Se usiamo una codifica ad 8 bit e sommiamo due numeri che danno come risultato un numero di 9 bit abbiamo un risultato non rappresentabile con la nostra codifica, e siamo in una situazione chiamata di overflow. Se tagliamo il bit in eccesso ottenuamo un risultato sbagliato, quindi in genere i calcolatori hanno un sistema per segnalare quando si è andati in overflow.

Rappresentazione dei caratteri (non c'è nelle dispense) X = lettere dell'alfabeto U cifre decimali U segni di punteggiatura U simboli matematici U altri caratteri speciali (spazio, ritorno a capo....) Sistemi diversi possono usare codifiche diverse: ad esempio su DOS/Windows il ritorno a capo è composto da due caratteri (carriage return; new line) su Linux solo da uno e questo può causare problemi di incompatibilità in programmi che non gestiscono entrambe le codifiche. Lo standard per le codifiche dei caratteri è definita dalla tabella ASCII, che associa caratteri ai numeri interi da 0 a 128. Esistono altre codifiche che permettono di rappresentare più caratteri (tabella ASCII estesa, Unicode (8 e 16 bit)). In ASCII: A=65, B=66 e così via. Vengono rappresentate prima le maiuscole delle minuscole.

3.1 Rappresentazione di numeri interi con segno Se stiamo lavorando sui numeri non possiamo mettere un più o un meno davanti per specificare il segno, poiché abbiamo a disposizione solo i simboli 0 e 1. Servono quindi altre strategie per utilizzare i numeri con segno.

3.1.1 Rappresentazione in modulo e segno Riservo il bit più a sinistra per rappresentare il segno (0 = +; 1 = -) e i rimanenti bit per rappresentare il modulo del numero. In questo modo in una codifica a 8 bit avrei 7 bit per il numero e uno per il segno, quindi potrò rappresentare meno numeri (la metà) poiché un bit è impiegato per rappresentare il segno. In questo modo ho anche due rappresentazioni possibili per lo zero: 00000000 e 10000000 (sarebbe come dire +0 e -0). Non è una bella codifica perché ha due possibili codifiche per uno stesso valore, e perché +0 e -0 dal punto di vista matematico non ha senso. Rende anche più complicata la somma di positivi e negativi, perché bisogna prima controllare quale dei due addendi ha il modulo più grande. Difetti della rappresentazione in modulo e segno: • •

due rappresentazioni possibili per lo zero (00000000 e 10000000) algoritmo di somma farraginoso

3.1.2 Rappresentazione in complemento a 1 I numeri positivi sono rappresentati normalmente, i numeri negativi si codificano prendendo il modulo del numero e negando tutti i suoi bit. Esempio di rappresentazione in complemento a 1: -98 su 8 bit. Rappresentiamo prima in binario +98: 01100010 Ora neghiamo tutti i suoi bit: 10011101 : questo è -98 in binario rappresentato in complemento a 1. Anche in questo caso il primo bit viene utilizzato per rappresentare il segno: altrimenti non potrei sapere se un numero è positivo o negativo. La rappresentazione in complemento a 1 non elimina il problema della doppia rappresentazione dello 0: infatti 00000000 e 11111111 rappresentano entrambi lo zero (sarebbe come dire +0 e -0).

Somma di numeri in complemento a 1: se voglio calcolare a+b con a e b rappresentati in complemento a 1: • • •

se a>=0, b>=0 funziona l'algoritmo standard se a=0 oppure a>=0, b il comando è >>, che indica che va letto qualcosa dal flusso cin. Stessa cosa per la scrittura in output. Operazioni fondamentali sui flussi • • •

•

aprire il flusso in lettura o in scrittura leggere o scrivere un dato interrogare lo stato del flusso, che può essere: normale, end of file (solo per la lettura), anomalo/errore (ad esempio se tento di leggere un file inesistente, o se voglio leggere un numero ma invece c'è un carattere). chiusura del flusso

17.1 Operare sui file Per leggere o scrivere su file devo associare il file su disco ad una variabile di tipo stream. Da dentro il programma non vedrò il file fisicamente presente sulla memoria di massa, ma una variabile stream, sulla quale possiamo leggere scrivere, e queste operazioni si ripercuoteranno sul vero file. Ogni volta che apro un file in lettura, lo stream inizierà sempre dall'inizio del file. In C++ (e nella maggior parte dei linguaggi) l'input/output non è un'operazione primitiva ma è fornita da librerie. Questo vale anche per i flussi: in C++ la libreria per fare I/O su file è fstream. Questa libreria fornisce i tipi ifstream e ofstream , due flussi che consentono la lettura (ifstream) e la scrittura (ofstream) su file. Per poterli usare in un programma devo dichiarare due variabili di tipi ifstream o ofstream Dichiarazione: ifstream fi; Dopo la dichiarazione il flusso esiste, ma non posso ancora utilizzarlo poiché non è ancora stato associato a nessun file: è come una variabile non inizializzata. L'inizializzazione avviene attraverso una funzione di libreria chiamata open. Open è una funzione interna alla classe ifstream, quindi si invoca attraverso la dot notation nome_flusso.open("nome_file") Inizializzazione (o apertura) del flusso: fi.open("filename") Se quest'operazione va a buon fine, potremo leggere il file specificato semplicemente leggendo dallo stream fi. ATTENZIONE: Se,in scrittura, facciamo fo.open("filename") (dove fo è un ofstream) e specifichiamo un file esistente, questo verrà cancellato e rimpiazzato con un file vuoto su cui

possiamo iniziare a scrivere dal primo carattere. Per aggiungere in coda ad un file esistente bisogna usare altri metodi. Gli stream sono tutti sequenze di caratteri. Possiamo leggere/scrivere singoli caratteri oppure numeri e stringhe formattate come sequenze di caratteri. I/O formattato: si fa con > per la lettura, come abbiamo sempre fatto con cin e cout. Ad esempio fi>>x legge da fi un valore, dello stesso tipo della variabile x, e lo mette in x. fo> e MAX e (fs+sz)-MAX quando fs+sz>MAX.

Coda implementata su un array circolare Funzione enqueue di una coda su array circolare:

Error Enqueue(Queue& q, elem x) { if(q.sz==MAX) return FULL; q.a[(q.fs+q.sz)%MAX]=x; q.sz++; return OK; }

Error dequeue(Queue& q)

{ if(q.sz==0) return EMPTY; q.fs=(q.fs+1)%MAX; q.sz--; return OK; }

20. Gestione dinamica della memoria Un grosso limite degli array è che hanno dimensioni statiche: nelle strutture dati che abbiamo definito nelle lezioni precedenti, dobbiamo stabilire una dimensione massima in fase di compilazione e non può più essere cambiata. Se abbiamo bisogno di strutture dinamiche, queste verranno allocate nello heap, un serbatoio di memoria dinamica a disposizione del programma. Anche lo stack è una porzione di memoria dinamica, ma per un uso specifico: è gestito dal runtime environment viene usato per allocare le estensioni procedurali. Lo heap invece è a disposizione del programma per qualunque utilizzo.

Schema della suddivisione della memoria di un programma.

La separazione tra heap e stack non è fissa come quella tra codice e variabili statiche: le dimensioni di heap e stack infatti possono variare a seconda delle richieste del programma. Quando si esaurisce la parte di memoria riservata al programma dal SO si verificano condizioni di errore come lo stack overflow.

20.1 Puntatori I puntatori sono variabili di programma che puntano a indirizzi di memoria. Un puntatore contiene due informazioni: l'indirizzo del dato a cui punta e il suo tipo. Un dato che sta in memoria e il puntatore ad esso associato vengono messi in relazione dagli operatori * e &. Se ho una variabile x di tipo t allora &x è l'indirizzo di x ed è un puntatore a un dato di tipo t. Viceversa se ho un puntatore p che punta a dati di tipo t allora *p è il dato puntato da p. &x è un valore destro, non posso eseguire assegnazioni su di esso perché non indica un dato, ma un indirizzo. *p è un valore sia sinistro che destro, perché posso sia scrivere in quella posizione tramite assegnazione sia usarla come dato. Variabili puntatore: dichiarazione: * Esempio: int * p Ogni volta che dichiariamo una variabile puntatore int * p, nella memoria statica viene allocata una cella di tipo puntatore adatta a contenere un indirizzo, non un intero. Se sul puntatore eseguo un'assegnazione del tipo p=&n (dove n è una variabile int) in p verrà messo l'indirizzo di n. In questo modo ho operato solo sulla memoria statica, lo heap non è stato modificato. Questo però non è un utilizzo molto furbo dei puntatori: non ha molto senso usare un puntatore per accedere ad una variabile statica, quando vi posso accedere direttamente. I puntatori di solito si usano per accedere allo heap.

20.2 Gestione dello heap Per chiedere memoria allo heap si usa il comando new, che dev'essere associato a un tipo. Sintassi: new Semantica: alloca sullo heap una cella del tipo specificato e restituisci il suo indirizzo. L'indirizzo restituito da new può essere assegnato ad un puntatore dello stesso tipo che abbiamo specificato in new. Esempio: int * p; p=new int;

Stato della memoria dopo aver eseguito allocazione e assegnazione

20.2.1 Memory leak Il memory leak è una situazione in cui un puntatore viene cancellato o sovrascritto senza prima deallocare l'area di memoria a cui puntava: in questo modo quella memoria sarà sempre occupata, ma non più accessibile, causando uno spreco di memoria. Per questo è importante fare sempre la delete quando la memoria indirizzata da un puntatore non serve più. Si fa con delete [] nome;

20.3 Array dinamici Si può allocare dinamicamente anche un array di variabili, con la sintassi new [] dove l'intero tra le paren...