DiarioLezioni < Infogen/AA1011

Tags: view all tags

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

<font color="#AF0F0F"><b>Giovedì 10 marzo (Lezione 1)</b></font> - Introduzione al corso. Informatica visible e invisibile. Aree cruciali. Al-khwarismi, al-jabr e Cervantes. Programmazione in grande e in piccolo. Cos'&egrave; un algoritmo. Algoritmi sequenziali e paralleli. Algoritmi deterministici, probabilistici, non deterministici. Problemi di decisione, di ricerca, di ottimizzazione. Ambiti degli algoritmi: analisi, sintesi, classificazione. 

<font color="#AF0F0F"><b>Venerdì 11 marzo (Lezione 2)</b></font> - Panoramica su strutture dati, complessit&agrave; 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&agrave; nel caso migliore, peggiore, tempo di calcolo medio. Notazione asintotica: O grande ("it allows us to be sloppy&#8212;but in a satisfactorily controlled way", cfr. [[%ATTACHURL%/ocalc.pdf][Knuth comments on this notation]]), delimitazione asintotica superiore (upper bound).

<font color="#AF0F0F"><b>Martedì  15 marzo (Lezione 3)</b></font> - Notazione asintotica. Omega grande: delimitazione asintotica inferiore (lower bound). Theta grande (delimitazione esatta, o limite asintotico stretto). Classi di complessit&agrave; asintotica per algoritmi: costante, logaritmica, polilogaritmica, lineare, pseudolineare, quadratica, cubica, polinomiale, esponenziale, fattoriale. Numeri di Fibonacci, relazione ricorsiva, espressione esponenziale con la sezione aurea. 
 
<font color="#AF0F0F"><b>Mercoledì  16 marzo (Tutorato 1)</b></font> - Ecco la [[%ATTACHURL%/InfoGen_scheda01.pdf][prima scheda di esercizi ]] proposti nel tutorato.

 <font color="#AF0F0F"><b>Giovedì  17 marzo </b></font> - Lezioni sospese per i 150 anni dell'unit&agrave; d'Italia. Un omaggio musicale: [[http://dl.dropbox.com/u/15083924/Camicia%20Rossa.m4a][Camicia Rossa]], cantata da Daniele Poli nell'esecuzione del gruppo
[[http://www.tuscaegentes.it/][Tuscae Gentes]].

 <font color="#AF0F0F"><b>Venerdì  18 marzo (Esercitazione 1)</b></font> - Introduzione al modello RAM e al linguaggio C. Alcuni programmi in C proposti durante l'esercitazione:
   * [[%ATTACHURL%/1-min-primo.c][1-min-primo.c]]: 1-min-primo.c

   * [[%ATTACHURL%/2-min-secondo.c][2-min-secondo.c]]: 2-min-secondo.c

   * [[%ATTACHURL%/3-min-max.c][3-min-max.c]]: 3-min-max.c

   * [[%ATTACHURL%/4-ricerca-lineare.c][4-ricerca-lineare.c]]: 4-ricerca-lineare.c

   * [[%ATTACHURL%/5-ricerca-binaria.c][5-ricerca-binaria.c]]: 5-ricerca-binaria.c


 <font color="#AF0F0F"><b>Martedì  22 marzo (Lezione 4)</b></font> - 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.

 <font color="#AF0F0F"><b>Mercoledì  23 marzo (Tutorato 2)</b></font> - Ecco la   
[[%ATTACHURL%/InfoGen_scheda02.pdf][seconda scheda di esercizi ]] proposti. *Attenzione!* Versione modificata il 31/3.

 <font color="#AF0F0F"><b>Giovedì  24 marzo (Esercitazione 2)</b></font> - 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.

 <font color="#AF0F0F"><b>Venerdì 25 marzo (Lezione 5)</b></font> - Proposizione: in un albero binario in cui ogni nodo interno ha esattamente due figli, il numero totale di nodi interni &egrave; uguale al numero delle foglie meno 1. Calcolo della complessit&agrave; 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&agrave; 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.

 <font color="#AF0F0F"><b>Martedì  29 marzo (Lezione 6)</b></font> - Algoritmo ricorsivo per la ricerca binaria, e sua complessit&agrave;. Relazioni di ricorrenza per il tempo di esecuzione di un algoritmo ricorsivo: metodo per iterazione, metodo per sostituzione. Esempi e problemi correlati. 

 <font color="#AF0F0F"><b>Mercoledì 30 marzo (Tutorato 3)</b></font> - Ecco la [[%ATTACHURL%/InfoGen_scheda03.pdf][terza scheda di esercizi]] proposti. *Attenzione!* Versione modificata il 31/3.

 <font color="#AF0F0F"><b>Giovedì 31 marzo (Esercitazione 3)</b></font> - 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).

 <font color="#AF0F0F"><b>Venerdì 1 aprile (Lezione 7)</b></font> - 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. 
 
<font color="#AF0F0F"><b>Martedì  5 aprile (Lezione 8)</b></font> - 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.

<font color="#AF0F0F"><b>Mercoledì  6 aprile (Tutorato 4)</b></font> - Ecco la [[%ATTACHURL%/InfoGen_scheda04.pdf][quarta scheda di esercizi]]. 

<font color="#AF0F0F"><b>Giovedì 7 aprile (Esercitazione 4)</b></font> - 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.

<font color="#AF0F0F"><b>Venerdì  8 aprile (Lezione 9)</b></font> - Ordinamento per selezione (selection sort), invarianza di ciclo, complessit&agrave;. 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&agrave; col teorema principale. 

<font color="#AF0F0F"><b>Martedì  12 aprile (Lezione 10)</b></font> - Gli heap.

<font color="#AF0F0F"><b>Mercoledì  13 aprile (Tutorato 5)</b></font> - Esercizi di ricapitolazione dalle schede 1., 2., 3. e 4. 

<font color="#AF0F0F"><b>Giovedì  14 aprile </b></font> - Prima prova intermedia

<font color="#AF0F0F"><b>Giovedì  21 aprile - Martedì  26 aprile</b></font> - Buone vacanze di Pasqua! Qui trovate alcune 
[[http://www.i-programmer.info/news/150-training-a-education/2255-sorting-algorithms-as-dances.html][animazioni di algoritmi di ordinamento...]]

<font color="#AF0F0F"><b>Mercoledì  27aprile (Tutorato 6)</b></font> - Correzione esonero

<font color="#AF0F0F"><b>Giovedì  28 aprile (Esercitazione 5)</b></font> - Implementazione di [[%ATTACHURL%/stack.c][pile]] e [[%ATTACHURL%/queue.c][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.

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

Osservazioni su iterazione e ricorsione possono essere trovati nella seguente dispensa  
  [[%ATTACHURL%/dispensa1.pdf][Sviluppare Programmi Corretti]]. (i curiosi potranno trovarvi molto altro :)


<font color="#AF0F0F"><b>Martedì 3 maggio (Lezione 11)</b></font> - Inserimento, estrazione del massimo, mantenimento della propriet&agrave; di heap (come array e come albero). Creazione di uno heap da un array. Heapsort e sua complessit&agrave; temporale.

<font color="#AF0F0F"><b>Mercoledì  4 maggio (Tutorato 7)</b></font> - Ecco la [[%ATTACHURL%/InfoGen_scheda05.pdf][quinta scheda di esercizi]].

<font color="#AF0F0F"><b>Giovedì  5 maggio (Esercitazione 7)</b></font> - 
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.

   * [[%ATTACHURL%/hanoi.c][hanoi.c]]: codice Torre di Hanoi iterativo

<font color="#AF0F0F"><b>Venerdì  6 maggio (Lezione 12)</b></font> - 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&agrave; lineare quando anche k &egrave; O(n). Quicksort. Funzione di partizione. Complessit&agrave;: problemi per il bilanciamento della suddivisione. Analisi del caso peggiore. Analisi (probabilista) del caso medio.

<font color="#AF0F0F"><b>Martedì  10 maggio (Lezione 13)</b></font> - 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). [[http://www.dsi.uniroma1.it/~md1c/md1c.pdf][Appunti di Combinatoria]] a cura di C. Malvenuto e [[http://w3.uniroma1.it/dipinfo/visuadoc.asp?iddoc1=19][J&aacute;nos K&ouml;rner]], cap. 1.

<font color="#AF0F0F"><b>Mercoledì  11 maggio (Tutorato 8)</b></font> - [[%ATTACHURL%/InfoGen_scheda06.pdf][Sesta scheda di esercizi]] sui grafi.

<font color="#AF0F0F"><b>Giovedì  12 maggio (Esercitazione 8)</b></font> - 
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.

  [[%ATTACHURL%/dispensa.pdf][Dispensa su Tipi di Dato Induttivi]]
  
<font color="#AF0F0F"><b>Venerdì  13 maggio (Lezione 14)</b></font> - Connessione in un grafo. Passeggiate, cammini, circuiti, cammini semplici, cicli. La relazione di raggiungibilit&agrave;. Grafi connessi. Distanza in un grafo. Grafi aciclici (foreste). Alberi e alberi radicati.

<font color="#AF0F0F"><b>Martedì 17 maggio (Lezione 15)</b></font> - Minimalit&agrave; e massimalit&agrave; 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).

<font color="#AF0F0F"><b>Mercoledì 18 maggio (Tutorato 9)</b></font> -  Potete gi&agrave; scaricare la [[%ATTACHURL%/InfoGen_scheda07.pdf][settima scheda di esercizi]] che verrano proposti, su alberi e distanza.

<font color="#AF0F0F"><b>Giovedì  19 maggio (Esercitazione 9)</b></font> - Introduzione agli alberi binari. Laboratorio: implementazione delle visite in profondità
(preorder, in order, post order).

<font color="#AF0F0F"><b>Venerdì  20 maggio (Lezione 16)</b></font> - Proposizione: In un grafo aciclico il numero di archi &egrave; 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'&egrave; almeno un vertice di grado 1. Proposizione: G &egrave; un albero se e solo se G'=G-v &egrave; un albero, con v foglia (permette la ricorsione negli alberi. 

<font color="#AF0F0F"><b>Martedì  24 maggio (Lezione 17)</b></font> - 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. 

<font color="#AF0F0F"><b>Mercoledì  25 maggio (Tutorato 10)</b></font> - Esercizi sulle schede 6 e 7.

<font color="#AF0F0F"><b>Giovedì  26 maggio (Esercitazione 10)</b></font> - 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.

<font color="#AF0F0F"><b>Venerdì  27 maggio (Lezione 18)</b></font> - 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&iacute;k) per la ricerca di un albero di copertura di costo minimo; il problema della selezione di attivit&agrave;. Ancora sul quicksort: dimostrazione probabilista del numero di confronti medi eseguiti dal quicksort: trovate alle [[%ATTACHURL%/Scan.pdf][Pag1]], [[%ATTACHURL%/Scan_1.pdf][Pag.2]] e [[%ATTACHURL%/Scan_2.pdf][Pag.3]] la dimostrazione del libro "Discrete Mathematics, di J. Matousek e J. Nesetril, Clarendon Press, Oxford (pagine 290-292).

[[http://twiki.di.uniroma1.it/pub/Algoritmi2/Infogen.WebHome/Disp_greedy.pdf][Appunti sulla tecnica di progettazione "greedy"]] del prof. Angelo Monti.

<font color="#AF0F0F"><b>Martedì  31 maggio (Lezione 19)</b></font> - Esercizi sulla tecnica di progettazione di algoritmi greedy.

<font color="#AF0F0F"><b>Mercoledì  1 giugno (Lezione 20)</b></font> -  Esercizi svolti dall'[[%ATTACHURL%/InfoGen_scheda08.pdf][ottava scheda di esercizi]].

<font color="#AF0F0F"><b>Giovedì  2 giugno</b></font> - Festa della Repubblica

<font color="#AF0F0F"><b>Venerdì  3 giugno (Esercitazione 11)</b></font> - Esercitazione in laboratorio: prova simulata d'esame. I testi sono [[%ATTACHURL%/prova-esame.pdf][questi]]. Soluzioni: [[%ATTACHURL%/biliste.c][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).

  * [[%ATTACHURL%/esercizi.pdf][esercizi.pdf]]: 16 esercizi per i volenterosi


<font color="#AF0F0F"><b>Mercoledì  8 giugno (Tutorato 11)</b></font> -  Ricevimento studenti dalle ore 14.

Attachments

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