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. Per le esercitazioni e le prove d'esame del corso viene
utilizzato il linguaggio C.
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. Per le esercitazioni e le prove d'esame del corso viene
utilizzato 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.
Modalità Erogazione
Lezioni frontali in presenza. Homework da svolgere online durante la settimana consistenti in funzioni da implementare in linguaggio C.Modalità Frequenza
Le trasparenze delle lezioni sono a disposizione per chi dovesse perdere qualche lezione frontale.Modalità Valutazione
La valutazione è principalmente composta da un compito scritto di due ore (domande di teoria e una funzione da implementare in linguaggio C). Alla valutazione dello scritto può seguire una discussione orale dello scritto, anche con domande sul programma del corso. Gli homework eventualmente svolti durante l'erogazione del corso danno diritto a due punti in più sulla 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 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.
Modalità Erogazione
Lezioni frontali in presenza. Homework da svolgere online durante la settimana consistenti in funzioni da implementare in linguaggio C.Modalità Frequenza
Le trasparenze delle lezioni sono a disposizione per chi dovesse perdere qualche lezione frontale.Modalità Valutazione
La valutazione è principalmente composta da un compito scritto di due ore (domande di teoria e una funzione da implementare in linguaggio C). Alla valutazione dello scritto può seguire una discussione orale dello scritto, anche con domande sul programma del corso. Gli homework eventualmente svolti durante l'erogazione del corso danno diritto a due punti in più sulla valutazione finale.