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
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 una decina di "homework" settimanali su moodle (https://moodle1.ing.uniroma3.it/) consistenti nella scrittura di funzioni in linguaggio C. Ogni studente può rispondere ad un homework ripetute volte senza alcuna penalizzazione, finché la risposta non è corretta (moodle compila la risposta e ne verifica automaticamente la correttezza con opportuni dati di test). Il voto finale si ottiene tramite la media del voto della prova scritta e del voto della prova orale. Gli studenti che hanno svolto correttamente tutti gli homework aggiungono a questo voto un trentesimo. L'arrotondamento finale è per eccesso. Agli studenti che ottengono il voto di 31/30 verrà verbalizzata la lode. Una precondizione per poter fruire del punto in più degli homework è di verbalizzare l'esame nell'appello di febbraio dello stesso Anno Accademico in cui gli homework sono svolti. Gli studenti che hanno svolto correttamente solamente una porzione degli homework avranno un contributo sul voto finale ridotto in proporzione. Attenzione: nei periodi di emergenza COVID-19 l’esame di profitto sarà svolto secondo quanto previsto all’art.1 del Decreto Rettorale n°. 703 del 5 maggio 2020. La prova orale sarà determinante per l’attribuzione della valutazione finale. 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.
Mutuazione: 20810078 ALGORITMI E STRUTTURE DI DATI in Ingegneria informatica L-8 A - Z PATRIGNANI MAURIZIO
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 una decina di "homework" settimanali su moodle (https://moodle1.ing.uniroma3.it/) consistenti nella scrittura di funzioni in linguaggio C. Ogni studente può rispondere ad un homework ripetute volte senza alcuna penalizzazione, finché la risposta non è corretta (moodle compila la risposta e ne verifica automaticamente la correttezza con opportuni dati di test). Il voto finale si ottiene tramite la media del voto della prova scritta e del voto della prova orale. Gli studenti che hanno svolto correttamente tutti gli homework aggiungono a questo voto un trentesimo. L'arrotondamento finale è per eccesso. Agli studenti che ottengono il voto di 31/30 verrà verbalizzata la lode. Una precondizione per poter fruire del punto in più degli homework è di verbalizzare l'esame nell'appello di febbraio dello stesso Anno Accademico in cui gli homework sono svolti. Gli studenti che hanno svolto correttamente solamente una porzione degli homework avranno un contributo sul voto finale ridotto in proporzione. Attenzione: nei periodi di emergenza COVID-19 l’esame di profitto sarà svolto secondo quanto previsto all’art.1 del Decreto Rettorale n°. 703 del 5 maggio 2020. La prova orale sarà determinante per l’attribuzione della valutazione finale.