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 2012Esercizi 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.
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
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 PasquaTutoraggio 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:
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:
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:
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, ...).
Esempio, massimo degli elementi in una lista: max_list_int.c
Funzioni che modificano la struttura dati (inserimento, cancellazione, ecc.).