Tags:
create new tag
view all tags

A.A. 2011/2012

Lezioni 1-2: lunedý 5 marzo 2012

Presentazione del corso
Introduzione

  • Concetti di algoritmo, di struttura dati, di efficienza; di complessita' computazionale.
  • Modello RAM; misura di costo uniforme e logaritmico.

Lezioni 3-4: martedý 6 marzo 2012

Notazione asintotica (1)

  • Definizione e significato degli insiemi O, Ω e Θ.
  • Esempi.
  • Algebra della notazione asintotica.
  • Valutazione della complessita' computazionale.

Esercitazioni 1-2: Venerdý 9 marzo 2012

  • Discussione del programma di esempio: esempio1.c
  • Compilazione ed esecuzione di un programma C in Linux
  • Ripasso di nozioni elementari del linguaggio C:
    • Commenti
    • Inclusione di librerie predefinite
    • Direttive del preprocessore C: #include e #define
    • Dal file C al file eseguibile: preprocessore, compilazione, linking
    • La funzione main
    • Variabili: tipi, dichiarazione, assegnamento
    • Operatori aritmetici, di uguaglianza, relazionali e logici
    • Il comando if..else
    • Input e output standard in C: funzione printf e scanf

Lezioni 5-6: lunedi' 12 marzo 2012

Notazione asintotica (2)

  • Esempi di valutazione della complessita' computazionale.

Il problema della ricerca

  • Ricerca sequenziale in un vettore disordinato;
  • complessita' nel caso migliore, peggiore e medio.
  • Ricerca binaria in un vettore ordinato (vers. iterativa);
  • complessita' nel caso migliore, peggiore e medio.
  • Formulazione ricorsiva della ricerca binaria.

Esercitazioni 3-4: Martedý 13 marzo 2012

Iterazione:

  • Ciclo while, for e do..while
  • Istruzioni break e continue
  • Esercizio: determinare se un numero e' primo: is_prime.c
Vettori:
  • Allocazione statica
  • Indicizzazione e accesso agli elementi
  • Esercizio: trovare l'elemento di valore massimo: find_max_array.c
  • Esercizio: trovare la lunghezza del piu' lungo sottovettore composto da soli numeri pari: sottovettore_pari_lin.c

Esercizi assegnati:

Iterazione:

  • Scrivere un programma che prenda in input un intero n e:
    • Calcoli n!
    • Stampi un quadrato di * di dimensione nxn
    • Stampi i primi n numeri primi

Vettori:

  • Scrivere un programma che calcoli la somma degli elementi di un vettore
  • Scrivere un programma che trovi il minimo ed il massimo di un vettore
  • Modificare il programma sottovettore_pari_lin.c per fare in modo che stampi il sottovettore trovato
  • Scrivere un programma che dati due vettori A e B trovi la lunghezza del sottovettore comune pie' lungo

Lezioni 7-8: venerd' 16 marzo 2012

Ricorsione

  • Funzioni matematiche ricorsive
  • Algoritmi ricorsivi
    • Fattoriale;
    • Numeri di Fibonacci;
    • Ricerca sequenziale;
    • Ricerca binaria.
Esercizi assegnati:
  • Progettare degli algoritmi ricorsivi che risolvano i seguenti problemi ed esprimerli tramite pseudocodice:
    • sommare gli n elementi di un vettore di interi;
    • trovare il massimo fra gli n elementi di un vettore di interi;
    • dati due interi n e k, calcolare la potenza k-esima di n;
    • verificare se un vettore dato Ŕ palindromo;
    • trovare la somma del sottovettore di somma massima in un vettore di n interi (positivi e negativi).

Lezioni 9-10: lunedi' 19 marzo 2012

Soluzioni delle equazioni di ricorrenza (1)

  • Metodo di sostituzione.
  • Metodo iterativo.
  • Metodo dell'albero.
  • Esempi di applicazione dei vari metodi.

Lezioni 11-12: martedi' 20 marzo 2012

Soluzioni delle equazioni di ricorrenza (2)

  • Metodo del teorema principale.
  • Esempi di applicazione del metodo del teorema principale.
  • Dimostrazione del teorema principale.

Esercitazioni 5-6: Venerdý 23 marzo 2012

  • Soluzione esercizio: Trovare il sottovettore comune di lunghezza massima di due vettori. sottovettore_comune_max.c
  • Matrici di dati:
    • Dichiarazione, rappresentazione in memoria
    • Esercizio: calcolare la somma degli elementi con valore positivo di una matrice: sum_positive_matrix.c
  • Assegnazione Homework di prova.

Esercizi assegnati:

Matrici:

  • Scrivere un programma che allochi una matrice M di ROW righe e COL colonne e calcoli quanti elementi rispettano la relazione M[i,j] = i+j
  • Scrivere un programma che allochi una matrice quadrata M di dimensione SIZE x SIZE e:
    • Calcoli la somma degli elementi della diagonale primaria
    • Calcoli la somma degli elementi della diagonale secondaria
    • Verifichi se M Ŕ simmetrica, i.e. M[i,j] = M[j,i]
    • Calcoli la trasposta di M
    • Verifichi se M e' un quadrato magico, cioŔ se:
      • La somma di ogni riga e' pari a K
      • La somma di ogni colonna e' pari a K
      • La somma delle diagonali primaria e secondaria e' pari a K

Lezioni 13-14: lunedi' 26 marzo 2012

Esercizi svolti in aula:

  • Risolvere col metodo del teorema principale le seguenti equazioni di ricorrenza:
    • T(n)=2 T(n/2)+Θ(n); T(1)=Θ(1)
    • T(n)=2 T(n/3)+Θ(n); T(1)=Θ(1)
    • T(n)=3 T(n/2)+Θ(n); T(1)=Θ(1)
  • Risolverne una a scelta col metodo iterativo.
  • Progettare una soluzione iterativa ed una ricorsiva al seguente problema:
    • trovare la somma del sottovettore di somma massima in un vettore di n interi (positivi e negativi).

Esercizi assegnati:

  • Risolvere col metodo iterativo le restanti equazioni di ricorrenza sopra elencate.
  • Risolvere col metodo del teorema principale e col metodo iterativo le seguenti equazioni di ricorrenza:
    • T(n)=4 T(n/2)+Θ(n); T(1)=Θ(1)
    • T(n)=4 T(n/2)+Θ(n^2); T(1)=Θ(1)
    • T(n)=4 T(n/2)+Θ(n^3); T(1)=Θ(1)
  • Risolvere la seguente equazione di ricorrenza:
    • T(n)= T(n-1)+Θ(n); T(1)=Θ(1)
  • Valutare la complessita' delle soluzioni iterativa e ricorsiva al problema di trovare la somma del sottovettore di somma massima in un vettore di n interi (positivi e negativi).

Lezioni 15-16: martedý 27 marzo 2012

Il problema dell'ordinamento (1)

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

Esercizi assegnati:

  • scrivere una funzione che, dato un vettore, trovi il minimo e lo metta in prima posizione. Riscrivere il codice del selection sort in modo che chiami ripetutamente questa funzione.
  • scrivere lo pseudocodice di una funzione che determini se una sequenza arbitraria di n numeri contiene occorrenze ripetute dello stesso numero. Valutare la complessitÓ.
  • dati n+1 coefficienti a_0, ..., a_n ed un reale y, scrivere lo pseudocodice di una funzione che calcoli il valore del polinomio P(x)=a_0 + a_1x+ ... +a_n x^n nel punto y. Scrivere un'altra funzione che risolva lo stesso problema che sfrutti la regola di Horner: P(x)=(...(a_n x + a_{n-1})x+ ... +a_1)x+a_0. Calcolare la complessitÓ di entrambe le funzioni.

Tutoraggio 1-2: mercoledý 28 marzo 2012

  • Assistenza agli studenti per la compressione e l'invio delle soluzioni agli homework.
  • Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.

Esercitazioni 7-8: Venerdý 30 marzo 2012

Funzioni:

  • Motivazioni: modularitÓ, riusabilitÓ del codice
  • Dichiarazione
  • Variabili locali e valori di ritorno
  • Passaggio di parametri per valore
  • Esercizio: somma degli elementi di un vettore: sum_vect_iterative.c

Esercizi assegnati:

Scrivere un programma che allochi una matrice quadrata M:NxN rappresentante i rapporti di conoscenza di un gruppo di N persone, tale che:

  • contenga 2 sulla diagonale principale, M[i,i] = 2 per i = 0,..,N-1
  • contenga 1 in posizione i,j se i conosce j, M[i,j] = 1 se i conosce e j, j ! = i
Il programma deve verificare se esiste un VIP nel gruppo, cioŔ se esiste un indice i t.c. i e' conosciuto da tutti e non conosce nessuno. Formalmente:
  • M[i,j] = 0 per i ! = j
  • M[j,i] = 1 per i ! = j

Notare che il problema pu˛ essere risolto in O(n).

Lezioni 17-18: lunedý 2 aprile 2012

  • Il problema dell'ordinamento (2)
    • algoritmi efficienti: merge sort

Esercizi assegnati:

  • scrivere lo pseudocodice di una funzione che determini se una sequenza arbitraria di n numeri contiene occorrenze ripetute dello stesso numero. Valutare la complessitÓ, che dovrebbe essere Θ(n log n).
  • Nonostante il merge sort funzioni in tempo Θ(n log n), l'insertion sort Ŕ pi¨ veloce del merge sort per valori piccoli di n. Quindi ha senso usare insertion sort dentro il merge sort quando i sottoproblemi diventano sufficientemente piccoli. Si consideri una modifica del merge sort in cui il caso base diviene una porzione del vettore di lunghezza k, con k che deve essere determinato, la quale viene ordinata usando insertion sort. Le porzioni ordinate vengono poi combinate usando il meccanismo standard di fusione. Determinare il massimo valore di k come funzione di n per cui l'algoritmo modificato ha lo stesso tempo di esecuzione asintotico del merge sort.

Esercitazioni 9-10: Martedý 3 aprile 2012

  • Prototipi di funzione: motivazioni e sintassi
  • Funzioni ricorsive:
    • Scrittura di una funzione ricorsiva: caso base e passo ricorsivo
    • Schema "generale" funzione ricorsiva
  • Esercizi sulle funzioni ricorsive:

Esercizi assegnati:

  • Dato un vettore di interi ed un intero k, verificare che la somma degli elementi del vettore sia pari a k.
  • Dato un vettore, verificare se esiste un elemento che si ripeta pi¨ di una volta.

Tutoraggio 3-4: mercoledý 4 aprile 2012

  • Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.

Venerdý 6 aprile - martedý 10 aprile 2012: Vacanze di Pasqua

Tutoraggio 5-6: mercoledý 11 aprile 2012

  • Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.

Esercitazioni 11-12: Venerdý 13 aprile 2012

Esercizi sulla ricorsione:

  • Dato un vettore di interi ed un intero k, verificare che la somma degli elementi del vettore sia pari a k: check_sum_vect_ric.c
  • Dato un vettore, verificare se esiste un elemento che si ripeta pi¨ di una volta: repeated_elem.c

Esercizio sulle matrici:

  • Data una matrice quadrata M:NxN rappresentante i rapporti di conoscenza di un gruppo di N persone, tale che:
    contenga 2 sulla diagonale principale, M[i,i] = 2 per i = 0,..,N-1
    contenga 1 in posizione i,j se i conosce j, M[i,j] = 1 se i conosce e j, j ! = i
    Il programma deve verificare se esiste un VIP nel gruppo, cioŔ se esiste un indice i t.c. i e' conosciuto da tutti e non conosce nessuno. Formalmente:
    • M[i,j] = 0 per i ! = j
    • M[j,i] = 1 per i ! = j

Assegnazione homework 2.

Esercizi assegnati:

  • Date due matrici quadrate A:axa e B:bxb t.c. a>b. Dire se B e' una sottomatrice di A.

Lezioni 19-20: lunedý 16 aprile 2012

  • Il problema dell'ordinamento (3)
    • algoritmi efficienti: quicksort (pseudocodice e complessitÓ nei casi migliore, peggiore e medio)

Esercizi assegnati:

  • Determinare la complessitÓ del Quicksort se il vettore dato in input contiene n elementi uguali e se Ŕ giÓ ordinato in senso decrescente (nell'ipotesi che non contenga elementi uguali).

Esercitazioni 13-14: Martedý 17 aprile 2012

Esercizi sulla ricorsione:

  • Dati due vettori A e B di dimensione n verificare che siano uguali: equal_vect_ric.c
  • Dato un vettore A di dimensione n ed un vettore B di dimensione m, verificare che B sia sottovettore di A: subvect_ric.c

Esercizio sulle matrici:

  • Date due matrici quadrate A:axa e B:bxb t.c. a>b. Dire se B e' una sottomatrice di A: submatrix.c

Tutoraggio 7-8: mercoledý 18 aprile 2012

  • Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.

Lezioni 21-22: venerdý 20 aprile 2012

  • Il problema dell'ordinamento (4)
    • Counting sort e relativa analisi della complessitÓ.
  • Esercizi sulle equazioni di ricorrenza.

Esercizi assegnati:

  • Scrivere lo pseudocodice di una funzione che determini se una data una sequenza arbitraria di n numeri compresi tar 1 e k, con k=O(n), contiene occorrenze ripetute dello stesso numero. Valutare la complessitÓ, che dovrebbe essere O(n).

Lunedý 23 aprile - venerd' 27 aprile 2012: Sospensione della didattica per lo svolgimento delle prove in itinere.

Esercitazioni 15-16: Venerdý 4 Maggio 2012

Puntatori:

  • Definizione, dichiarazione, inizializzazione, assegnamento.
  • Operatori & e *
  • Allocazione dinamica della memoria: funzioni malloc e free
  • Esempio di uso dei puntatori: es_puntatori.c

Vettori e matrici:

Lezioni 23-24: lunedý 7 maggio 2012

  • Il problema dell'ordinamento (5)
    • algoritmi efficienti: heapsort (struttura dati heap, pseudocodice e complessitÓ)

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 la complessitÓ.

Lezioni 25-26: martedý 8 maggio 2012

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
  • realizzazione della struttura dati lista tramite vettore

Esercitazioni 17-18: Venerdý 11 Maggio 2012

Strutture dati:

  • Definizione, dichiarazione.
  • Accesso ai campi di strutture allocate staticamente
  • Confronti tra strutture
  • Definizione di alias per i tipi, istruzione typedef
  • Typedef e strutture
  • Allocazione dinamica di strutture
  • Accesso ai campi di strutture allocate dinamicamente

Passaggio di parametri per riferimento a funzioni in C:

  • Motivazioni
  • Ottenere il passaggio per riferimento in C. Esempio: read_point.c
  • Riflessioni sui vettori passati a funzioni

Lezioni 27-28: lunedý 14 maggio 2012

Strutture dati fondamentali (2)

  • la struttura dati lista doppiamente puntata
  • eliminazione di un elemento dalla lista doppiamente puntata
  • cancellazione logica e cancellazione fisica
  • la lista circolare
  • la struttura dati coda
  • le operazioni enqueue e dequeue

Esercizi assegnati:

  • Scrivere lo pseudocodice, in versione iterativa, dell'eliminazione di un elemento (di cui si fornisce il puntatore) da una lista semplice.
  • Scrivere lo pseudocodice, in versione ricorsiva, dell'eliminazione di un elemento (di cui si fornisce il puntatore) da una lista semplice.
  • Scrivere lo pseudocodice, in versione iterativa, di una funzione che restituisce il puntatore al massimo elemento contenuto in una lista semplice.
  • Scrivere lo pseudocodice, in versione ricorsiva, di una funzione che restituisce il puntatore al massimo elemento contenuto in una lista semplice.

Lezioni 29-30: martedý 15 maggio 2012

Strutture dati fondamentali (3)

  • la struttura dati pila
  • le operazioni push e pop
  • la struttura dati albero
    • definizione come grafo connesso e aciclico
    • alberi radicati, alberi ordinati ed alberi binari
    • limitazioni sul numero di nodi, numero di foglie ed altezza negli alberi binari

Esercizi assegnati:

  • Scrivere lo pseudocodice, in versione iterativa, di una funzione che restituisce il puntatore al predecessore di un elemento (di cui si conosce il puntatore) contenuto in una lista semplice nella quale tutti gli elementi sono diversi fra loro. Nota: il predecessore di un elemento Ŕ quello che lo precederebbe se gli elementi fossero ordinati.
  • Scrivere lo pseudocodice di una funzione che, dato un puntatore che indica la testa di una lista contenente chiavi intere, la scomponga in due liste, una contenente gli elementi con chiave pari e una contenente gli elementi con chiave dispari
  • Scrivere lo pseudocodice di una funzione che, dati due puntatori a due liste contenenti ciascuna chiavi intere ordinate, produca una terza lista contenente tutte le chiavi ordinate

Esercitazioni 19-20: Venerdý 18 Maggio 2012

Liste:

  • Definizione
  • Dichiarazione struttura dati in C
  • Definizione ricorsiva
  • Code
    • Inserimento: Enqueue
    • Estrazione: Dequeue
    • Implementazione: coda.c
  • Pile
    • Inserimento: Push
    • Estrazione: Pop
    • Implementazione: pila.c

Esercizi sulle liste:

Esercitazioni 21-22: Lunedý 21 Maggio 2012

Esercizi sulle liste:

  • Restituire il puntatore all'elemento con valore massimo: max_list.c
  • Scomporre una lista L in due liste, L_p ed L_d, contenenti rispettivamenti gli elementi di L pari e dipsari (senza creare copie degli elementi): scomponi_lista.c
  • Data una lista p ed un elemento x di p, trovare il predecessore di x in p: predecessore.c

Lezioni 31-32: martedý 22 maggio 2012

Strutture dati fondamentali (4)

  • la struttura dati albero
    • memorizzazione di alberi
      • rappresentazione posizionale
      • memorizzazione tramite record e puntatori
      • vettore dei padri
      • raffronto delle strutture in termini di spazio e di complessitÓ delle operazioni di ricerca del padre di un nodo e di calcolo del numero dei figli di un nodo
    • visita di alberi: pre-ordine, in-ordine e post-ordine
    • complessitÓ delle visite tramite equazione di ricorrenza
    • Esercizio: calcolo del numero di nodi contenuti in un albero binario
    • Esercizio: calcolo dell'altezza di un albero binario

Esercizi assegnati:

  • Scivere lo pseudocodice di una funzione che, dato il puntatore ad un albero binario, calcoli la somma dei valori delle chiavi contenute nell'albero
  • Scivere lo pseudocodice di una funzione che, dato il puntatore ad un albero binario, stampi la sua rappresentazione parentetica
  • Scivere lo pseudocodice di una funzione che, dato il puntatore ad un albero binario, calcoli il numero dei nodi a distanza k dalla radice. La complessitÓ dovrebbe essere dell'ordine del numero dei nodi a distanza minore o uguale di k dalla radice.

Lezioni 33-34: venerdý 25 maggio 2012

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
    • analisi delle prestazioni nel caso medio

Lezioni 35-36: lunedý 28 maggio 2012

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'
  • Esercizio svolto in classe: fusione di due liste ordinate

Lezioni 37-38: martedý 29 maggio 2012

Dizionari (3)

  • alberi binari di ricerca
    • algoritmo di cancellazione e sua complessitÓ
    • la problematica del bilanciamento per la limitazione della complessitÓ
    • alberi red-black

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

Esercitazioni 23-24: Venerdý 1 Giugno 2012

Alberi binari:

  • GeneralitÓ
  • Definizione struttura dati in C
  • Definizione ricorsiva di albero binario

Progettazione di funzioni ricorsive su strutture dati dinamiche:

  • Funzioni che non modificano la struttura dati (es. somma chiavi degli elementi di una lista, altezza di un albero, ...).
  • Funzioni che modificano la struttura dati (inserimento, cancellazione, ecc.).

Esercizi sugli alberi binari:

  • Inserimento su albero binario di ricerca
  • Rapresentazione parentetica di un albero
  • Somma delle chiavi del cammino radice-foglia avente somma delle chiavi massima
  • Codice degli esercizi sopra elencati: insert_bin_tree.c

Lezioni 39-40: lunedý 4 giugno 2012

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

  • visita in ampiezza (BFS)
    • definizione di albero ricoprente
    • pseudocodice della visita in ampiezza e sua complessitÓ
    • proprietÓ degli archi non dell'albero
    • proprieta' della distanza dalla radice

Lezioni 41-42: martedý 5 giugno 2012

Grafi (3)

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

  • Esercizio svolto in classe: conteggio del numero di nodi a distanza k dalla radice in un albero binario

Esercitazioni 25-26: Mercoledý 6 Giugno 2012

Esercizi su liste:

  • Data una lista ed un intero x, rimuovere dalla lista gli elementi con chiave < x
  • Data una lista, rimuovere gli elementi in posizione pari
  • Soluzioni esercizi precedenti: remove_list.c

Esercizi su alberi binari:

  • Dato un albero, restituire l'albero opposto (albero opposto = albero in cui per ogni nodo il figlio sx e quello dx sono scambiati)
  • Dato un albero e due interi a e b, con a < b, stampare tutte le chiavi comprese nell'intervallo [a,b]
  • Soluzioni esercizi precedenti: es_alberi.c

-- GiancarloBongiovanni - 05 Apr 2016

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 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