A.A. 2011/2012
Lezioni 1-2: lunedì 5 marzo 2012 Presentazione del corsoIntroduzione
- Concetti di algoritmo, di struttura dati, di efficienza; di complessita' computazionale.
- Modello RAM; misura di costo uniforme e logaritmico.
- Definizione e significato degli insiemi O, Ω e Θ.
- Esempi.
- Algebra della notazione asintotica.
- Valutazione della complessita' computazionale.
- 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
- Esempi di valutazione della complessita' computazionale.
- 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.
- Ciclo while, for e do..while
- Istruzioni break e continue
- Esercizio: determinare se un numero e' primo: is_prime.c
- 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
- 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
- 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
- Funzioni matematiche ricorsive
- Algoritmi ricorsivi
- Fattoriale;
- Numeri di Fibonacci;
- Ricerca sequenziale;
- Ricerca binaria.
- 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).
- Metodo di sostituzione.
- Metodo iterativo.
- Metodo dell'albero.
- Esempi di applicazione dei vari metodi.
- Metodo del teorema principale.
- Esempi di applicazione del metodo del teorema principale.
- Dimostrazione del teorema principale.
- 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.
- 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
- 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).
- 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).
- 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.
- 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.
- 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.
- Soluzione esercizio quadrato magico: quadrato_magico.c
- 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
- 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
- M[i,j] = 0 per i ! = j
- M[j,i] = 1 per i ! = j
- Il problema dell'ordinamento (2)
- algoritmi efficienti: merge sort
- 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.
- 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:
- Trovare il massimo di un vettore: max_vect_ric.c
- Somma degli elementi di un vettore: sum_vect_ric.c
- Trovare il numero di occorrenze di un valore in un vettore: conta_occorrenze_ric.c
- Verificare che un vettore sia palindromo: palindromo_ric.c
- 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.
- Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.
- Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.
- 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
- 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
- Soluzione: vip_quadratico.c
- Date due matrici quadrate A:axa e B:bxb t.c. a>b. Dire se B e' una sottomatrice di A.
- Il problema dell'ordinamento (3)
- algoritmi efficienti: quicksort (pseudocodice e complessità nei casi migliore, peggiore e medio)
- 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).
- 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
- Date due matrici quadrate A:axa e B:bxb t.c. a>b. Dire se B e' una sottomatrice di A: submatrix.c
- Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.
- Il problema dell'ordinamento (4)
- Counting sort e relativa analisi della complessità.
- Esercizi sulle equazioni di ricorrenza.
- 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).
- Definizione, dichiarazione, inizializzazione, assegnamento.
- Operatori & e *
- Allocazione dinamica della memoria: funzioni malloc e free
- Esempio di uso dei puntatori: es_puntatori.c
- Allocazione e deallocazione dinamica di vettori: alloc_dyn_vect.c
- Allocazione e deallocazione dinamica di matrici: alloc_dyn_matrix.c
- Il problema dell'ordinamento (5)
- algoritmi efficienti: heapsort (struttura dati heap, pseudocodice e complessità)
- 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à.
- 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
- 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
- Motivazioni
- Ottenere il passaggio per riferimento in C. Esempio: read_point.c
- Riflessioni sui vettori passati a funzioni
- 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
- 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.
- 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
- 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
- Definizione
- Dichiarazione struttura dati in C
- Definizione ricorsiva
- Code
- Inserimento: Enqueue
- Estrazione: Dequeue
- Implementazione: coda.c
- Pile
- Inserimento: Push
- Estrazione: Pop
- Implementazione: pila.c
- Stampa elementi: stampa_lista.c
- Somma elementi: sum_list.c
- 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
- 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
- memorizzazione di alberi
- 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.
- 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
- 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
- alberi binari di ricerca
- algoritmo di cancellazione e sua complessità
- la problematica del bilanciamento per la limitazione della complessità
- alberi red-black
- 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
- Generalità
- Definizione struttura dati in C
- Definizione ricorsiva di albero binario
- 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.).
- Esempio, inserimento ordinato ricorsivo in una lista: insert_sorted_list.c
- 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
- 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
- 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
- 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
- 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
This topic: Infogen > WebHome > DiarioDelleLezioni > LezioniDegliAnniAccademiciPrecedenti > AnnoAccademico2011-2012
Topic revision: r2 - 2018-02-17 - GiancarloBongiovanni
Copyright © 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