Tags:
create new tag
view all tags

A.A. 2014/2015

Lezioni 1-2: lunedý 2 marzo 2015

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.
  • Pseudocodice

Esercitazioni 1-2: venerdý 6 marzo 2015

Introduzione al Linguaggio C.
Cenni alla struttura di un programma C. Funzione main().
Primo programma in C: Helloworld.
Semplici funzioni: somma e predecessore avendo un esecutore in grado solo di sommare 1.

Lezioni 3-4: lunedý 9 marzo 2015

Notazione asintotica (1)

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

Esercizi assegnati:

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

Lezioni 5-6: mercoledý 11 Marzo 2015

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

Esercitazioni 3-4: venerdý 13 marzo 2015

Ancora semplici funzioni in linguaggio C: divisione intera.
Cenni all'uso di asserzioni logiche: precondizioni, postcondizioni e invarianti nella progettazione di un programma iterativo.
Funzioni: stato locale e globale. Stack di attivazione delle funzioni.
Passaggio di parametri: passaggi per valore e per indirizzo.
Esempio: funzione scambia.
Cenni alla definizione per induzione di funzioni (somma) e relativa funzione ricorsiva in C.

Lezioni 7-8: lunedý 16 Marzo 2015

Ricorsione

  • funzioni matematiche ricorsive;
  • algoritmi ricorsivi: aspetti principali;
  • calcolo del fattoriale: pseudocodice ricorsivo;
  • 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, visualizzare i suoi valori al contrario (dall'ultimo al primo)
    • calcolare la somma di n numeri reali inseriti da tastiera (uno per ogni chiamata ricorsiva)

Lezioni 9-10: mercoledý 18 Marzo 2015

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 iterativo, tenendo conto che per tutte il caso base Ŕ T(1)=&Theta(1):
    • T(n)=2T(n/2)+Θ(n)
    • T(n)=3T(n/2)+Θ(n)
    • T(n)=2T(n/3)+Θ(n)

Esercizi assegnati:

  • Calcolare la soluzione delle seguenti equazioni di ricorrenza con quanti pi¨ metodi Ŕ possibile, tenendo conto che per tutte il caso base Ŕ T(1)=&Theta(1):
    • T(n)=3T(n/2)+Θ(n)
    • T(n)=3T(n/4)+Θ(n)
    • T(n)=2T(n/2)+Θ(n^2)
    • T(n)=T(n/3)+T(2/3n)+Θ(n)
    • T(n)=4T(n/2)+Θ(n)
    • T(n)=2T(n/2)+Θ(n^3)
    • T(n)=16T(n/4)+Θ(n^2)
    • T(n)=T(n-1)+Θ(n)
    • T(n)=3T(n/2)+Θ(n log n)

Esercitazioni 5-6: venerdý 20 marzo 2015

Esempio di funzione ricorsiva: calcolo dei numeri di Fibonacci.
Inefficienza della funzione ricorsiva che calcola i numeri di Fibonacci: albero delle chiamate ricorsive.
Programma iterativo che calcola i numeri di Fibonacci.
Programma ricorsivo efficiente. Cenni alla trasformazione sistematica di programmi iterativi in ricorsivi.
Problemi con soluzione inerentemente ricorsiva: il problema della torre di Hanoi.
Esercizi: predecessore con ricorsione, moltiplicazione egiziana.

Lezioni 11-12: lunedý 23 Marzo 2015

Soluzioni delle equazioni di ricorrenza (3)

Esercizio svolto in classe:

  • calcolare la soluzione della seguente equazione di ricorrenza con tutti e quattro i metodi, tenendo conto che per tutte il caso base Ŕ T(1)=&Theta(1):
    • T(n)=2T(n/2)+Θ(n)

Il problema dell'ordinamento (1)

  • Algoritmi semplici: insertion sort e selection sort, pseudocodici e complessitÓ nel caso migliore e peggiore.

Lezioni 13-14: mercoledý 25 Marzo 2015

Il problema dell'ordinamento (2)

  • Algoritmi semplici: bubble sort, pseudocodice e complessitÓ nel caso migliore e peggiore.
  • Teorema sulla limitazione inferiore per la complessitÓ di un algoritmo per confronti.
  • Algoritmi efficienti: merge sort, pseudocodice e complessitÓ

Esercizi assegnati:

  • Scrivere lo pseudocodice iterativo e ricorsivo, e per entrambe le versioni calcolare il costo computazionale, di algoritmi che risolvono i seguenti problemi:
    • dati in input due interi, n e k, calcolare n^k
    • calcolare la somma degli elementi di un vettore dato in input
    • verificare se un dato vettore di caratteri Ŕ palindromo
    • trovare il minimo di un vettore dato in input

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

Esercitazioni 7-8: venerdý 27 marzo 2015

Introduzione ai vettori in linguaggio C.
Vettori e puntatori.
Esempio: stampa di un vettore con indici, aritmetica dei puntatori e ricorsiva.
Vettori statici e dinamici. Introduzione all'allocazione dinamica.
Esercizio: calcolo del baricentro di un vettore.

Lezioni 15-16: lunedý 30 Marzo 2015

Il problema dell'ordinamento (3)

  • Algoritmi efficienti: quicksort, pseudocodice e complessitÓ nei casi migliore, peggiore e medio (con dimostrazione)

Esercizi assegnati:

  • Scrivere la funzione di fusione ricorsiva
  • Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono a1 a2 e b1 b2 (con l'implicita ipotesi che a1<a2 e b1<b2)
  • Risolvere l'equazione di ricorrenza del Merge sort con tutti i metodi studiati
  • 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))
  • 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 ed in cui sia giÓ ordinato da destra a sinistra.

Lezioni 17-18: mercoledý 1 Aprile 2015

Il problema dell'ordinamento (4)

  • Algoritmi efficienti: heapsort (struttura dati heap, heapify, buildheap, e heapsort: pseudocodice e costo computazionale)

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.
  • 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.

2-7 Aprile 2015: Vacanze di Pasqua

Lezioni 19-20: mercoledý 8 Aprile 2015

Il problema dell'ordinamento (5)

  • Algoritmi di ordinamento lineari: counting sort, bucket sort (pseudocodice e costo computazionale)

Esercizi svolti in classe:

  • Esempio 6.1 delle dispense.

Esercizi assegnati

  • 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.

Esercitazioni 9-10: venerdý 10 aprile 2015

Esercizi sui Vettori.
Crivello di Eratostene.
Calcolo dei Coefficienti Binomiali.
Uso di vettori per memorizzare i valori giÓ calcolati dalla funzione ricorsiva.

Lezioni 21-22: lunedý 13 Aprile 2015

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

Lezioni 23-24: mercoledý 15 Aprile 2015

Svolgimento in classe di esercizi preparatori al primo esonero

Esercitazioni 11-12: venerdý 17 aprile 2015

Esercizi in preparazione all'esonero.
Correzione esonero 2014: scomposizione in fattori primi.
Correzione esonero 2013: verificare se un array Ŕ contenuto in un altro.

20-24 Aprile 2015: Settimana di interruzione della didattica e Primo esonero

Esercitazioni 13-14: lunedý 27 aprile 2015

Introduzione alle matrici.
Programmazione top-down: gioco del forza4.

Lezioni 25-26: mercoledý 29 Aprile 2015

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
  • Discussione sull'esercizio n. 3 del primo esonero

Lezioni 27-28: lunedý 4 Maggio 2015

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 tramite vettore dei padri, restituirlo in output tramite notazione posizionale. Calcolare il costo computazionale
  • dato un albero tramite notazione posizionale, restituirlo in output tramite vettore dei padri. Calcolare il costo computazionale

Lezioni 29-30: mercoledý 6 Maggio 2015

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
  • Verificare se una data chiave k Ŕ presente in un albero binario
  • Calcolare l'altezza di 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

Esercitazioni 15-16: venerdý 8 maggio 2015

Ancora sulle matrici: allocazione statica e dinamica delle matrici.
Rappresentazione in memoria di una matrice.
Esercizi: verifica che una matrice di interi Ŕ un quadrato magico.

Lezioni 31-32: lunedý 11 maggio 2015

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

Lezioni 33-34: mercoledý 13 maggio 2015

Dizionari (2)

  • alberi binari di ricerca
    • definizione
    • algoritmo di ricerca e sua complessita'
    • algoritmi di ricerca del massimo, minimo, successore e predecessore e loro complessita'
    • algoritmo di inserimento e sua complessita'
    • algoritmo di cancellazione e sua complessita'

Esercitazioni 17-18: venerdý 15 maggio 2015

Strutture.
Liste o sequenze: definizione induttiva.
Rappresentazione in C di liste.
Primi programmi sulle liste: inserimento in testa, in coda.
Funzione reverse e reverse efficiente ricorsiva.
Funzione append.
Versioni che creano nuove liste e funzioni che modificano la lista di input.

Lezioni 35-36: lunedý 18 maggio 2015

Dizionari (3)

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

Grafi (1)

  • definizione di grafo, grafo diretto, grafo pesato
  • definizine di passeggiata, cammino, cammino semplice
  • definizine di circuito e ciclo
  • relazione di raggiungibilitÓ e sue caratteristiche
  • definizione di componente connessa
  • definizione di sottografo, sottografo indotto, sottografo ricoprente

Lezioni 37-38: mercoledý 20 maggio 2015

Grafi (2)

  • rappresentazioni in memoria
    • liste di adiacenza
    • matrice di adiacenza
    • matrice di incidenza
    • lista di archi
    • confronto della complessita' spaziale e temporale per alcune operazioni elementari

  • 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

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

Esercitazioni 19-20: venerdý 22 maggio 2015

Specifica di funzioni su liste tramite equazioni ricorsive.
Liste ordinate. Funzione merge su liste. Versione in-place e versione che genera una nuova lista.
Funzione reverse in-place.

Lezioni 39-40: lunedý 25 maggio 2015

Grafi (3)

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

  • 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 sul funzionamento store-and-forward dei router
    • fenomeni che possono modificare i cammini minimi: caduta di linee o di router, congestione

Lezioni 41-42: mercoledý 27 maggio 2015

Grafi (4)

  • Algoritmo di Dijkstra
    • 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

Esercitazioni 21-22: venerdý 29 maggio 2015

Definizione induttiva di alberi.
Rappresentazione in C di alberi binari.
Specifica di funzioni su alberi tramite equazioni ricorsive.
Prime funzioni su alberi: costruttori, distruttori, conteggio dei nodi, altezza.
Il problema del bilanciamento: versione naif e versione efficiente con un'unica scansione dell'albero.

Lezioni 43-44: mercoledý 3 giugno 2015

Esercizi svolti in classe:

  • Dato un albero binario, trovare il nodo che presenta la massima differenza fra i numeri di nodi del proprio sottoalbero sinistro e del proprio sottoalbero destro. Se vi sono pi¨ nodi con la massima differenza, restituirne uno fra quelli pi¨ vicini alla radice
  • Dato un vettore di n elementi considerato come un albero binario gestito mediante la notazione posizionale, riempirlo con i primi n valori dell'albero di Kalkin-Wilf (contati nell'albero per livelli e, in ciascun livello, da sinistra a destra)
  • Dati due alberi binari di ricerca, fonderli in un unico albero binario di ricerca
  • Dato un vettore contenente interi positivi e negativi, scrivere una funzione che sistemi tutti i valori negativi a sinistra di tutti i valori positivi

Esercitazioni 23-24: venerdý 5 giugno 2015

Esercitazione in vista dell'esame.
Compiti precedenti: somma successivi e somma precedenti in una lista.
Trucchi: usare i parametri per memorizzare valori in corso di computazione: stampa indentata di un albero.
Altri esercizi sugli alberi: relazione di uguaglianza e di sottoalbero.

-- GiancarloBongiovanni - 05 Apr 2016

Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2018-02-17 - GiancarloBongiovanni






 
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-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback