Diario delle lezioni (Informatica Generale, canale I-Z, A.A. 2010-2011)

Giovedì 10 marzo (Lezione 1) - Introduzione al corso. Informatica visible e invisibile. Aree cruciali. Al-khwarismi, al-jabr e Cervantes. Programmazione in grande e in piccolo. Cos'è un algoritmo. Algoritmi sequenziali e paralleli. Algoritmi deterministici, probabilistici, non deterministici. Problemi di decisione, di ricerca, di ottimizzazione. Ambiti degli algoritmi: analisi, sintesi, classificazione.

Venerdì 11 marzo (Lezione 2) - Panoramica su strutture dati, complessità computazionale (spaziale e temporale) e correttezza degli algoritmi. Definizioni di tempo di calcolo e spazio di memoria per un algoritmo. Dimensione delle istanze. Tempo di calcolo o complessità nel caso migliore, peggiore, tempo di calcolo medio. Notazione asintotica: O grande ("it allows us to be sloppy—but in a satisfactorily controlled way", cfr. Knuth comments on this notation), delimitazione asintotica superiore (upper bound).

Martedì 15 marzo (Lezione 3) - Notazione asintotica. Omega grande: delimitazione asintotica inferiore (lower bound). Theta grande (delimitazione esatta, o limite asintotico stretto). Classi di complessità asintotica per algoritmi: costante, logaritmica, polilogaritmica, lineare, pseudolineare, quadratica, cubica, polinomiale, esponenziale, fattoriale. Numeri di Fibonacci, relazione ricorsiva, espressione esponenziale con la sezione aurea.

Mercoledì 16 marzo (Tutorato 1) - Ecco la prima scheda di esercizi proposti nel tutorato.

Giovedì 17 marzo - Lezioni sospese per i 150 anni dell'unità d'Italia. Un omaggio musicale: Camicia Rossa, cantata da Daniele Poli nell'esecuzione del gruppo Tuscae Gentes.

Venerdì 18 marzo (Esercitazione 1) - Introduzione al modello RAM e al linguaggio C. Alcuni programmi in C proposti durante l'esercitazione:

Martedì 22 marzo (Lezione 4) - Algoritmi iterativi. Calcolo del tempo di esecuzione per algoritmi iterativi. Algoritmo iterativo per il calcolo del fattoriale e per il calcolo dei numeri di Fibonacci, calcolo del tempo di esecuzione. Algoritmi ricorsivi: esempi per il fattoriale e i numeri di Fibonacci. Calcolo del tempo di esecuzione tramite l'albero delle chiamate ricorsive. Proposizione: l'albero delle chiamate dell'algoritmo ricorsivo per Fibonacci per n ha tante numero di foglie quante l'ennesimo Fibonacci.

Mercoledì 23 marzo (Tutorato 2) - Ecco la seconda scheda di esercizi proposti. Attenzione! Versione modificata il 31/3.

Giovedì 24 marzo (Esercitazione 2) - In laboratorio. Sono stati svolti i seguenti esercizi:

  • chiedere all'utente 3 interi e stamparne la media (non arrotondata);
  • stesso esercizio, ma su un numero di interi scelto dall'utente (invece che 3);
  • ampliare il programma precedente in modo da dire quale numero, tra quelli inseriti dall'utente, è più vicino alla media;
  • ampliare il secondo programma in modo da dire quanti numeri, tra quelli inseriti dall'utente, distano dalla media meno di un epsilon inserito dall'utente.

Venerdì 25 marzo (Lezione 5) - Proposizione: in un albero binario in cui ogni nodo interno ha esattamente due figli, il numero totale di nodi interni è uguale al numero delle foglie meno 1. Calcolo della complessità dell'algoritmo ricorsivo per i numeri di Fibonacci. Gli array. Problemi di ricerca in un array. Algoritmo di visita di un array. Ricerca lineare (o sequenziale) in un vettore disordinato. Complessità nel caso migliore, peggiore, tempo di esecuzione medio. Ricerca binaria (o dicotomica) in un array ordinato. Algoritmo iterativo e tempo di calcolo nel caso peggiore col numero di confronti. Tecnica di progettazione di algoritmi ricorsivi: divide et impera : schema generale e conseguente relazione ricorsiva per il tempo di esecuzione.

Martedì 29 marzo (Lezione 6) - Algoritmo ricorsivo per la ricerca binaria, e sua complessità. Relazioni di ricorrenza per il tempo di esecuzione di un algoritmo ricorsivo: metodo per iterazione, metodo per sostituzione. Esempi e problemi correlati.

Mercoledì 30 marzo (Tutorato 3) - Ecco la terza scheda di esercizi proposti. Attenzione! Versione modificata il 31/3.

Giovedì 31 marzo (Esercitazione 3) - Puntatori in C: i costrutti del linguaggio e il relativo funzionamento nel modello della RAM; operatori * e &; operazioni su puntatori e aritmetica dei puntatori; puntatori e vettori; passaggio di parametri per riferimento (Sezioni da 7.1 a 7.4, 7.7 e 7.8 del Deitel and Deitel).

Venerdì 1 aprile (Lezione 7) - Relazioni ricorsive per il tempo di esecuzione T(n)=aT(n/b)+f(n): metodo dell'albero di ricorsione; teorema principale: sua dimostrazione nel caso in cui la dimensione dell'input sia una potenza esatta.

Martedì 5 aprile (Lezione 8) - Relazioni d'ordine parziali e totali. Ordine lessicografico su un alfabeto finito. Problema dell'ordinamento. Algoritmi di ordinamento per array: per confronti, interni/esterni, in loco, stabili. Ordinamento per inserimento (insertion sort): dimostrazione di correttezza per invarianza di ciclo, tempo di esecuzione nel caso migliore e peggiore.

Mercoledì 6 aprile (Tutorato 4) - Ecco la quarta scheda di esercizi.

Giovedì 7 aprile (Esercitazione 4) - Allocazione dinamica della memoria (funzioni malloc, free e sizeof); vettori dinamici; array multidimensionali come vettori e loro allocazione dinamica. Strutture dati ricorsive: Liste concatenate e loro creazione. (Sezioni da 12.1 a 12.4 del Deitel and Deitel). Laboratorio: ordinamento a bolle su liste di interi.

Venerdì 8 aprile (Lezione 9) - Ordinamento per selezione (selection sort), invarianza di ciclo, complessità. Ordinamento per fusione (mergesort): descrizione dell'algoritmo divide et impera, esempi, algoritmo di fusione, invariante di ciclo, relazione ricorsiva per il tempo di esecuzione, calcolo della complessità col teorema principale.

Martedì 12 aprile (Lezione 10) - Gli heap.

Mercoledì 13 aprile (Tutorato 5) - Esercizi di ricapitolazione dalle schede 1., 2., 3. e 4.

Giovedì 14 aprile - Prima prova intermedia

Giovedì 21 aprile - Martedì 26 aprile - Buone vacanze di Pasqua! Qui trovate alcune animazioni di algoritmi di ordinamento...

Mercoledì 27aprile (Tutorato 6) - Correzione esonero

Giovedì 28 aprile (Esercitazione 5) - Implementazione di pile e code usando liste concatenate (si puo' anche vedere come questi argomenti sono svolti sul Deitel and Deitel, sezioni 12.5 e 12.6). In laboratorio: assegnamento di due esercizi tipo quelli che saranno dati alla prova finale di laboratorio:

  • si scriva una funzione che, presa in input una pila (piena) e una coda (vuota), copi gli elementi della pila nella coda, rispettando l'ordine di inserimento. Ad esempio, se la pila e' (TOP) 3 -> 2 -> 1 -|| , la coda deve essere (FIRST) 1 -> 2 -> 3 (LAST) -||
  • si implementi una coda con priorita'. In tale struttura dati, ogni nodo ha associata anche una priorita' (per esempio un carattere, giusto per distinguere la priorita' dall'informazione contenuta nel nodo) e i nodi devono essere ordinati in modo decrescente (da first a last) rispetto alla priorita', indipendentemente dall'ordine di inserimento. Nodi con stessa priorita', invece, vengono memorizzati con la normale politica FIFO delle code. La politica per l'estrazione dalla coda, invece, e' sempre la stessa: elimino l'elemento first. Ad esempio, se la coda e' (FIRST) 1b -> 2b -> 3c (LAST) -|| e voglio inserire l'elemento 4 con priorita' d (ma anche c), questo va messo alla fine della coda; se inserisco 4 con priorita' b, questo va messo tra 2 e 3; se lo inserisco con priorita' a, va messo come primo elemento della coda.

Venerdì 29 aprile (Esercitazione 6) - Ricorsione e iterazione. Definizioni induttive e programmi ricorsivi.
Esempi classici (e semplici): fattoriale e fibonacci.
Funzione ricorsiva efficiente (lineare in n) per il calcolo dell'ennesimo numero di fibonacci.
Soluzioni inerentemente ricorsive (induttive): il problema della Torre di Hanoi.

Osservazioni su iterazione e ricorsione possono essere trovati nella seguente dispensa Sviluppare Programmi Corretti. (i curiosi potranno trovarvi molto altro smile

Martedì 3 maggio (Lezione 11) - Inserimento, estrazione del massimo, mantenimento della proprietà di heap (come array e come albero). Creazione di uno heap da un array. Heapsort e sua complessità temporale.

Mercoledì 4 maggio (Tutorato 7) - Ecco la quinta scheda di esercizi.

Giovedì 5 maggio (Esercitazione 7) - Stack di sistema e record di attivazione di una chiamata a funzione. Ricorsione: trasformazione sistematica di ogni programma ricorsivo in iterativo, mediante simulazione dello stack degli activation record. Esempio: Torre di Hanoi.

  • hanoi.c: codice Torre di Hanoi iterativo

Venerdì 6 maggio (Lezione 12) - Delimitazione inferiore di algoritmi di ordinamento per confronti Omega(n log n). Alberi di decisione (o dei confronti). Lemma1: in un albero di decisione per gli ordinamenti ci sono almeno n! foglie. Lemma2: un albero binario (pieno) con k foglie ha altezza almeno [log_2 k] (parte intera sup). Approssimazione di Stirling per n!. Counting sort (ordinamento di insiemi formati dai naturali da 0 a k) come esempio di ordinamento che abbia complessità lineare quando anche k è O(n). Quicksort. Funzione di partizione. Complessità: problemi per il bilanciamento della suddivisione. Analisi del caso peggiore. Analisi (probabilista) del caso medio.

Martedì 10 maggio (Lezione 13) - Grafi semplici: vertici, archi, incidenza, adiacenza, intorni, grado di un vertice, grado del grafo. Esempi: il grafo completo, il ciclo, il cammino, il grafo bipartito completo. Sottografi; sottografi ricoprenti, e indotti. Isomorfismo. Grafo complementare di un dato grafo. Proposizione (tecnica del doppio conteggio): la somma dei gradi dei vertici e' pari al doppio del numero degli archi (handshaking lemma). Appunti di Combinatoria a cura di C. Malvenuto e János Körner, cap. 1.

Mercoledì 11 maggio (Tutorato 8) - Sesta scheda di esercizi sui grafi.

Giovedì 12 maggio (Esercitazione 8) - Programmi ricorsivi su lista: stampa, stampa in ordine inverso, inserimento ordinato di un elemento, rovesciamento di una lista (con allocazione di memoria e in place), tecnica di uso dei parametri per propagare risultati parziali alle successive chiamate ricorsive.

Dispensa su Tipi di Dato Induttivi

Venerdì 13 maggio (Lezione 14) - Connessione in un grafo. Passeggiate, cammini, circuiti, cammini semplici, cicli. La relazione di raggiungibilità. Grafi connessi. Distanza in un grafo. Grafi aciclici (foreste). Alberi e alberi radicati.

Martedì 17 maggio (Lezione 15) - Minimalità e massimalità in una famiglia di sottoinsiemi. Esempio: clique e numero di clique di un grafo. In un grafo connesso esiste almeno un vertice di grado 1. Caratterizzazione di un albero: le seguenti sono equivalenti: i) G albero. ii) esiste un unico cammino comunque presi due vertici di G. iii) G grafo connesso minimale. iv) G grafo aciclico massimale. v) G connesso e |E|=|V|-1 (formula di Eulero).

Mercoledì 18 maggio (Tutorato 9) - Potete già scaricare la settima scheda di esercizi che verrano proposti, su alberi e distanza.

Giovedì 19 maggio (Esercitazione 9) - Introduzione agli alberi binari. Laboratorio: implementazione delle visite in profondità (preorder, in order, post order).

Venerdì 20 maggio (Lezione 16) - Proposizione: In un grafo aciclico il numero di archi è pari al numero di nodi meno il numero di componenti connesse. Alberi di copertura di un grafo connesso. Alberi di copertura del completo: teorema di Cayley (no: dimostrazione). Calcolo del minimo numero di archi da togliere a un completo per avere un grafo sconnesso. Proposizione: in un albero c'è almeno un vertice di grado 1. Proposizione: G è un albero se e solo se G'=G-v è un albero, con v foglia (permette la ricorsione negli alberi.

Martedì 24 maggio (Lezione 17) - In un albero esistono almeno due foglie. In un albero esistono almeno tante foglie quante il grado dell'albero. Strategie per costruire, dato un grafo connesso, un suo albero di copertura. Problema: ricerca dell'albero di copertura di costo minimo in un grafo con archi pesati. Algoritmo di Kruskal.

Mercoledì 25 maggio (Tutorato 10) - Esercizi sulle schede 6 e 7.

Giovedì 26 maggio (Esercitazione 10) - Ancora sugli alberi: visita per livelli. Verifica del bilanciamento di un albero. Versione ingenua e versione efficiente con un'unica scansione dell'albero. Strutture dati generiche: uso di void* come tipo per il campo informazione.

Venerdì 27 maggio (Lezione 18) - Dimostrazione di correttezza dell'algoritmo di Kruskal. Tecnica di progettazione di algoritmi: gli algoritmi greedy. Schema generale, schema di dimostrazione di correttezza, esempi: algoritmo di Kruskal, algoritmo di Prim (Jarník) per la ricerca di un albero di copertura di costo minimo; il problema della selezione di attività. Ancora sul quicksort: dimostrazione probabilista del numero di confronti medi eseguiti dal quicksort: trovate alle Pag1, Pag.2 e Pag.3 la dimostrazione del libro "Discrete Mathematics, di J. Matousek e J. Nesetril, Clarendon Press, Oxford (pagine 290-292).

Appunti sulla tecnica di progettazione "greedy" del prof. Angelo Monti.

Martedì 31 maggio (Lezione 19) - Esercizi sulla tecnica di progettazione di algoritmi greedy.

Mercoledì 1 giugno (Lezione 20) - Esercizi svolti dall'ottava scheda di esercizi.

Giovedì 2 giugno - Festa della Repubblica

Venerdì 3 giugno (Esercitazione 11) - Esercitazione in laboratorio: prova simulata d'esame. I testi sono questi. Soluzioni: primo esercizio; il secondo esercizio è una variazione del calcolo dell'altezza (la prima funzione è esattamente l'altezza, la seconda si ottiene dalla prima mettendo il minimo al posto del massimo).

* esercizi.pdf: 16 esercizi per i volenterosi

Mercoledì 8 giugno (Tutorato 11) - Ricevimento studenti dalle ore 14.

Topic attachments
I Attachment History Action Size Date Who Comment
C source code filec 2-min-secondo.c r1 manage 0.6 K 2011-03-18 - 14:34 ClaudiaMalvenuto  
C source code filec 3-min-max.c r1 manage 0.4 K 2011-03-18 - 14:34 ClaudiaMalvenuto  
C source code filec 4-ricerca-lineare.c r1 manage 0.9 K 2011-03-18 - 14:35 ClaudiaMalvenuto  
C source code filec 5-ricerca-binaria.c r1 manage 1.1 K 2011-03-18 - 14:35 ClaudiaMalvenuto  
PDFpdf InfoGen_scheda01.pdf r1 manage 35.1 K 2011-03-18 - 14:39 ClaudiaMalvenuto Prima scheda di esercizi
PDFpdf InfoGen_scheda02.pdf r2 r1 manage 29.6 K 2011-03-31 - 12:28 ClaudiaMalvenuto Seconda scheda di esercizi
PDFpdf InfoGen_scheda03.pdf r1 manage 39.0 K 2011-03-31 - 12:38 ClaudiaMalvenuto Terza scheda di esercizi
PDFpdf InfoGen_scheda03_sol.pdf r1 manage 34.5 K 2011-03-30 - 09:27 ClaudiaMalvenuto Alcune soluzioni della terza scheda di esercizi
PDFpdf InfoGen_scheda04.pdf r1 manage 28.5 K 2011-04-06 - 10:50 ClaudiaMalvenuto Quarta scheda di esercizi
PDFpdf InfoGen_scheda05.pdf r1 manage 23.8 K 2011-05-04 - 19:46 ClaudiaMalvenuto Quinta scheda di esercizi
PDFpdf InfoGen_scheda06.pdf r1 manage 17.7 K 2011-05-10 - 18:08 ClaudiaMalvenuto Sesta scheda di esercizi
PDFpdf InfoGen_scheda07.pdf r1 manage 31.6 K 2011-05-10 - 18:09 ClaudiaMalvenuto Settima scheda di esercizi
PDFpdf InfoGen_scheda08.pdf r1 manage 24.8 K 2011-05-25 - 16:46 ClaudiaMalvenuto Ottava scheda di esercizi
JPEGjpeg Scan.jpeg r1 manage 1080.8 K 2011-06-20 - 08:49 ClaudiaMalvenuto Prob1
PDFpdf Scan.pdf r1 manage 1084.8 K 2011-06-20 - 08:59 ClaudiaMalvenuto Pagina1
PDFpdf Scan_1.pdf r1 manage 1392.3 K 2011-06-20 - 09:01 ClaudiaMalvenuto Pagina 2
PDFpdf Scan_2.pdf r1 manage 1149.2 K 2011-06-20 - 09:02 ClaudiaMalvenuto Pagina 3
C source code filec biliste.c r1 manage 0.9 K 2011-06-11 - 20:59 DanieleGorla  
PDFpdf esercizi.pdf r1 manage 126.7 K 2011-06-07 - 16:00 IvanoSalvo 16 esercizi per i volenterosi
PDFpdf ocalc.pdf r1 manage 98.8 K 2011-05-07 - 15:54 ClaudiaMalvenuto Knuth comments on O notation
PDFpdf prova-esame.pdf r1 manage 59.5 K 2011-06-03 - 08:32 DanieleGorla  
C source code filec queue.c r1 manage 0.9 K 2011-04-28 - 09:28 DanieleGorla  
C source code filec stack.c r1 manage 0.7 K 2011-04-28 - 09:28 DanieleGorla  
Edit | Attach | Watch | Print version | History: r49 < r48 < r47 < r46 < r45 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r49 - 2012-01-29 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback