Diario delle lezioni

A.A. 2019/2020

Martedì 25 Febbraio 2020 - Lezioni 1-2

Introduzione (1)

• Informazioni sul corso.
• Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.

Mercoledì 26 Febbraio 2020 - Lezioni 3-4

Introduzione (2)

• Modello RAM; misura di costo uniforme e logaritmico.

Venerdì 28 febbraio 2020 - Esercitazioni 1-2

• TinyC. Codifica in TinyC del programma che calcola la somma iterando +1 [ D1, sezione 2 ]
• Indagini su un programma iterativo [ L1, sez. 2.1 ]:
  • Precondizioni, Postcondizioni, invarianti di ciclo.
  • Terminazione di un ciclo: funzione di terminazione.
• Esempi:
  • funzione che calcola la moltiplicazione. Uso della funzione somma nel calcolo del prodotto [ D1, sez. 3 ].
  • funzione che calcola il predecessore. Specifica come contratto.

• Esercizi consigliati: Dispensa L1, sez. 2.5, esercizi da 2 a 8.
• Sperimentazioni: Disp. D1, sez. 2.1.

Martedì 3 Marzo 2020 - Esercitazioni 3-4

• Usando l'esempio del predecessore, revisione delle asserzioni logiche: precondizioni, postcondizioni, invarianti, funzioni di terminazione.
• Progetto di funzioni a partire dalle specifiche logiche [ L1, sez. 2.3 ].
  • Esempio: divisione intera.
• Uso di passaggi per riferimento per passare più risultati: funzione int divRef(int, int, int*, int*).
• Utilizzo della funzione divRef nell'algoritmo mcdMaestra [ D1, sez. 4 ].

• Esercizi consigliati: Dispensa L1, sez. 2.5, esercizi da 2 a 8.

Mercoledì 4 Marzo 2020 - Lezioni 5-6

Notazione asintotica (2)

• Metodo del limite
• Pseudocodice
• Valutazione del costo computazionale di un algoritmo
• Un primo esempio
• Esempi di problemi che si possono risolvere in modo più o meno efficiente e loro costo computazionale
  • somma dei primi n interi
  • valutazione di un polinomio in un punto

Venerdì 6 Marzo 2020

Sospensione della didattica per emergenza sanitaria

Martedì 10 Marzo 2020 - Lezioni 7-8-9 (a distanza)

Il problema della ricerca

• ricerca sequenziale e suo costo computazionale nel caso migliore e peggiore
• ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

Mercoledì 11 Marzo 2020 - Lezioni 10-11 (a distanza)

Soluzioni delle equazioni di ricorrenza (1)

• metodi risolutivi (1):
  • metodo iterativo;
  • metodo di sostituzione;
  • metodo dell'albero.

Venerdì 13 marzo 2020 - Esercitazioni 5-6 (a distanza)

• Ancora sui passaggi per riferimento: funzione scambia(int*,int*)
• Passaggio di parametri: call-by-value: impossibilità di scrivere una funzione myAnd equivalente all'operatore && predefinito.
• Call-by-value, funzione ap(int*,int*,int,int) (assegnamento parallelo à la Python) [ D2, sez. 2 ].
• I problemi di alias: funzione scambia(int*,int*) senza variabile di appoggio [ D2, sez. 3 ].
• Induzione e Ricorsione: definizione induttiva di + e funzione sommaRec(int, int) [ D3, sez. 1.1 ].
• Esercizio: predecessore ricorsivo in TinyReC. Riflessioni sulla completezza computazioneale di TinyReC.
• Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.

• Esercizi consigliati: Dispensa D2 [sez. 4 ]
• Esercizi consigliati: Dispensa D3 [sez. 1.3 ]

Martedì 17 marzo 2020: Esercitazioni 7-8: (a distanza)

• Esecuzione della funzione ricorsiva di Fibonacci: evoluzione della pila di sistema.
• Iterazione e ricorsione: Fibonacci iterativo efficiente. Trasformazione sistematica di un ciclo in una funzione ricorsiva.
• Dimostrazioni di correttezza per programmi ricorsivi. [ D3, sez. 2 ]
• Problemi con soluzione inerentemente ricorsiva: il problema della Torre di Hanoi [ D3, sez. 3 ]
• Soluzione Esonero 2014 sul tema: il problema del massimo fattore primo [ S4 ]

• Esercizi consigliati: Dispensa 3 [sez. 2.4 e 3.3 ]

Mercoledì 18 Marzo 2020 - Lezioni 12-13 (a distanza)

Soluzioni delle equazioni di ricorrenza (2)

• metodi risolutivi (2):
  • metodo principale
• esempi di soluzione di equazioni di ricorrenza

Venerdì 20 Marzo 2020 - Lezioni 14-15

Soluzioni delle equazioni di ricorrenza (2)

• esempi di soluzione di equazioni di ricorrenza

martedì 24 marzo 2020 - Esercitazioni 9-10 (a distanza)

• Introduzione ai vettori in C: definizione e allocazione [ D4, sez. 1 ]. Passaggio di parametri vettori. Vettori e puntatori [ D4, sez. 1.1 ].
• Un primo programma sui vettori: stampa di un vettore, iterativa e ricorsiva [ D4, sez. 1.1 ].
• Un esempio di programma con asserzioni logiche: minimo di un vettore [ D4, sez. 2.1 ].
• Soluzione Esonero 2012: il Problema del baricentro [ S1 ].
• Virtuosismi: Baricentro con un'unica scansione ricorsiva del vettore [ S1 ].

• Esercizi consigliati: Dispensa 4 [sez. 1.3 e 2.6 ],
• Lettura: due grandi classici: crivello di Eratostene [ D4, sez. 2.4 ] e coefficienti binomiali [ D4, sez. 2.5 ].

Mercoledì 25 Marzo 2020 - Lezioni 16-17

Alcuni esercizi svolti

Il problema dell'ordinamento (2)

• algoritmi efficienti:
  • paradigma del Divide et Impera
  • merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
  • cosa non va nel merge sort: una parentesi sull'uso della memoria secondaria
  • quick sort (idea)

Venerdì 27 Marzo 2020 - Lezioni 18-19

Il problema dell'ordinamento (3)

• algoritmi efficienti:
  • quick sort (pseudocodice, pseudocodice e costo della funzione Partiziona, riflessioni sulla scelta del valore soglia, costo computazionale nei casi migliore e peggiore, costo computazionale nel caso medio)

martedì 31 marzo 2020 - Esercitazioni 11-12 (a distanza)

• Soluzione Esonero 2018: il problema del minimo intero libero [ S7 ];
• Vettori variabili (allocati dentro le funzioni e di dimensioni dipendenti da una variabile);
• Vettori dinamici (allocati con malloc o calloc ). Il tipo void *
• Esempio: il Crivello di Eratostene.
• Un aiutino sull'Homework, esercizio 3: il problema delle partizioni [ S3, sez. 1 ]

• Esercizi consigliati: Dispensa 4 [sez. 1.3 e 2.6 ],

Mercoledì 1 Aprile 2020 - Lezioni 20-21

Il problema dell'ordinamento (4)

• algoritmi efficienti
  • heapsort (struttura dati heap; Heapify: pseudocodice e costo computazionale; Build Heap: pseudocodice e costo; Heapsort: pseudocodice e costo)

Venerdì 3 Aprile 2020 - Lezioni 22-23

Il problema dell'ordinamento (5)

• algoritmi lineari
  • counting sort (versione semplificata e versione completa)
  • bucket sort (idea)

martedì 7 aprile 2020 - Esercitazioni 13-14 (a distanza)

• Soluzione Esonero 2016: generazione delle combinazioni di n oggetti presi k a k [ S5 ]
• Vettori bidimensionali: allocazione statica [ D5, sez. 2 ].
• Percorrere righe, colonne e diagonali di una matrice: verifica di un quadrato magico.
• Allocazione di una matrice dinamica [ D5, sez. 3 ].
• Costruzione del triangolo di tartaglia e costruzione di un quadrato magico di ordine dispari.

• Esercizi consigliati: Di tutto un po', su vettori e ricorsione, dispensa D3 e D4.

Mercoledì 8 Aprile 2020 - Lezioni 24-25

Strutture dati fondamentali (1)

• strutture dati ed insiemi dinamici
• confronto tra vettore qualunque e vettore ordinato
• introduzione alle liste: ricerca e inserimento in testa
• cancellazione nelle liste, liste doppiamente puntate

• vari esercizi di manipolazione delle liste.

9-14 Aprile 2020: Vacanze di Pasqua

Mercoledì 15 Aprile 2020 - Lezioni 26-27

• Strutture dati fondamentali (2)
  • pila
  • le operazioni Push e Pop
  • code con priorità
  • la struttura dati coda
  • le operazioni enqueue e dequeue
  • Esercizio: simulazione di una coda tramite due pile

• scrivere lo pseudocodice delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
• scrivere lo pseudocodice delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore

Venerdì 17 Aprile 2020 - Lezioni 28-29

• Strutture dati fondamentali (3)
  • alberi (1)
    • definizione tramite la nozione di grafo
    • caratterizzazione degli alberi
    • memorizzazione degli alberi:
      • tramite record e puntatori
      • posizionale
      • tramite vettore dei padri
      • confronto delle tre strutture dati

martedì 21 aprile 2020 - Esercitazioni 15-16 (a distanza)

• Costruire tipi di dato: struct e typedef. Esempio: memorizzare date [ D6, sez. 1 ].
• Tipo di dato sequenza: una visione algebrica. Costruttori e distruttori. [ D6, sez. 3 ].
• Le sequenze in C: liste concatenate [ D6, sez. 3 ].
• Primi programmi con le liste, e primi problemi: alias e side-effects [ D6, sez. 3.2 ]

• Esercizi consigliati: struct e tipi di dato [ D3, sez. 1.1 ] e liste [ sez.*3.7* ].

Mercoledì 22 Aprile 2020 - Lezioni 30-31

• Strutture dati fondamentali (4)
  • alberi (2)
    • visite di alberi: in-ordine, pre-ordine e post-ordine
      • pseudocodice ricorsivo
      • costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
      • esercizi che si risolvono utilizzando le visite

Venerdì 24 Aprile 2020 - Lezioni 32-33

• Strutture dati fondamentali (5)
  • alberi (3)
    • esercizi che si risolvono usando alberi, pile e code
• Esercizi svolti riepilogativi

martedì 28 aprile 2020 - Esercitazioni 17-18 (a distanza)

• Programmi su liste: trattamento funzionale (o immutabile) e per side-effects (mutabile).
• aggiunta di elementi: addTail, append. [ D6, sez. 3.3 e 3.4 ].
• rovesciamento di una lista reverse [ D6, sez. 3.5 ].
• esonero 2012: somma successivi [ S2 ]
• 1mo appello 2012: somma precedenti [ S6, sez. 1.2 ]

• Esercizi consigliati: implementare code e pile con liste semplici, con inserimenti/rimozioni in tempo costante.

Lunedì 6 Maggio 2020 - Lezioni 34-35

• Strutture dati fondamentali (6)
  • dizionari (1)
    • tabelle ad indirizzamento diretto
    • tabelle hash
      • collisioni
      • liste di trabocco
      • tabelle ad indirizzamento aperto e hashing doppio

martedì 5 maggio 2020 - Esercitazioni 19-20 (a distanza)

• Programmazione su liste: rimozione di elementi [ D6 ].
• Programmazione su liste: liste ordinate [ D6 ].
• Compiti passati: lista palindroma, selection Sort su liste, dividi e mergeSort su liste [ S7 ].

• Esercizi consigliati: dispensa [ D6 ].

Venerdì 8 Maggio 2020 - Lezioni 36-37

• Strutture dati fondamentali (7)
  • Alberi binari di ricerca (ABR) (1):
    • definizione e proprietà dell' "ordinamento orizzontale"
    • algoritmo per il massimo e minimo
    • algoritmo per il successore e predecessore
    • algoritmo di inserimento
    • osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza
    • Esercizi svolti sugli ABR (fusione di due ABR senza e con ipotesi aggiuntive).

martedì 12 maggio 2020 - Esercitazioni 21-22 (a distanza)

• Alberi binari radicati: definizione algebrica, rappresentazione in C, costruttori e distruttori.
• Funzioni base su alberi: peso, numero nodi, profondità, uguaglianza.
• Alberi binari: visite e stampe [ D7 ].
• Il problema del bilanciamento [ D7 ].
• Compiti passati: selezione di un cammino e relazione di prefisso tra alberi [ S7 ].

• Esercizi consigliati: dispensa [ D7 ].

Mercoledì 13 Maggio 2020 - Lezioni 38-39

• Strutture dati fondamentali (8)
  • Alberi binari di ricerca (ABR) (2):
    • alberi bilanciati: alberi rosso-neri (1)
      • dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
      • rotazioni
• SOMMINISTRAZIONE TEST DI VALUTAZIONE DEL CORSO

Venerdì 15 Maggio 2020 - Lezioni 40-41

• Strutture dati fondamentali (9)
  • Alberi binari di ricerca (ABR) (3):
    • alberi bilanciati: alberi rosso-neri (2)
      • algoritmo di inserimento
• Esercizi svolti riepilogativi su alberi

martedì 19 maggio 2020 - Esercitazioni 23-24 (a distanza)

• Problemi di riscaldamento: sottoalbero, lista dei nodi, frontiera [ D7 ].
• Ricostruzione di un albero partendo dalle visite preorder e inorder.
• Diametro di un albero.
• Funzioni che generano/modificano alberi: mirror e somma sottoalberi [ D7 ].
• Soluzioni di compiti passati: immersione e shuffle tra liste. Nodi al livello k di un albero, e cammino fino a x. [ S6 ]

• Esercizi consigliati: dispensa [ D7 ].

Mercoledì 20 Maggio 2020 - Lezioni 42-43

• Grafi (1)
  • Definizione e alcune proprietà
  • Rappresentazione in memoria di grafi:
    • liste di adiacenza
    • matrice di adiacenza
    • matrice di incidenza
    • lista di archi
    • confronto tra rappresentazioni

Venerdì 22 Maggio 2020 - Lezioni 44-45

• Grafi (2)
  • Visite di grafi
  • Alberi di visita * Visita in ampiezza: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza (archi di riporto vs. di attraversamento, cammini più corti)
  • Esempi di uso di visita in ampiezza: calcolo dei cammini più corti da un nodo dato

martedì 26 maggio 2020 - Esercitazioni 25-26 (a distanza)

• Calcolo degli Ulam numbers: esonero 2019 (contaSomme). Ulam generativo.
• Esercizi di stile: mille modi di scrivere merge fra vettori [ L2 ].
• Una perla del Maestro E. W. Dijkstra: uguaglianza di vettori a meno di shift [ L3 ].

• Esercizi consigliati: di tutto un po'.

Mercoledì 27 Maggio 2020 - Lezioni 46-47

• Grafi (3)
  • Visita in profondità: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in profondità (archi di riporto vs. di attraversamento)
  • Esempi di uso di visita in profondità: calcolo del numero delle componenti connesse
  • Esercizio svolto sulle visite: verifica della ciclicità di un grafo dato

Venerdì 29 Maggio 2020 - Lezioni 48-49

• Grafi (4)
  • Grafi euleriani: definizione, teorema di Eulero, esercizio
  • Grafi bipartiti: definizione, caratterizzazione, esercizio
  • Accoppiamento massimale massimo, completo: definizione, esercizio, teorema di P. Hall

Mercoledì 3 Giugno 2020 - Lezioni 50-51

• Grafi (5)
  • Grafi planari e relazione di Eulero
  • Colorazione di grafi
  • Un'applicazione alle reti cellulari

Mercoledì 10 Giugno 2020 - Lezioni 52-53

• Esercizi in preparazione dell'esame

Anni Precedenti

alt="joomla visitor" >