Fornire conoscenze sui metodi di rappresentazione delle principali strutture di dati (pile, code, liste, alberi, grafi) e sugli algoritmi fondamentali per la loro gestione. Esporre gli strumenti formali per la valutazione rigorosa della complessità computazionale degli algoritmi e dei problemi. E' un obiettivo del corso anche l'acquisizione di familiarità con i principali approcci algoritmici (divide et impera, greedy, incrementale) e con i paradigmi di programmazione ricorsivo e iterativo. Durante il corso gli studenti vengono introdotti al linguaggio C
Curriculum
Canali
scheda docente materiale didattico
Definizione di problema computazionale, algoritmo, struttura di dati.
Random Access Machine e pseudocodice.
Studio asintotico delle funzioni (notazioni O-grande, Omega e Theta).
Complessità asintotica degli algoritmi e dei problemi.
Complessità ammortizzata.
Analisi del caso migliore, medio, peggiore.
Ricorsione ed equazioni di ricorrenza.
Teoremi per l'analisi di funzioni ricorsive.
PARTE 2: Tipi astratti di dato.
Tipi astratti di dato e loro rappresentazioni.
Esempi già noti: insiemi, pile, code, liste, ecc.
Gestione telescopica di strutture di dati dinamiche.
Alberi: Alberi binari; Alberi di grado arbitrario; Visite di alberi; Alberi binari di ricerca; Alberi rosso-neri.
Tabelle hash.
Grafi: Rappresentazione con matrici e liste di adiacenza. Visite in ampiezza e profondità. Grafi e connettività. Componenti connesse. Cammini minimi su grafi.
PARTE 3: Paradigmi algoritmici.
Algoritmi greedy (esempio: Ordinamento tramite selection sort).
Algoritmi iterativi (esempio: Ordinamento tramite insertion sort).
Algoritmi divide et impera (esempi: Ordinamento tramite merge-sort, ordinamento tramite quick-sort).
PARTE 4: Il corso contiene richiami delle seguenti nozioni di Linguaggio C
Programmazione imperativa.
Tipi di dato elementari.
Funzioni.
Puntatori e Array.
Stringhe.
Gestione della memoria: Heap e Stack.
Gestione di progetti in C: prototipi e implementazioni.
Ricorsione e Memoria.
Puntatori e Record.
Gestione dinamica della memoria.
Gestione di File.
INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI
(TERZA EDIZIONE) MCGRAW-HILL, 2010
B.W.KERNIGHAM, D.M.RITCHIE
IL LINGUAGGIO C, PRINCIPI DI PROGRAMMAZIONE E MANUALE DI RIFERIMENTO (SECONDA EDIZIONE)
PEARSON EDUCATION ITALIA, 2004
Programma
PARTE 1: Generalità e strumenti.Definizione di problema computazionale, algoritmo, struttura di dati.
Random Access Machine e pseudocodice.
Studio asintotico delle funzioni (notazioni O-grande, Omega e Theta).
Complessità asintotica degli algoritmi e dei problemi.
Complessità ammortizzata.
Analisi del caso migliore, medio, peggiore.
Ricorsione ed equazioni di ricorrenza.
Teoremi per l'analisi di funzioni ricorsive.
PARTE 2: Tipi astratti di dato.
Tipi astratti di dato e loro rappresentazioni.
Esempi già noti: insiemi, pile, code, liste, ecc.
Gestione telescopica di strutture di dati dinamiche.
Alberi: Alberi binari; Alberi di grado arbitrario; Visite di alberi; Alberi binari di ricerca; Alberi rosso-neri.
Tabelle hash.
Grafi: Rappresentazione con matrici e liste di adiacenza. Visite in ampiezza e profondità. Grafi e connettività. Componenti connesse. Cammini minimi su grafi.
PARTE 3: Paradigmi algoritmici.
Algoritmi greedy (esempio: Ordinamento tramite selection sort).
Algoritmi iterativi (esempio: Ordinamento tramite insertion sort).
Algoritmi divide et impera (esempi: Ordinamento tramite merge-sort, ordinamento tramite quick-sort).
PARTE 4: Il corso contiene richiami delle seguenti nozioni di Linguaggio C
Programmazione imperativa.
Tipi di dato elementari.
Funzioni.
Puntatori e Array.
Stringhe.
Gestione della memoria: Heap e Stack.
Gestione di progetti in C: prototipi e implementazioni.
Ricorsione e Memoria.
Puntatori e Record.
Gestione dinamica della memoria.
Gestione di File.
Testi Adottati
T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEININTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI
(TERZA EDIZIONE) MCGRAW-HILL, 2010
B.W.KERNIGHAM, D.M.RITCHIE
IL LINGUAGGIO C, PRINCIPI DI PROGRAMMAZIONE E MANUALE DI RIFERIMENTO (SECONDA EDIZIONE)
PEARSON EDUCATION ITALIA, 2004
Modalità Valutazione
Prova scritta Prova oraleCanali
scheda docente materiale didattico
Definizione di problema computazionale, algoritmo, struttura di dati.
Random Access Machine e pseudocodice.
Studio asintotico delle funzioni (notazioni O-grande, Omega e Theta).
Complessità asintotica degli algoritmi e dei problemi.
Complessità ammortizzata.
Analisi del caso migliore, medio, peggiore.
Ricorsione ed equazioni di ricorrenza.
Teoremi per l'analisi di funzioni ricorsive.
PARTE 2: Tipi astratti di dato.
Tipi astratti di dato e loro rappresentazioni.
Esempi già noti: insiemi, pile, code, liste, ecc.
Gestione telescopica di strutture di dati dinamiche.
Alberi: Alberi binari; Alberi di grado arbitrario; Visite di alberi; Alberi binari di ricerca; Alberi rosso-neri.
Tabelle hash.
Grafi: Rappresentazione con matrici e liste di adiacenza. Visite in ampiezza e profondità. Grafi e connettività. Componenti connesse. Cammini minimi su grafi.
PARTE 3: Paradigmi algoritmici.
Algoritmi greedy (esempio: Ordinamento tramite selection sort).
Algoritmi iterativi (esempio: Ordinamento tramite insertion sort).
Algoritmi divide et impera (esempi: Ordinamento tramite merge-sort, ordinamento tramite quick-sort).
PARTE 4: Il corso contiene richiami delle seguenti nozioni di Linguaggio C
Programmazione imperativa.
Tipi di dato elementari.
Funzioni.
Puntatori e Array.
Stringhe.
Gestione della memoria: Heap e Stack.
Gestione di progetti in C: prototipi e implementazioni.
Ricorsione e Memoria.
Puntatori e Record.
Gestione dinamica della memoria.
Gestione di File.
INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI
(TERZA EDIZIONE) MCGRAW-HILL, 2010
B.W.KERNIGHAM, D.M.RITCHIE
IL LINGUAGGIO C, PRINCIPI DI PROGRAMMAZIONE E MANUALE DI RIFERIMENTO (SECONDA EDIZIONE)
PEARSON EDUCATION ITALIA, 2004
Programma
PARTE 1: Generalità e strumenti.Definizione di problema computazionale, algoritmo, struttura di dati.
Random Access Machine e pseudocodice.
Studio asintotico delle funzioni (notazioni O-grande, Omega e Theta).
Complessità asintotica degli algoritmi e dei problemi.
Complessità ammortizzata.
Analisi del caso migliore, medio, peggiore.
Ricorsione ed equazioni di ricorrenza.
Teoremi per l'analisi di funzioni ricorsive.
PARTE 2: Tipi astratti di dato.
Tipi astratti di dato e loro rappresentazioni.
Esempi già noti: insiemi, pile, code, liste, ecc.
Gestione telescopica di strutture di dati dinamiche.
Alberi: Alberi binari; Alberi di grado arbitrario; Visite di alberi; Alberi binari di ricerca; Alberi rosso-neri.
Tabelle hash.
Grafi: Rappresentazione con matrici e liste di adiacenza. Visite in ampiezza e profondità. Grafi e connettività. Componenti connesse. Cammini minimi su grafi.
PARTE 3: Paradigmi algoritmici.
Algoritmi greedy (esempio: Ordinamento tramite selection sort).
Algoritmi iterativi (esempio: Ordinamento tramite insertion sort).
Algoritmi divide et impera (esempi: Ordinamento tramite merge-sort, ordinamento tramite quick-sort).
PARTE 4: Il corso contiene richiami delle seguenti nozioni di Linguaggio C
Programmazione imperativa.
Tipi di dato elementari.
Funzioni.
Puntatori e Array.
Stringhe.
Gestione della memoria: Heap e Stack.
Gestione di progetti in C: prototipi e implementazioni.
Ricorsione e Memoria.
Puntatori e Record.
Gestione dinamica della memoria.
Gestione di File.
Testi Adottati
T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEININTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI
(TERZA EDIZIONE) MCGRAW-HILL, 2010
B.W.KERNIGHAM, D.M.RITCHIE
IL LINGUAGGIO C, PRINCIPI DI PROGRAMMAZIONE E MANUALE DI RIFERIMENTO (SECONDA EDIZIONE)
PEARSON EDUCATION ITALIA, 2004
Modalità Valutazione
Prova scritta Prova orale