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. Il linguaggio di programmazione utilizzato nel corso è il linguaggio C.
Curriculum
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.
Per scaricare le slides sono neccessarie le credenziali di ateneo.
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.
Testi Adottati
Trasparenze fornite dal docente e scaricabili via via dal sito del corso: https://moodle1.ing.uniroma3.it/Per scaricare le slides sono neccessarie le credenziali di ateneo.
Bibliografia Di Riferimento
I seguenti testi sono consigliati esclusivamente agli studenti che non possono seguire le lezioni: T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEIN 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 Qualsiasi altro testo introduttivo al linguaggio C potrebbe essere equivalente a questo qui sopra.Modalità Erogazione
Lezioni con proiezione di slides. Esercitazioni in classe con scrittura da parte del docente (con suggerimenti degli studenti) di codice in lingaggio C, compilazione, linking ed esecuzione di programmi.Modalità Frequenza
Le trasparenze del corso sono abbondantemente commentate allo scopo di rendere possibile la preparazione all'esame anche agli studenti non frequentanti.Modalità Valutazione
Prova scritta: ha una durata di 2 ore e consiste in un programma in pseudocodice di cui lo studente deve eseguire un'analisi della complessità asintotica in termini di O-grande, Omega e Theta e di un problema da risolvere tramite una funzione in linguaggio C (ed eventuali funzioni di appoggio). Prova orale: consiste in un colloquio della durata di mezzora al massimo svolto in una data concordata con il docente. L'orale si apre con la discussione della valutazione del compito scritto (che lo studente conosce in anticipo) e contempla sia domande di teoria sia (eventualmente) la richiesta di scrivere del codice in linguaggio C o pseudocodifica. Valutazione in itinere: durante l'erogazione del corso gli studenti verranno invitati a risolvere degli "homework" su moodle (https://moodle1.ing.uniroma3.it/) consistenti nella scrittura di funzioni in linguaggio C. Moodle compila la risposta e ne verifica automaticamente la correttezza con opportuni dati di test. Gli studenti che hanno svolto gli homework hanno guadagnato una porzione del voto finale. Il voto finale viene completato con una prova scritta e una prova orale.
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.
Per scaricare le slides sono neccessarie le credenziali di ateneo.
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.
Testi Adottati
Trasparenze fornite dal docente e scaricabili via via dal sito del corso: https://moodle1.ing.uniroma3.it/Per scaricare le slides sono neccessarie le credenziali di ateneo.
Bibliografia Di Riferimento
I seguenti testi sono consigliati esclusivamente agli studenti che non possono seguire le lezioni: T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEIN 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 Qualsiasi altro testo introduttivo al linguaggio C potrebbe essere equivalente a questo qui sopra.Modalità Erogazione
Lezioni con proiezione di slides. Esercitazioni in classe con scrittura da parte del docente (con suggerimenti degli studenti) di codice in lingaggio C, compilazione, linking ed esecuzione di programmi.Modalità Frequenza
Le trasparenze del corso sono abbondantemente commentate allo scopo di rendere possibile la preparazione all'esame anche agli studenti non frequentanti.Modalità Valutazione
Prova scritta: ha una durata di 2 ore e consiste in un programma in pseudocodice di cui lo studente deve eseguire un'analisi della complessità asintotica in termini di O-grande, Omega e Theta e di un problema da risolvere tramite una funzione in linguaggio C (ed eventuali funzioni di appoggio). Prova orale: consiste in un colloquio della durata di mezzora al massimo svolto in una data concordata con il docente. L'orale si apre con la discussione della valutazione del compito scritto (che lo studente conosce in anticipo) e contempla sia domande di teoria sia (eventualmente) la richiesta di scrivere del codice in linguaggio C o pseudocodifica. Valutazione in itinere: durante l'erogazione del corso gli studenti verranno invitati a risolvere degli "homework" su moodle (https://moodle1.ing.uniroma3.it/) consistenti nella scrittura di funzioni in linguaggio C. Moodle compila la risposta e ne verifica automaticamente la correttezza con opportuni dati di test. Gli studenti che hanno svolto gli homework hanno guadagnato una porzione del voto finale. Il voto finale viene completato con una prova scritta e una prova orale.