DiaLez < Info_gen

Tags: view all tags
---++ <font color="#006400" size="+3">Diario delle Lezioni 2021</font>

<div align="justify" style="margin-left: 5%; margin-right: 10%;">
<b>Mercoledì 24 febbraio 2021 - Lezione 1</b> (*Introduzione al Corso*) <blockquote>
Presentazione del corso. <br />
Introduzione all'informatica e agli algoritmi.<br />
Modello di esecutore: la Random Access Machine e complessità computazionale.
</blockquote>

*Giovedì 25 febbraio 2021 - Lezione 2* (*Notazione Asintotica*)
<blockquote>
Notazione asintotica: O, \Omega, \Theta. <br />
Algebra della notazione asintotica e metodo del limite.
</blockquote>

<b>Lunedì 1 marzo 2021 - Lezione 3</b>  (*Pseudocodice e complessità computazionale*)<blockquote>
Introduzione al calcolo del costo computazionale:  criterio del costo uniforme e criterio del costo logaritmico per le operazioni aritmetiche.<br />
Pseudocodice e costo delle istruzioni. Assegnazione, selezione e cicli.<br />
Esempi: valutazione di un polinomio, somma dei primi _n_ numeri.
</blockquote>

*Giovedì 4 marzo 2021 - Lezione 4* (*Ricerca e Ricorsione I*)
<blockquote>
Il problema della ricerca: ricerca sequenziale e binaria.<br />
Introduzione alla ricorsione: terminazione e correttezza delle definizioni ricorsive. <br>
Funzioni definite induttivamente e programmi ricorsivi.<br>
Ricerca binaria ricorsiva.
</blockquote>

<b>Lunedì 8 marzo 2021 - Lezione 5</b>  (*Ricorsione II*)<blockquote>
Versioni ricorsive di semplici programmi visti in forma iterativa: minimo, ricerca, somma degli elementi di un vettore.<br>
Tranelli delle definizioni ricorsive: Il caso di Fibonacci.<br> 
Modello computazionale della ricorsione: attivazione delle chiamate ricorsive e albero delle chiamate ricorsive.<br> 
Fibonacci efficiente ricorsivo.<br>
Problemi inerentemente ricorsivi: la Torre di Hanoi.
</blockquote>

*Giovedì 11 marzo 2021 - Lezione 6* (*Equazioni di Ricorrenza I*)
<blockquote>
Complessità dei programmi ricorsivi: le equazioni di ricorrenza.<br>
Soluzioni delle equazioni di ricorrenza: metodo iterativo, metodo di sostituzione, metodo dell'albero e Teorema Principale.<br>
Primi esempi di soluzioni con questi metodi.
</blockquote>

*Lunedì 15 marzo 2021 - Lezione 7* (*Equazioni di Ricorrenza II*)
<blockquote>
Revisione del Teorema Principale.<br>
Soluzioni di Equazioni di Ricorrenza con tutti e 4 i metodi.
</blockquote>

*Giovedì 18 marzo 2021 - Lezione 8* (*Algoritmi Elementari di Ordinamento*)
<blockquote>
Algoritmi Elementari di Ordinamento: _InsertionSort_, _SelectionSort_ e _BubbleSort_.<br>
Limite Inferiore al problema dell'ordinamento basato su confronti.
</blockquote>


*Lunedì 22 marzo 2021 - Lezione 9* (*Ordinamento per fusione: mergeSort*)
<blockquote>
L'algortimo di ordinamento _mergeSort_. La funzione di fusione ordinata _merge_.
Analisi di Complessità.<br>
Alcuni esercizi: uso di _insertionSort_ dentro _mergesort_. _InsertionSort_ con ricerca binaria del punto dove inserire.<br>
Un altro esercizio sulle relazioni di Ricorrenza.
</blockquote>

*Giovedì 25 marzo 2021 - Lezione 10* (*L'algortimo quickSort*)
<blockquote>
L'algortimo di ordinamento _quickSort_. La funzione di partizionamento _partiziona_ (versione originale di Hoare). Cenni a funzioni alternative.<br>
Analisi di complessità di _partiziona_. Analisi del caso ottimo e caso pessimo di _quickSort_.<br>
Alcune considerazioni intuitive sul rischio di incappare nel caso pessimo.<br>
Analisi del caso medio di _quickSort_. Cenni a tecniche di randomizzazione per evitare il caso pessimo.
</blockquote>

*Lunedì 29 marzo 2021 - Lezione 11* (*L'algortimo heapSort*)
<blockquote>
Struttura dati heap e sua rappresentazione dentro un vettore.<br>
Funzione _heapify_ che risistema un heap in cui al più la radice sia fuori posto.<br>
Funzione _buildHeap_ che costruisce un heap, in tempo O(_n_). Analisi della complessità di _heapify_ e _buildHeap_.<br>
Costruzione di un vettore ordinato partendo da un heap: l'algoritmo _heapSort_ e sua analisi di complessità.
</blockquote>

*Giovedì 8 aprile 2021 - Lezione 12* (*Algortimi di ordinamento lineari*)
<blockquote>
L'algortimo di ordinamento _countingSort_: ipotesi sui valori delle chiavi.<br>
Adattamento di _countingSort_ al caso di presenza di dati satellite.<br>
Algoritmo _bucketSort_: ipotesi sui valori delle chiavi.<br>
Soluzioni di esercizi su mergeSort: mergeSort iterativo e merge ricorsiva.
</blockquote>

*Lunedì 12 aprile 2021 - Lezione 13* (*Strutture dati I: vettori e liste*)
<blockquote>
Tipi di dato e strutture dati.<br>
Rappresentazione di insiemi dinamici con vettori: caso ordinato e non ordinato. Pro e contro.<br>
La struttura dati lista concatenata. Algoritmi base: ricerca, inserimento, eliminazione.<br>
Cenni alle liste doppiamente concatenate.<br>
*Esercizio Svolto*: inserimento ordinato in lista ordinata.
</blockquote>

*Giovedì 15 aprile 2021 - Lezione 14* (*Strutture dati II: code e pile*)
<blockquote>
Tipo di dato coda e sua implementazione con liste e vettori.<br>
Cenni alle applicazioni delle code e alle code di priorità.<br>
Tipo di dato pila e sua implementazione con liste e vettori.<br>
Applicazioni delle pile: la pila di sistema.<br>
*Esercizio Svolto*: simulazione di una coda con due pile.
</blockquote>

*Lunedì 19 aprile 2021 - Lezione 15* (*Strutture dati III: alberi*)
<blockquote>
Alberi come grafi connessi aciclici: caratterizzazioni.<br>
Alberi radicati e nomenclatura associata: radici, foglie, padri, figli, fratelli, antenati, livelli etc.<br>
Rappresentazione posizionale (simil-heap), a puntatori, a vettori di padri.<br>
Confronti delle rappresentazioni in alcuni semplici problemi: determinazione del padre, dei figli, distanza dalla radice.<br>

*Esercizi Svolti*: Problemi sugli Heap: trovare il minimo, usare min-Heap per Heapsort.
</blockquote>

*Giovedì 22 aprile 2021 - Lezione 16* (*Strutture dati III: alberi: visite*)
<blockquote>
Visite in profondità: pre-order, in-order, post-order.<br>
Complessità computazionale delle visite in profondità.<br>
Applicazioni delle visite: alcuni problemi elementari su alberi.<br>
Tecnica di passare parametri ausiliari: conteggio nodi a livello _k_.<br>
Visita per livelli e sua complessità.
</blockquote>

*Lunedì 26 aprile 2021 - Lezione 17* (*Strutture dati IV: alberi binari di ricerca*)
<blockquote>
Definizioni. Il problema della ricerca e dell'inserimento negli alberi binari di ricerca.
</blockquote>

*Giovedì 29 aprile 2021 - Lezione 18* (*Strutture dati V: tabelle Hash*)
<blockquote>
Tabelle Hash come implementazione dei dizionari.<br>
Risoluzione dei conflitti: liste di trabocco e indirizzamento aperto.<br>
Cenni a buone funzioni di hashing.
</blockquote>

*Lunedì 3 maggio 2021 - Lezione 19* (*Strutture dati VI: alberi red-black*)
<blockquote>
Definizioni e proprietà dei red-black: numero di nodi rispetto all'altezza nera.<br>
Rotazioni destre e sinistre.<br>
Inserimento in un albero red-black.
</blockquote>

*Giovedì 6 maggio 2021 - Lezione 20* (*Strutture dati Comparate: il problema dell'ordinamento sulle liste*)
<blockquote>
Gli algoritmi di ordinamento su liste:
   * Selection Sort
   * Insertion Sort
   * Merge Sort
   * Quick Sort
   * Bubble Sort
Vantaggi e svantaggi (computazionali e di programmazione) rispetto agli stessi algoritmi su vettori.
</blockquote>

*Lunedì 10 maggio 2021 - Lezione 21* (*Grafi I: introduzione ai Grafi*)
<blockquote>
Definizione di grafo e sue varianti (orientato, pesato, etc.).<br>
Definizioni di grado, passeggiata, cammino, circuito, ciclo, componente connessa. <br>
Rappresentazione in memoria dei grafi: matrici di incidenza, adiacenza, liste di adiacenza, lista di archi.<br>
</blockquote>

*Giovedì 13 maggio 2021 - Lezione 22* (*Esercizi di Riepilogo I: Equazioni di Ricorrenza, Quicksort, Liste*)
<blockquote>
Un'equazione di ricorrenza non risolvibile col metodo principale.<br>
Dallo pseudocodice alle equazioni di ricorrenza.<br>
Caso pessimo di Quicksort. Ordinamento di vettori con soli due valori usando partiziona.<br>
Il problema del rovesciamento di una lista.
</blockquote>

*Lunedì 17 maggio 2021 - Lezione 23* (*Grafi II: Visite*)
<blockquote>
Introduzione alle visite: albero di visita, archi all'indietro e archi di attraversamento.<br>
Visita in ampiezza: distanze minime. Assenza di archi all'indietro.<br>
Visita in profondità. Assenza di archi di attraversamento.<br>
Differenze dovute alle diverse rappresentazioni dei grafi.
</blockquote>

*Giovedì 20 maggio 2021 - Lezione 24* (*Esercizi di Riepilogo II: Alberi, Ordinamenti Lineari*)
<blockquote>
Ultime due equazioni di ricorrenza.<br>
Esercizi su alberi: rappresentazioni a vettore dei padri.<br>
Stabilità di Counting Sort ed Efficienza di Bucket Sort.<br>
</blockquote>

*Lunedì 24 maggio 2021 - Lezione 25* (*Grafi III: Cammini Minimi*)
<blockquote>
Cenni ad alcuni esempi di problemi modellabili come cammini minimi: routing di Internet.<br>
L'algoritmo di Dijkstra su grafi diretti con pesi positivi: idea e correttezza.<br>
Complessità dell'algoritmo di Dijkstra: implementazione della coda di priorità con heap e vettore.<br> 
Complessità nei grafi sparsi e densi.<br>
Esempio di non funzionamento su grafi con pesi negativi.
</blockquote>

*Giovedì 27 maggio 2021 - Lezione 26* (*Esercizi di Riepilogo III: Alberi, ABR e Alberi Red-Black*)
<blockquote>
Alcuni esercizi da compiti passati:
   * somma chiavi al più _k_ in un albero;
   * estrazione _k_ minimi da un ABR;
   * stampa foglie in un albero rappresentato a liste di adiacenza e in rappresentazione posizionale.
Esempio di costruzione di un albero red-black<br>
Uso di ABR e alberi red-black in una procedura di ordinamento.
</blockquote>

*Lunedì 31 maggio 2021 - Lezione 27* (*Esercizi di Riepilogo IV: Grafi I*)
<blockquote>
Esercizi su grafi e visite: 
   * trasformazioni tra rappresentazioni: liste di adiacenza e matrici di adiacenza;
   * distanze usando la BFS, diametro di un grafo;
   * ricerca di cicli e determinazione delle componenti connesse.
Ultimi esercizi su liste semplici. 
</blockquote>

*Giovedì 3 giugno 2021 - Lezione 28* (*Esercizi da vecchi compiti I*)
<blockquote>
   * Alberi binari di ricerca;
   * heap e Red Black Tree;
   * cicli in grafo colorato;
   * _k_ elmenti minori in un vettore.
</blockquote>

*Lunedì 7 giugno 2021 - Lezione 29* (*Esercizi da vecchi compiti II*)
<blockquote>
Miscellanea: _k_-mediana usando partiziona di quickSort e applicazioni.<br>
Altri esercizi da vecchi scritti:
   * chiavi maggiori di _a_ in un ABR;
   * differenza simmetrica tra insiemi;
   * punto di sella in una matrice;
   * cancellazione da un heap;
   * verifica se un grafo è semplice. 
Un paio di osservazioni su grafi e algoritmi greedy.
</blockquote>

*Giovedì 10 giugno 2021 - Lezione 30* (*Test di autovalutazione*)
<blockquote>
Distanza tra due insiemi di nodi in un grafo.
</blockquote>

*Giovedì 1 luglio 2021 - Lezione 31* (*Correzione Scritto 21 giugno*)
<blockquote>
   * Il problema del calcolo dei numeri di Cappanacci.
   * Bilanciamento delle parentesi con pile e code.
   * Nodi equidistanti da due nodi dati.
   * Lista dei nodi a distanza _k_ da un nodo dato. 
</blockquote>

-- %USERSIG{IvanoSalvo - 2021-02-25}%
</div>