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.

Notazione asintotica (1)

  • Definizione e significato degli insiemi O, Ω e Θ
  • Algebra della notazione asintotica
  • Esempi

Esercizi assegnati:

  • Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
  • Calcolare l'ordine asintotico stretto di alcune funzioni assegnate.

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

Esercizi assegnati:

  • Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle dispense)

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

Ricorsione

  • funzioni matematiche ricorsive ed algoritmi ricorsivi
  • ricerca sequenziale e binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

Esercizi assegnati:

  • Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
    • dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
    • dato un intero n, calcolare la somma di n valori immessi da tastiera (uno per ogni chiamata ricorsiva)
    • calcolare il MCD tra due interi positivi x ed y come segue:
      • sia y<x
      • se y=0 allora MCD(x,y)=y
      • altrimenti MCD(x,y))MCD(y, x%y) (dove x%y indica il resto della divisione intera tra x e y)
    • risolvere il problema delle Torri di Hanoi

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.

Esercizi assegnati:

  • Risolvere con tutti i metodi possibili alcune equazioni di ricorrenza assegnate

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

Il problema dell'ordinamento (1)

  • algoritmi naif: insertion sort, selection sort e bubble sort; calcolo del costo computazionale; algoritmi input sensitive
  • albero delle decisioni e teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti

Esercizi assegnati:

  • Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente può essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo così modificato.
  • Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione.
  • Modificare l'algoritmo di Bubble Sort in modo che non prosegua la computazione se il vettore risulta ordinato (con l'aggiunta di una flag).
  • Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).
  • Determinare l'albero delle decisioni del Selection Sort.

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)

Esercizi assegnati:

  • Scrivere la funzione di fusione ricorsiva
  • Scrivere Merge Sort iterativo

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)

Esercizi assegnati:

  • Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2.
  • Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort.
  • Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali.

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)

Esercizi assegnati:

  • Scrivere una funzione che restituisca il valore minimo di un HeapMax e calcolarne il costo computazionale
  • Scrivere Heapsort sfruttando la struttura dati HeapMin

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

Esercizi assegnati:

  • 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

Esercizi assegnati:

  • 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

Esercizi assegnati:

  • Dato G memorizzato con una struttura dati X, dare in output G memorizzato con un'altra struttura dati Y, dove X ed Y variano in tutti i modi possibili tra le 4 rappresentazioni viste

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" >

Topic attachments
I Attachment History Action Size DateSorted ascending Who Comment
C source code filec esempio1.c r1 manage 0.2 K 2011-03-15 - 10:25 SimoneSilvestri  
C source code filec fattoriale_iterativo.c r1 manage 0.3 K 2011-03-18 - 07:26 SimoneSilvestri Fattoriale iteraivo
C source code filec find_max_array.c r1 manage 0.6 K 2011-03-18 - 07:30 SimoneSilvestri  
C source code filec power_function.c r1 manage 0.4 K 2011-03-24 - 08:48 SimoneSilvestri  
C source code filec sum_positive_matrix.c r1 manage 0.7 K 2011-03-24 - 08:42 SimoneSilvestri  
Texttxt minimo_vettore_ricorsivo.txt r1 manage 0.2 K 2011-03-31 - 11:05 SimoneSilvestri  
Texttxt elemento_comune_vettori.txt r1 manage 0.4 K 2011-04-01 - 13:01 SimoneSilvestri  
Texttxt occorrenze_vettore_ricorsivo.txt r1 manage 0.3 K 2011-04-01 - 13:00 SimoneSilvestri  
Texttxt palidromo_ricorsivo.txt r1 manage 0.4 K 2011-04-01 - 13:01 SimoneSilvestri  
Texttxt to_binary.txt r1 manage 0.2 K 2011-04-15 - 08:55 SimoneSilvestri  
Texttxt trova_vip.txt r1 manage 1.1 K 2011-04-15 - 08:55 SimoneSilvestri  
Texttxt trova_vip_lineare.txt r1 manage 0.8 K 2011-04-28 - 08:27 SimoneSilvestri  
C source code filec int_list.c r1 manage 0.8 K 2011-05-10 - 09:16 SimoneSilvestri  
C source code filec coda.c r1 manage 1.5 K 2011-05-12 - 14:07 SimoneSilvestri  
C source code filec inverti_lista.c r1 manage 1.7 K 2011-05-12 - 14:09 SimoneSilvestri  
C source code filec pila.c r1 manage 1.2 K 2011-05-12 - 14:07 SimoneSilvestri  
C source code filec elimina_occorrenze.c r1 manage 2.0 K 2011-05-19 - 10:51 SimoneSilvestri  
C source code filec inverti_list.c r1 manage 1.5 K 2011-05-19 - 10:50 SimoneSilvestri  
C source code filec pop.c r1 manage 0.2 K 2011-05-19 - 10:50 SimoneSilvestri  
C source code filec inserimento_ordinato.c r1 manage 1.0 K 2011-05-26 - 08:09 SimoneSilvestri  
C source code filec liste_funzioni_ricorsive.c r1 manage 2.5 K 2011-05-26 - 08:09 SimoneSilvestri  
Edit | Attach | Watch | Print version | History: r294 < r293 < r292 < r291 < r290 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r294 - 2020-05-29 - TizianaCalamoneri






 
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