DiarioLezioni < Algoritmi1/Inf

Tags: view all tags
---+Diario delle lezioni (Algoritmi I, Informatica, A.A. 2008-2009)


   * 22 Sep - <font color="#660000">Introduzione al corso. Un esempio "giocattolo": i numeri di Fibonacci. Algoritmo ricorsivo, albero della ricorsione.</font>

   * 25 Sep - <font color="#660000">Analisi algoritmo ricorsivo. Algoritmi iterativi. Occupazione di memoria. Notazione asintotica.</font>

   * 29 Sep - <font color="#660000">Algoritmo basato su potenze di matrice. Soluzione ricorrenze per iterazione. Un nuovo esempio: ricerca di duplicati.</font>

   * 02 Oct - <font color="green">Esercitazione: Fibonacci e ricerca dei duplicati ricorsiva</font>

   * 06 Oct - <font color="#660000">Caso peggiore e migliore. Analisi ricerca di duplicati. Insertion e selection sort: pseudocodice e correttezza.</font>

   * 09 Oct - <font color="#660000">Tempo di esecuzione Insertionsort e Selectionsort. Mergesort (con analisi).</font>

   * 13 Oct - <font color="#660000">Heap: altezza, vettore posizionale, fixHeap, cancellazione max, costruzione. Esercizi notazione asintotica.</font>

   * 16 Oct - <font color="green">Esercitazione: Bubblesort iterativo e ricorsivo, variante mergesort</font>

   * 20 Oct - <font color="#660000">Heapsort. Analisi heapify. Teorema master: enunciato ed esempi d'uso. </font>

   * 23 Oct - <font color="blue">Esercitazione annullata per assemblea di studenti e docenti (14 - 18 Aula I NEC)</font>

   * 27 Oct - <font color="blue">Sospensione didattica per protesta Legge 133</font>

   * 30 Oct - <font color="blue">Sospensione didattica per protesta Legge 133</font>

   * 3 Nov - <font color="blue">Sospensione didattica per protesta Legge 133</font>

   * 6 Nov - <font color="green">Esercitazione: Relazioni di ricorrenza, ricerca binaria, analisi fixheap</font>

   * 10 Nov - <font color="#660000">Metodo di sostituzione. Quicksort: partition in loco, analisi caso peggiore e migliore, intuizione caso medio.</font>

   * 13 Nov - <font color="green">Esercitazione: esercizio 2.9, problemi 2.9 e 2.10, esercizio 4.12, esercizio 7 assegnato in classe</font>

   * 17 Nov - <font color="#660000">Lower bound ordinamento. Ordinamenti lineari: integerSort e bucketSort. Problema 4.12.</font>

   * 20 Nov - <font color="#660000">Esercizi di preparazione alla prova intermedia.</font>

   * 24 Nov - <font color="blue">Ore cedute al corso di Laboratorio di Sistemi Operativi</font>

   * 27 Nov - <font color="blue">Prova Intermedia</font>

   * 1 Dec - <font color="#660000">ABR: alberi binari di ricerca. Rappresentazioni di alberi: indicizzate e collegate.</font>

   * 4 Dec - <font color="green"> Esercitazione: soluzioni prova intermedia</font>

   * 8 Dec - <font color="blue">Festività Immacolata Concezione</font>

   * 11 Dec - <font color="#660000">Alberi AVL: definizioni, delimitazione altezza, rotazioni, operazione insert.</font>

   * 15 Dec - <font color="#660000">AVL: operazione delete. Visite di alberi: visita generica, in profondità, per livelli. Esercizi.</font>

   * 18 Dec - <font color="#660000">Definizione di grafo. Grafi orientati. Cammini e cicli. Rappresentazioni in memoria.</font>

   * 8 Jan 2009 - <font color="#660000">Visite di grafi non orientati: visita generica, analisi tempo di esecuzione, visita BFS, proprietà dell'albero BFS.</font>

   * 12 Jan 2009 - <font color="#660000">Visita DFS ricorsiva e iterativa, proprietà dell'albero DFS. Visite di grafi orientati. Calcolo componenti connesse.</font>

   * 15 Jan 2009 - <font color="green">Esercitazione: Esercizi su grafi e alberi AVL. Grafi bipartiti.</font>

   * 19 Jan 2009 - <font color="#660000">Esercizi di preparazione all'esame: grafi e alberi AVL.</font>

<!--

Se non diversamente specificato, i riferimenti bibliografici sono relativi al libro di testo "Algoritmi e strutture dati", Demetrescu, Finocchi, Italiano, Mc Graw Hill, 2004.

---++++ <font color=green> Mercoledì 16 Gennaio 2008</font>

Visita in ampiezza e in profondità su grafi non orientati (problema 11.4). Versione non orientata dei problemi 11.9 e 11.10 e loro varianti.

---++++ <font color=green> Giovedì 10 Gennaio 2008</font>

Visita in ampiezza e in profondità su grafi orientati (problemi 11.9 e 11.10). Varianti dei problemi 11.9 e 11.10 (cambiare sorgente; trovare alberi e foreste che non sono producibili da una visita in ampiezza o in profondità dato un qualsiasi ordinamento dei vertici e dei loro adiacenti).


---++++ <font color=green> Giovedì 20 dicembre 2007</font>

Grafi: algoritmi di visita in ampiezza e in profondità (versione ricorsiva e iterativa). Proprietà degli alberi di copertura e partizione degli spigoli indotta dalle visite (sia per grafi non orientati che per grafi orientati) [Cap. 11, par 11.3] 

---++++ <font color=green> Mercoledì 19 dicembre 2007</font>

Grafi: algoritmo di visita generica, analisi del tempo di esecuzione in funzione delle varie rappresentazioni [Cap. 11, par 11.3] 

---++++ <font color=green> Mercoledì 12 dicembre 2007</font>

Grafi: definizioni fondamentali, rappresentazioni [Cap. 11, par 11.1 e 11.2] 

---++++ <font color=green> Mercoledì 5 dicembre 2007</font>

Tavole hash: definizioni di funzioni hash, uniformità semplice, risoluzione delle collisioni tramite liste di collisione ed indirizzamento aperto. [Cap. 7] 

---++++ <font color=green> Mercoledì 28 novembre 2007</font>

Alberi AVL: operazioni insert e delete. Realizzazione di dizionari tramite tavole ad accesso diretto e tavole hash perfette. [Cap. 6 par. 6.2, cap. 7 par 7.1 e 7.2] 

---++++ <font color=green> Giovedì 22 novembre 2007</font>

Alberi AVL: bilanciamento in altezza, alberi di Fibonacci, calcolo dell'altezza di un albero AVL, rotazioni semplici e doppie. [Cap. 6 par. 6.2] 

---++++ <font color=green>Mercoledì 21 novembre 2007</font>

Ordinamento in tempo lineare: algoritmi intergerSort e bucketSort. Alberi binari di ricerca. [Cap. 4 par. 4.6, cap. 6 par. 6.1] 

---++++ <font color=green>Mercoledì 14 novembre 2007: svolgimento della prova intermedia</font>

---++++ <font color=green>Mercoledì 7 novembre 2007</font>

Quicksort: tempo di esecuzione nel caso peggiore e nel caso medio. Risoluzione di equazioni di ricorrenza per sostituzione. [Cap. 4 par. 4.5, cap. 2 par. 2.5] 

---++++ <font color=green>Mercoledì 31 ottobre 2007</font>

Analisi heapify: discussione del caso in cui l'heap non è completo.  Il teorema fondamentale delle ricorrenze (teorema master): esempi d'uso e dimostrazione completa. [Cap. 2 par. 2.5] 

---++++ <font color=green>Giovedì 25 ottobre 2007</font>

Heap binari, heapsort ed analisi. Rappresentazione posizionale di alberi binari ed ordinamento in loco [Cap. 4 par. 4.3] 

---++++ <font color=green>Giovedì 18 ottobre 2007</font>

Algoritmi di ordinamento quadratici: insertionSort, selectionSort, bubbleSort. Un algoritmo ottimo: mergesort e sua analisi. [Cap. 4 par. 4.2 e 4.4] 

---++++ <font color=green>Mercoledì 17 ottobre 2007</font>

Delimitazioni inferiori e superiori. Un esempio di lower bound: algoritmi di ordinamento basati su confronti. Esercizi sulla notazione asintotica. [Cap. 2 par. 2.3, Cap. 4 par. 4.1] 

---++++ <font color=green>Giovedì 11 ottobre 2007</font>

Ancora sul caso medio: analisi degli algoritmi di ricerca sequenziale e ricerca binaria. La notazione asintotica O, Omega, Theta. [Cap. 2 par. 2.4 e 2.2] 
---++++ <font color=green>Giovedì 4 ottobre 2007</font>

Analisi dell'algoritmo basato sul calcolo di potenze di matrice. Cenni al modello di calcolo. Analisi nel caso peggiore, migliore e medio. Caso di studio: la ricerca sequenziale. [Cap. 1, Cap. 2 par. 2.4]

---++++ <font color=green>Giovedì 27 settembre 2007</font>

Ancora sui numeri di Fibonacci: analisi dell'algoritmo ricorsivo, un algoritmo iterativo esponenzialmente più veloce. Cenni alla notazione O.
Introduzione all'algoritmo basato sul calcolo di potenze di matrice. [Cap. 1]

---++++ <font color=green>Mercoledì 26 settembre 2007</font>

Introduzione al corso. Un esempio "giocattolo": il calcolo dei numeri di Fibonacci. Un algoritmo non corretto e un algoritmo ricorsivo. Primi cenni al calcolo dei tempi di esecuzione di algoritmi ricorsivi: albero della ricorsione ed equazioni di ricorrenza. [Cap. 1]

<br>

---+Diario delle esercitazioni (Informatica)
I file qui postati differiscono leggermente da quelli usati nelle esercitazioni, nel senso che sono stati corretti eventuali errori e sono stati eliminati/aggiunti alcuni punti in base al feedback che si è avuto durante la lezione

---++++ <font color=green>Mercoledì 19 dicembre 2007</font>
   * [[%ATTACHURL%/Esercitazione_7.pdf][Esercitazione_7.pdf]]

   * [[%ATTACHURL%/Esercitazione_7_soluzioni.pdf][Esercitazione_7_soluzioni.pdf]]

---++++ <font color=green>Giovedì 6 dicembre 2007</font>
   * [[%ATTACHURL%/Esercitazione_6.pdf][Esercitazione_6.pdf]]

   * [[%ATTACHURL%/Esercitazione_6_soluzioni.pdf][Esercitazione_6_soluzioni.pdf]]

---++++ <font color=green>Giovedì 29 novembre 2007</font>
   * [[%ATTACHURL%/Esercitazione_5.pdf][Esercitazione_5.pdf]]

   * [[%ATTACHURL%/Esercitazione_5_soluzioni.pdf][Esercitazione_5_soluzioni.pdf]]

---++++ <font color=green>Giovedì 8 novembre 2007</font>
   * [[%ATTACHURL%/esercitazione_4.pdf][esercitazione_4.pdf]]

   * [[%ATTACHURL%/esercitazione_4_soluzioni.pdf][esercitazione_4_soluzioni.pdf]]

---++++ <font color=green>Mercoledì 23 ottobre 2007</font>
   * [[%ATTACHURL%/esercitazione_3.pdf][esercitazione_3.pdf]]

   * [[%ATTACHURL%/esercitazione_3_-_soluzioni.pdf][esercitazione_3_-_soluzioni.pdf]]

---++++ <font color=green>Mercoledì 10 ottobre 2007</font>
   * [[%ATTACHURL%/esercitazione_02.pdf][esercitazione_02.pdf]]

   * [[%ATTACHURL%/esercitazione_02_soluzioni.pdf][esercitazione_02_soluzioni.pdf]]

---++++ <font color=green>Mercoledì 3 ottobre 2007</font>
   * [[%ATTACHURL%/esercitazione_01.pdf][esercitazione_01.pdf]]


<br>

---+Diario delle esercitazioni (Tecnologie Informatiche)

---++++ <font color=green>Giovedì 13 dicembre 2007</font>

Problemi su grafi orientati e non orientati (problema 11.5, insieme indipendente e matching massimali).
Analisi degli algoritmi e rappresentazioni in memoria.

---++++ <font color=green>Giovedì 6 dicembre 2007</font>

Ancora sugli alberi AVL (problema 6.6). Visite preordine, postordine e simmestrica di alberi binari.

---++++ <font color=green>Giovedì 29 novembre 2007</font>

Alberi binari di ricerca (problema 6.1). Alberi AVL (problemi 6.2, 6.3 e 6.4).

---++++ <font color=green>Giovedì 8 novembre 2007</font>

Discussione sui metodi di soluzione delle relazioni di ricorrenza. Esercizi sulla notazione O, omega e theta. Esercizi sulla struttura di heap. Varianti sull' ordinamento (problema 4.9).

---++++ <font color=green>Mercoledì 23 ottobre 2007</font>

Ancora sulle relazioni di ricorrenza (problema 2.5: es. 5 e 7). Varianti della ricerca binaria (problemi 2.8 e 2.9). Mergesort k-ario.

---++++ <font color=green>Mercoledì 10 ottobre 2007</font>

Ancora sui numeri di Tribonacci: algoritmo basato sul calcolo di potenze di matrice. Serie geometrica. Soluzione di relazioni di ricorrenza con il metodo iterativo utilizzando la serie geometrica.

---++++ <font color=green>Mercoledì 3 ottobre 2007</font>

Numeri di Tribonacci. Analisi dell' algoritmo ricorsivo. Algoritmo iterativo esponenzialmente più veloce.
Algoritmo iterativo con spazio di lavoro costante.

-->