Tags:
create new tag
view all tags

Diario delle lezioni

Lezioni degli Anni Accademici Precedenti

Lezioni dell'anno accademico 2017/2018

Lezioni 1-2: venerdý 23 febbraio 2018

Presentazione del corso
Introduzione

  • Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
  • modello RAM; misura di costo uniforme e logaritmico.

Lunedý 26 Febbraio 2018: Lezioni sospese per le condizioni meteo

Lezioni 3-4: mercoledý 28 febbraio 2018

Notazione asintotica (1)

  • Definizione e significato degli insiemi O, Ω e Θ.
  • Esempi.
  • Algebra della notazione asintotica.
  • Valutazione del costo computazionale di un algoritmo.
  • Pseudocodice

Esercizi assegnati: Esercizi assegnati:

  • Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione

Esercitazioni 1-2: venerdý 2 marzo 2018

  • Problemi, classi di Problemi, Soluzioni [ L1, sezioni 1 e 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.

Lunedý 5 Marzo 2018: Lezioni sospese per le elezioni

Mercoledý 7 Marzo 2018: Lezioni sospese per le Olimpiadi di Matematica (aule occupate)

Esercitazioni 3-4: venerdý 9 marzo 2018

  • Funzione compareTo che confronta due numeri naturali.
  • Progetto di funzioni a partire dalle specifiche logiche [ L1, sez. 2.3 ]. Osservazioni sulla complessitÓ dei programmi TinyC.
    • Esempio: divisione intera.
  • Introduzione alla pila di sistema, variabili locali, globali [ D1, sez. 3 ].
  • 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.
  • Elucubrazioni: InutilitÓ dell' if in TinyC. Altri esercizi in Disp. D1, sez. 1.2.

Lezioni 5-6: lunedý 12 marzo 2018

Notazione asintotica (2)

  • Esempi di problemi che si possono risolvere in modo pi¨ o meno efficiente
    • somma dei primi n interi
    • valutazione di un polinomio in un punto

Il problema della ricerca

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

Esercizi assegnati:

  • Calcolare l'andamento asintotico stretto di alcune funzioni
  • Calcolare il caso migliore e peggiore del costo computazionale degli algoritmi di Selection Sort, Insertion Sort e Bubble Sort (pseudocodice sulle dispense)

Lezioni 7-8: mercoledý 14 marzo 2018

Ricorsione

  • funzioni matematiche ricorsive;
  • algoritmi ricorsivi: aspetti principali;
  • ricerca sequenziale: pseudocodice ricorsivo;
  • ricerca binaria: pseudocodice ricorsivo;

Soluzioni delle equazioni di ricorrenza (1)

  • metodo di sostituzione; esempi
  • metodo iterativo; esempi

Esercizi assegnati:

  • Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
    • dato in input un vettore, stampare i suoi valori dal primo all'ultimo
    • dato in input un vettore, stampare i suoi valori dall'ultimo al primo

Esercitazioni 5-6: venerdý 16 marzo 2018

  • Valutazione dei parametri: call-by-value e impossibilitÓ di scrivere una funzione myAnd equivalente a &&.
  • Ancora sui passaggi per riferimento: funzione scambia(int*,int*), 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.
  • Fattoriale: definizione induttiva e programma ricorsivo. Considerazioni sulla sua complessitÓ in TinyC.
  • Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.
  • Funzioni: stack di attivazione delle chiamate [ D2, sez. 3 ].
  • Fibonacci Iterativo.

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

Lezioni 9-10: lunedý 19 marzo 2018

Soluzioni delle equazioni di ricorrenza (2)

  • metodo dell'albero; esempi
  • metodo del teorema principale (senza dimostrazione); esempi

Esercizi svolti in classe:

  • Calcolare la soluzione delle seguenti equazioni di ricorrenza col metodo del problema principale e col metodo iterativo, tenendo conto che per tutte il caso base Ŕ T(1)=Θ(1):
    • T(n)=3T(n/2)+Θ(n)
    • T(n)=2T(n/3)+Θ(n)

Lezioni 11-12: mercoledý 21 marzo 2018 (Prof.ssa Calamoneri)

Soluzioni delle equazioni di ricorrenza (3)

Esercizi svolti in classe:

  • calcolare la soluzione delle seguenti equazioni di ricorrenza:
    • T(n)=2T(n/2)+Θ(n)
    • T(n)=T(n/3)+T(2/3n)+Θ(n) qui i conteggi completi per il metodo iterativo di questa equazione
    • T(n)=4T(n/2)+Θ(n)
  • dove per tutte si ha:
    • T(1)=Θ(1)

Esercitazioni 7-8: venerdý 23 marzo 2018

  • Esercizio: moltiplicazione egiziana ricorsiva;
  • Moltiplicazione egiziana iterativa: sviluppo del programma a partire dalle post-condizioni e invarianti [ D2, sez. 4 ]
  • Fibonacci ricorsivo efficiente [ D3, sez. 2 ].
  • Dimostrazioni induttive di correttezza per funzione ricorsive [ D3, sez. 2 ].
  • Trasformazione sistematica di programmi iterativi in ricorsivi [ D3, sez. 2 ].

Lezioni 13-14: lunedý 26 marzo 2018

Il problema dell'ordinamento (1)

  • Algoritmi semplici: insertion sort, selection sort, bubble sort: pseudocodice e costo computazionale nel caso migliore e peggiore.
  • Teorema sulla limitazione inferiore per il costo computazionale di un algoritmo basato su confronti e scambi.

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 in modo che utilizzi ripetutamente questa funzione.
  • Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).

Lezioni 15-16: mercoledý 28 marzo 2018

Il problema dell'ordinamento (2)

  • Algoritmi efficienti: merge sort, pseudocodice e costo computazionale
  • Algoritmi efficienti: quicksort, pseudocodice

Esercizio svolto in classe:

  • Si consideri una modifica del Merge Sort in cui il caso base si applica ad una porzione del vettore di lunghezza k, ordinata usando l'algoritmo Insertion Sort. Le porzioni cosý ordinate vengono combinate usando il meccanismo standard di fusione. Si determini il valore di k come funzione di n per cui l'algoritmo modificato ha lo stesso tempo di esecuzione asintotico del Merge Sort.
Esercizi assegnati:
  • Scrivere la funzione di fusione utilizzando la ricorsione
  • Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono [a1, a2, a3] e [b1, b2, b3] (con l'implicita ipotesi che a1<a2<a3 e b1<b2<b3)
  • Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n log n))

Da Giovedý 29 Marzo a Martedý 3 Aprile 2018 inclusi: Vacanze di Pasqua

Lezioni 17-18: mercoledý 4 aprile 2018

Il problema dell'ordinamento (3)

  • Algoritmi efficienti: quicksort, costo computazionale nei casi migliore, peggiore e medio (con dimostrazione)
  • Algoritmi efficienti: heapsort (struttura dati heap; funzione heapify: pseudocodice e costo computazionale)

Esercizi assegnati:

  • Calcolare il costo computazionale del Quick sort nei casi in cui: il vettore sia ordinato in senso crescente; il vettore sia ordinato in senso decrescente; il vettore contenga tutti elementi uguali.
  • 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.
  • Scrivere lo pseudocodice di una funzione che, dato un heap di n elementi al quale e' stata aggiunta nella posizione (n + 1) una nuova foglia con valore arbitrario, ripristini la proprieta' di heap nel nuovo albero di dimensione (n + 1). Valutare il costo computazionale.
  • Scrivere lo pseudocodice di una funzione che, dato un heap massimo di n elementi, ripristini la proprieta' di heap dopo che il valore di uno e uno solo dei nodi dello heap sia stato arbitrariamente modificato. Valutare il costo computazionale.
  • Scrivere lo pseudocodice di una funzione che, dato un heap massimo di n elementi, ripristini la proprieta' di heap dopo che il valore di uno e uno solo dei nodi dello heap sia stato arbitrariamente eliminato. Valutare il costo computazionale.

Esercitazioni 9-10: venerdý 6 aprile 2018

  • Problemi inerentemente ricorsivi:
    • il problema della Torre di Hanoi [ D3, sez. 3 ];
    • il problema del massimo fattore primo [ S4 ];
    • il problema delle partizioni [ S3, sez. 1 ];
  • Introduzione agli array in C: vettori e puntatori [ D4, sez. 1 ];
  • Il problema del minimo di un vettore con asserzioni logiche [ D4, sez. 2.1 ];
  • Il problema del baricentro [ S1 ]

  • Esercizi consigliati: Dispensa D3 [sez. 3.3 ]
  • Esercizi consigliati: Dispensa D4 [sez. 1.3 ]

Lezioni 19-20: lunedý 9 aprile 2018

Il problema dell'ordinamento (4)

  • Algoritmi efficienti: heapsort (funzioni buildheap e heapsort: pseudocodice e costo computazionale)
  • Algoritmi di ordinamento lineari: counting sort (pseudocodice e costo computazionale); counting sort con dati satellite (pseudocodice e costo computazionale); bucket sort (descrizione generale dell'algoritmo).

Esercizi assegnati:

  • Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioŔ tale che A[i]>=A[parent(i)]), che mantiene il minimo nella radice.
  • Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare il costo computazionale.
  • Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n))

Lezioni 21-22: mercoledý 11 aprile 2018

  • Assegnazione e svolgimento alla lavagna di alcuni esercizi preparatori al primo esonero.

Esercitazioni 11-12: venerdý 13 aprile 2018

  • Esercizi su vettori e ricorsione in vista dell'esonero:
    • Ancora sul problema del baricentro: il caso di un vettore di positivi [ S1 ].
    • Il problema della verifica della combinazione del mastermind [ S3, sez. 2 ]: uso di vettori locali a una funzione.
    • Virtuosismi: funzione mergeRecVPC: merge ricorsiva da Veri Programmatori C [ L2 ]. Errata corrige alla Funzione in Fig.6 pag. 8.
    • Coefficienti binomiali con generazione delle righe del triangolo di Tartaglia [ D4, sez. 2.5 ].

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

Lunedý 16 aprile 2018

  • 14:00 - 17:00: Svolgimento della prova scritta relativa al primo esonero

Lezioni 23-24: lunedý 23 aprile 2018

Strutture dati fondamentali (1)

  • insiemi dinamici ed operazioni su di essi
  • implementazione di un insieme dinamico su un vettore non ordinato
  • implementazione di un insieme dinamico su un vettore ordinato
  • la struttura dati lista
  • operazioni elementari su liste: scorrimento, ricerca, inserimento in testa, eliminazione
  • la struttura dati lista doppiamente puntata
  • eliminazione di un elemento dalla lista doppiamente puntata
  • la lista circolare
  • la struttura dati coda
  • le operazioni enqueue e dequeue

Esercitazioni 13-14: venerdý 27 aprile 2018

  • Introduzione alla memoria allocata dinamicamente: stack e heap.
  • Funzioni di libreria malloc(int) e calloc(int, int).
  • Il tipo void *.
  • Differenza tra vettori a lunghezza variabile e vettori dinamici.
  • Introduzione ai record: definizioni di struct. [ D6, sez. 1 ]
  • Vettori bidimensionali: allocazione statica [ D5, sez. 2 ].
  • Allocazione di una matrice dinamica [ D5, sez. 3 ].

  • Esercizi consigliati: nessuno.

Lezioni 25-26: mercoledý 2 maggio 2018

Strutture dati fondamentali (2)

  • la struttura dati coda con prioritÓ
  • le operazioni enqueue e dequeue
  • la struttura dati pila
  • le operazioni push e pop
  • funzionamento della pila di sistema (system stack) per la gestione delle chiamate di funzione

Esercizi svolti in classe:

  • Simulare il comportamento di una coda mediante l'uso di pi¨ pile

Esercitazioni 15-16: venerdý 4 maggio 2018

  • Tipo di dato sequenza e sua definizione induttiva.
  • Rappresentazione in C delle sequenze: uso di struct 'ricorsive' [dispensa D6, sez. 3 ].
  • Costruttori e distruttori del tipo sequenza.
  • Prime funzioni C su liste: length, sumL [dispensa D6, sez. 3.1 ].
  • Attenzione alla memoria raggiungibile: side effects. L'esempio di twiceL [dispensa D6, sez. 3.2 ].

  • Esercizi consigliati: i pi¨ semplici di quelli alla fine della dispensa D6 .

Lezioni 27-28: lunedý 7 maggio 2018

Strutture dati fondamentali (3)

  • alberi (1)
    • definizione tramite la nozione di grafo
    • caratterizzazione degli alberi
    • alberi binari completi: relazione tra altezza e numero di nodi
    • memorizzazione degli alberi:
      • tramite record e puntatori
      • posizionale
      • tramite vettore dei padri

Esercizi assegnati:

  • dato un albero memorizzato tramite vettore dei padri, crearne una copia memorizzata tramite notazione posizionale. Calcolare il costo computazionale
  • dato un albero memorizzato tramite notazione posizionale, crearne una copia memorizzata tramite vettore dei padri. Calcolare il costo computazionale

Lezioni 29-30: mercoledý 9 maggio 2018

Dizionari (1)

  • definizione di dizionario e problematiche associate
  • tabelle ad indirizzamento diretto
  • tabelle hash
  • il problema delle collisioni
  • soluzione al problema delle collisioni tramite liste di trabocco
  • soluzione al problema delle collisioni tramite indirizzamento aperto
    • scansione lineare
    • scansione quadratica
    • hashing doppio

Esercitazioni 17-18: venerdý 11 maggio 2018

  • Inserzione di elementi in coda [dispensa D6, sez. 3.3 ]:
    • specifica con equazioni ricorsive,
    • versione iterativa addLastIt,
    • ricorsiva addLastRec,
    • con generazione di una nuova lista addLastFun .
  • Concatenazione di liste [dispensa D6, sez. 3.4 ]:
    • specifica con equazioni ricorsive,
    • versioni 'mista' append,
    • ricorsiva appendRec,
    • con generazione nuove liste appendFun .
  • Rovesciamento di liste [dispensa D6, sez. 3.5 ]:
    • specifica con equazioni ricorsive,
    • versione 'fun' inefficiente reverseFun,
    • iterativa reverseIt,
    • versione ricorsiva efficiente reverseFunEff .
  • Rovesciamento di Liste in place: versione ricorsiva reverseRec [dispensa D6, sez. 3.5 ].

  • Esercizi consigliati: reverse in place iterativa (virtuosismo) e altri esercizi tra di quelli alla fine della dispensa D6 .

Lezioni 31-32: lunedý 14 maggio 2018

Dizionari (2)

  • alberi binari di ricerca
    • definizione
    • algoritmo di ricerca e suo costo computazionale
    • algoritmi di ricerca del massimo, minimo, successore e predecessore e loro costo computazionale
    • algoritmo di inserimento e suo costo computazionale
    • algoritmo di cancellazione e suo costo computazionale

Esercizi assegnati:

  • Sia dato un albero binario di ricerca T memorizzato mediante record e puntatori e contenente chiavi intere. Si progetti un algoritmo il pi¨ efficiente possibile che trovi le due chiavi di T aventi distanza massima.
  • Sia dato un vettore V ordinato contenente n elementi distinti fra loro con n = 2**k -1 per un certo k. Si progetti una funzione ricorsiva il pi¨ efficiente possibile che crei un albero binario di ricerca completo contenente tutte le chiavi di V.
  • Sia dato un albero binario di ricerca T, memorizzato mediante record e puntatori e contenente chiavi intere, ed un valore intero a. Si progetti una funzione ricorsiva il pi¨ efficiente possibile che stampi tutte le chiavi di T che sono maggiori di a.

Lezioni 33-34: mercoledý 16 maggio 2018 (Prof.ssa Calamoneri)

Strutture dati fondamentali (4)

  • alberi (2)
    • visite di alberi: in-ordine, pre-ordine e post-ordine
      • pseudocodice ricorsivo
      • costo computazionale tramite equazione di ricorrenza

Esercizi svolti in classe:

  • Calcolare il numero di nodi di un albero binario
  • Calcolare l'altezza di un albero binario
  • Verificare se una data chiave k Ŕ presente in un albero binario
  • Contare i nodi di un albero binario che si trovano a livello k (il livello della radice Ŕ zero)
  • Realizzare una visita in pre-ordine senza ricorsione, mediante l'uso di una pila
  • Realizzare una visita per livelli mediante l'uso di una coda
  • Realizzare una visita ricorsiva su un albero memorizzato mediante vettore dei padri (pseudocodice e costo)

Esercitazioni 19-20: venerdý 18 maggio 2018

  • Discussione Homework 2: definizioni di tipi per il problema della Torre di Hanoi.
  • Eliminazione di elementi: removeFun e removeRec [dispensa D6, sez. 3.6 ].
  • Il problema della deallocazione di memoria dinamica: free() [dispensa D6, sez. 2.1 ].
  • Eliminazione di elementi: removeIt: attenzione a non perdere la testa (della lista)! [dispensa D6, sez. 3.6 ].
  • Esercizi da esoneri passati: il problema dello shuffle [Dispensa S6, sez. 1.5 ].

  • Esercizi consigliati: differenza tra liste, rimozione di duplicati [dispensa D6, sez. 3.6 ] e altri esercizi nella dispensa S6 sezione 1.

Lezioni 35-36: lunedý 21 maggio 2018

Dizionari (3)

  • alberi Red-Black
    • definizione
    • dimostrazione dell'altezza logaritmica
    • cenni ai meccanismi di ribilanciamento: cambi di colore e rotazioni

Svolgimento in classe del secondo esercizio assegnato il 18 maggio. Compilazione in classe del questionario OPIS

Lezioni 37-38: mercoledý 23 maggio 2018

Grafi (1)

  • definizione di grafo, grafo diretto, grafo pesato
  • definizione di passeggiata, cammino, cammino semplice
  • definizione di circuito e ciclo
  • relazione di raggiungibilitÓ e sue caratteristiche
  • definizione di componente connessa
  • definizione di sottografo, sottografo indotto, sottografo ricoprente
  • rappresentazioni in memoria
    • liste di adiacenza
    • matrice di adiacenza
    • matrice di incidenza
    • lista di archi
    • confronto della costo computazionale spaziale e temporale per alcune operazioni elementari

Esercitazioni 21-22: venerdý 25 maggio 2018

  • Introduzione agli alberi binari: definizione induttiva e rappresentazione in C [dispensa D7, sez. 1 e sez. 1.1 ].
  • Costruttori e distruttori: makeTree(int n, binTree L, binTree R) e isNotEmptyTree(binTree B, int r, binTree L, binTree *R)** [ *D7, sez. *1.1 ].
  • Funzioni base: numero di nodi, profonditÓ.
  • Il problema del bilanciamento [dispensa D7, sez. 1.4 ].
  • Fuori programma: macro espansioni con #define: la macro min(x,y)=x<y?x:y.

  • Esercizi consigliati: vedi dispensa D7, sez. finale di esercizi.

Lezioni 39-40: lunedý 28 maggio 2018

Grafi (2)

  • aspetti generali delle visite
    • differenza concettuale fra visita in ampiezza e visita in profonditÓ
    • implementazioni possibili: iterativa (tramite coda o pila) e ricorsiva (solo per visita in profonditÓ)
    • definizione di albero di visita
    • archi dell'albero e archi non dell'albero

  • visita in ampiezza (BFS)
    • pseudocodice della visita in ampiezza
    • esempio di funzionamento della visita in ampiezza
    • costo computazionale della visita in ampiezza
    • proprietÓ degli archi non dell'albero
    • proprieta' della distanza dalla radice

Esercizi assegnati:

  • Per ciascuno dei modi visti a lezione per memorizzare un grafo, scrivere le funzioni necessarie a crearne uno identico memorizzato in tutti gli altri modi
  • Modificare la visita in ampiezza in modo da calcolare e memorizzare, per ciascun nodo, la distanza dalla sorgente
  • Modificare la visita in ampiezza in modo da verificare se il grafo contiene cicli oppure no
  • Modificare la visita in ampiezza in modo da verificare se il grafo Ŕ connesso oppure no

Lezioni 41-42: mercoledý 30 maggio 2018

Grafi (3)

  • visita in profonditÓ (DFS)
    • pseudocodice della visita in profonditÓ
    • costo computazionale della visita in profonditÓ
    • proprietÓ degli archi non dell'albero
    • relazione fra lunghezza dei cammini e numero di archi del grafo

  • Algoritmo di Dijkstra (1)
    • la rete Internet Ŕ modellata come un grafo pesato sul quale individuare i cammini di costo minimo
    • cenni storici sull'evoluzione del sistema telefonico e della rete Internet
    • cenni sul funzionamento store-and-forward dei router
    • fenomeni che possono modificare i cammini minimi: caduta di linee o di router, congestione

Esercitazioni 23-24: venerdý 1 giugno 2018

  • Discussione Homework 3.
  • Alberi binari: relazione di uguaglianza e sotto-albero [dispensa D7, sez. 1.5 ].
  • Problemi con liste e alberi: il problema della frontiera [dispensa D7, sez. 1.2 ]. Versione efficiente che evita uso di append .
  • Esoneri passati: il problema di restituire la lista dei nodi al livello k: funzione livelloK [dispensa S6, sez. 2.2 ]

  • Esercizi consigliati: vedi dispensa D7, sez. finale di esercizi e dispensa S6.

Lezioni 43-44: lunedý 4 giugno 2018

Grafi (4)

  • Algoritmo di Dijkstra (2)
    • pseudocodice dell'algoritmo
    • esempio dettagliato di funzionamento su un grafo pesato
    • costo computazionale dell'algoritmo in funzione dell'implementazione della coda con prioritÓ
    • dimostrazione per induzione della correttezza dell'algoritmo

Lezioni 45-46: mercoledý 6 giugno 2018 (Prof.ssa Calamoneri)

Svolgimento in classe di esercizi preparatori al secondo esonero:

    • Calcolo dei cammini pi¨ corti da un nodo dato
    • Calcolo delle componenti connesse di un grafo
    • Verifica se un grafo memorizzato tramite matrice di adiacenza Ŕ Euleriano
    • Calcolo del grafo complemento e del quadrato di un grafo

Esercitazioni 25-26: venerdý 8 giugno 2018

  • Alberi binari: visita per livelli [dispensa D7, sez. 1.3 ].
  • Esercizi in preparazione dell'esonero:
    • divisione di liste: funzione dividi [dispensa S6, sez. 1.1 ]
    • somma precedenti [dispensa S6, sez. 1.2 ] e somma successiv [dispensa S2 ]
    • prefisso tra alberi [dispensa S6, sez. 2.4 ]

  • Esercizi consigliati: dispensa S6.

Lunedý 11 giugno 2018

  • 9:30 - 13:00: Svolgimento della prova scritta relativa al secondo esonero
Edit | Attach | Watch | Print version | History: r180 < r179 < r178 < r177 < r176 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r180 - 2018-06-07 - GiancarloBongiovanni






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback