Acquisire una buona conoscenza nella progettazione di algoritmi per la risoluzione di problemi e nella codifica di algoritmi con un linguaggio di programmazione (linguaggio C). Introdurre lo studente ad alcuni dei concetti fondamentali della matematica discreta (cenni sulla teoria dei grafi) ed in particolare ai primi elementi di ottimizzazione discreta (algoritmi di ottimizzazione su grafi, visita di grafi, cammini minimi, alberi ricoprenti).
Curriculum
scheda docente
materiale didattico
Introduzione alle caratteristiche del calcolatore ed al rapporto programmatore/ esecutore; compiti ed abilità del programmatore; principali caratteristiche ed abilità dell’esecutore, operazioni di base (logiche, aritmetiche e di confronto). Modelli di macchina calcolatrice: cenni sul modello di Von Neumann e sulla macchina di Turing.
Linguaggi di programmazione: linguaggi imperativi e dichiarativi. Istruzioni fondamentali di un linguaggio di programmazione procedurale generico. Algoritmi e programmi; diagrammi di flusso. Regole della programmazione strutturata, cenni sul teorema di Jacopini-Böhm; approccio top-down alla soluzione di un problema.
2. Il linguaggio C
Organizzazione della memoria di un calcolatore, indirizzi, parole, puntatori. Codifica binaria. Tipi di dato, strutture dati (array, matrici, pile, code, code di priorità, liste, alberi, grafi). Linguaggio macchina, linguaggi di alto livello; compilatori ed interpreti, compilazione ed esecuzione di un programma C in ambiente UNIX/Linux. Il linguaggio C: scopi e principali caratteristiche.
La struttura di un programma C, l’inclusione degli header, dichiarazione delle variabili; le librerie. Tipi di dato elementari in linguaggio C: interi, floating point, double, char. Operatori aritmetici, valutazione di espressioni logiche e connettori logici. Puntatori; aritmetica sui puntatori. Array e matrici e loro rappresentazione in memoria. Strutture dati complesse: liste, alberi, grafi; l’istruzione “struct”. Operatore di assegnazione, operatori aritmetici in C in forma estesa e compatta.
Strutture di controllo: “if ... else ...”, “while ...”, “do ... while”, “for ...”.
Funzioni: funzioni di libreria e funzioni definite dall’utente. Passaggio di parametri per valore e per indirizzo alle funzioni. Funzioni ricorsive. Funzioni di input/output: “printf”, “scanf”, “fprintf”, “fscanf”; funzioni per la gestione della memoria: “malloc”, “free”, “sizeof”; gestione di liste di record collegati tramite puntatori.
3. Algoritmi di ordinamento
Algoritmi di ordinamento elementari: Insertion sort, Selection sort, Bubble sort; l’approccio “divide et impera”, l’algoritmo Quick sort. Strutture di tipo LIFO (Last In First Out), pile; strutture di tipo FIFO (First In First Out), code; code di priorità, gli heap. Algoritmi ottimi per l’ordinamento: Heap sort, Merge sort.
Complessità di un algoritmo nel caso peggiore, la notazione “O grande”, analisi della complessità degli algoritmi di ordinamento.
4. Algoritmi su strutture dati di lista, grafo e albero
Definizioni principali: grafo, grafo orientato; sottografo, sottografo indotto; cammino, cammino semplice, grafo connesso, grafo fortemente connesso, grafo completo, clique, ciclo, grafo aciclico; alberi, foreste, spanning tree di un grafo. Strutture dati per la rappresentazione di grafi mediante un calcolatore: liste di adiacenza e matrici di adiacenza. Algoritmi di visita di un grafo: visita in ampiezza (BFS), visita in profondità (DFS), ordinamento topologico di un grafo orientato aciclico. Problemi di cammino di costo minimo su un grafo, l’algoritmo di Dijkstra.
Analisi della complessità degli algoritmi presentati. Cenni sulle classi dei problemi P, NP, NP-completi. Il problema “P=NP”.
A. Bellini, A. Guidi, "Linguaggio C - Guida alla programmazione", McGraw-Hill (Quinta edizione)
M. Liverani, "Programmare in C", Esculapio (Seconda edizione)
Dispense e altro materiale didattico fornito dal docente e reso disponibile sul sito web del corso (http://www.mat.uniroma3.it/users/liverani/IN110) e sulla piattaforma Microsoft Teams.
Programma
1. Problemi ed algoritmiIntroduzione alle caratteristiche del calcolatore ed al rapporto programmatore/ esecutore; compiti ed abilità del programmatore; principali caratteristiche ed abilità dell’esecutore, operazioni di base (logiche, aritmetiche e di confronto). Modelli di macchina calcolatrice: cenni sul modello di Von Neumann e sulla macchina di Turing.
Linguaggi di programmazione: linguaggi imperativi e dichiarativi. Istruzioni fondamentali di un linguaggio di programmazione procedurale generico. Algoritmi e programmi; diagrammi di flusso. Regole della programmazione strutturata, cenni sul teorema di Jacopini-Böhm; approccio top-down alla soluzione di un problema.
2. Il linguaggio C
Organizzazione della memoria di un calcolatore, indirizzi, parole, puntatori. Codifica binaria. Tipi di dato, strutture dati (array, matrici, pile, code, code di priorità, liste, alberi, grafi). Linguaggio macchina, linguaggi di alto livello; compilatori ed interpreti, compilazione ed esecuzione di un programma C in ambiente UNIX/Linux. Il linguaggio C: scopi e principali caratteristiche.
La struttura di un programma C, l’inclusione degli header, dichiarazione delle variabili; le librerie. Tipi di dato elementari in linguaggio C: interi, floating point, double, char. Operatori aritmetici, valutazione di espressioni logiche e connettori logici. Puntatori; aritmetica sui puntatori. Array e matrici e loro rappresentazione in memoria. Strutture dati complesse: liste, alberi, grafi; l’istruzione “struct”. Operatore di assegnazione, operatori aritmetici in C in forma estesa e compatta.
Strutture di controllo: “if ... else ...”, “while ...”, “do ... while”, “for ...”.
Funzioni: funzioni di libreria e funzioni definite dall’utente. Passaggio di parametri per valore e per indirizzo alle funzioni. Funzioni ricorsive. Funzioni di input/output: “printf”, “scanf”, “fprintf”, “fscanf”; funzioni per la gestione della memoria: “malloc”, “free”, “sizeof”; gestione di liste di record collegati tramite puntatori.
3. Algoritmi di ordinamento
Algoritmi di ordinamento elementari: Insertion sort, Selection sort, Bubble sort; l’approccio “divide et impera”, l’algoritmo Quick sort. Strutture di tipo LIFO (Last In First Out), pile; strutture di tipo FIFO (First In First Out), code; code di priorità, gli heap. Algoritmi ottimi per l’ordinamento: Heap sort, Merge sort.
Complessità di un algoritmo nel caso peggiore, la notazione “O grande”, analisi della complessità degli algoritmi di ordinamento.
4. Algoritmi su strutture dati di lista, grafo e albero
Definizioni principali: grafo, grafo orientato; sottografo, sottografo indotto; cammino, cammino semplice, grafo connesso, grafo fortemente connesso, grafo completo, clique, ciclo, grafo aciclico; alberi, foreste, spanning tree di un grafo. Strutture dati per la rappresentazione di grafi mediante un calcolatore: liste di adiacenza e matrici di adiacenza. Algoritmi di visita di un grafo: visita in ampiezza (BFS), visita in profondità (DFS), ordinamento topologico di un grafo orientato aciclico. Problemi di cammino di costo minimo su un grafo, l’algoritmo di Dijkstra.
Analisi della complessità degli algoritmi presentati. Cenni sulle classi dei problemi P, NP, NP-completi. Il problema “P=NP”.
Testi Adottati
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduzione agli algoritmi", McGraw–Hill (Terza edizione)A. Bellini, A. Guidi, "Linguaggio C - Guida alla programmazione", McGraw-Hill (Quinta edizione)
M. Liverani, "Programmare in C", Esculapio (Seconda edizione)
Dispense e altro materiale didattico fornito dal docente e reso disponibile sul sito web del corso (http://www.mat.uniroma3.it/users/liverani/IN110) e sulla piattaforma Microsoft Teams.
Bibliografia Di Riferimento
A.V. Aho, J.E. Hopcroft, J.D. Ullman, "Data structures and algorithms", Addison-Wesley. B.W. Kernighan, D.M. Ritchie, "Linguaggio C", seconda edizione, Pearson - Prentice Hall, 1988. B.W. Kernighan, R. Pike, "Programmazione nella pratica", Addison-Wesley, 1999.Modalità Erogazione
Lezioni di teoria in aula ed esercitazioni di programmazione in laboratorio informatico. Le lezioni sono registrate sulla piattaforma Microsoft Teams e fruibili anche a distanza. Le lezioni si svolgono in lingua italiana.Modalità Frequenza
Le lezioni si svolgono in aula. Le esercitazioni di programmazione in C si svolgono nel laboratorio informatico. La frequenza delle lezioni e delle esercitazioni in presenza è fortemente consigliata a tutti gli studenti.Modalità Valutazione
Esame scritto di programmazione in linguaggio C; esame orale sugli argomenti teorici. Sono previste prove di valutazione "in itinere" con esercizi scritti di progettazione di algoritmi e programmazione in linguaggio C che, se superate, esonerano lo studente dalla prova scritta d'esame.
scheda docente
materiale didattico
Introduzione alle caratteristiche del calcolatore ed al rapporto programmatore/ esecutore; compiti ed abilità del programmatore; principali caratteristiche ed abilità dell’esecutore, operazioni di base (logiche, aritmetiche e di confronto). Modelli di macchina calcolatrice: cenni sul modello di Von Neumann e sulla macchina di Turing.
Linguaggi di programmazione: linguaggi imperativi e dichiarativi. Istruzioni fondamentali di un linguaggio di programmazione procedurale generico. Algoritmi e programmi; diagrammi di flusso. Regole della programmazione strutturata, cenni sul teorema di Jacopini-Böhm; approccio top-down alla soluzione di un problema.
2. Il linguaggio C
Organizzazione della memoria di un calcolatore, indirizzi, parole, puntatori. Codifica binaria. Tipi di dato, strutture dati (array, matrici, pile, code, code di priorità, liste, alberi, grafi). Linguaggio macchina, linguaggi di alto livello; compilatori ed interpreti, compilazione ed esecuzione di un programma C in ambiente UNIX/Linux. Il linguaggio C: scopi e principali caratteristiche.
La struttura di un programma C, l’inclusione degli header, dichiarazione delle variabili; le librerie. Tipi di dato elementari in linguaggio C: interi, floating point, double, char. Operatori aritmetici, valutazione di espressioni logiche e connettori logici. Puntatori; aritmetica sui puntatori. Array e matrici e loro rappresentazione in memoria. Strutture dati complesse: liste, alberi, grafi; l’istruzione “struct”. Operatore di assegnazione, operatori aritmetici in C in forma estesa e compatta.
Strutture di controllo: “if ... else ...”, “while ...”, “do ... while”, “for ...”.
Funzioni: funzioni di libreria e funzioni definite dall’utente. Passaggio di parametri per valore e per indirizzo alle funzioni. Funzioni ricorsive. Funzioni di input/output: “printf”, “scanf”, “fprintf”, “fscanf”; funzioni per la gestione della memoria: “malloc”, “free”, “sizeof”; gestione di liste di record collegati tramite puntatori.
3. Algoritmi di ordinamento
Algoritmi di ordinamento elementari: Insertion sort, Selection sort, Bubble sort; l’approccio “divide et impera”, l’algoritmo Quick sort. Strutture di tipo LIFO (Last In First Out), pile; strutture di tipo FIFO (First In First Out), code; code di priorità, gli heap. Algoritmi ottimi per l’ordinamento: Heap sort, Merge sort.
Complessità di un algoritmo nel caso peggiore, la notazione “O grande”, analisi della complessità degli algoritmi di ordinamento.
4. Algoritmi su strutture dati di lista, grafo e albero
Definizioni principali: grafo, grafo orientato; sottografo, sottografo indotto; cammino, cammino semplice, grafo connesso, grafo fortemente connesso, grafo completo, clique, ciclo, grafo aciclico; alberi, foreste, spanning tree di un grafo. Strutture dati per la rappresentazione di grafi mediante un calcolatore: liste di adiacenza e matrici di adiacenza. Algoritmi di visita di un grafo: visita in ampiezza (BFS), visita in profondità (DFS), ordinamento topologico di un grafo orientato aciclico. Problemi di cammino di costo minimo su un grafo, l’algoritmo di Dijkstra.
Analisi della complessità degli algoritmi presentati. Cenni sulle classi dei problemi P, NP, NP-completi. Il problema “P=NP”.
A. Bellini, A. Guidi, "Linguaggio C - Guida alla programmazione", McGraw-Hill (Quinta edizione)
M. Liverani, "Programmare in C", Esculapio (Seconda edizione)
Dispense e altro materiale didattico fornito dal docente e reso disponibile sul sito web del corso (http://www.mat.uniroma3.it/users/liverani/IN110) e sulla piattaforma Microsoft Teams.
Programma
1. Problemi ed algoritmiIntroduzione alle caratteristiche del calcolatore ed al rapporto programmatore/ esecutore; compiti ed abilità del programmatore; principali caratteristiche ed abilità dell’esecutore, operazioni di base (logiche, aritmetiche e di confronto). Modelli di macchina calcolatrice: cenni sul modello di Von Neumann e sulla macchina di Turing.
Linguaggi di programmazione: linguaggi imperativi e dichiarativi. Istruzioni fondamentali di un linguaggio di programmazione procedurale generico. Algoritmi e programmi; diagrammi di flusso. Regole della programmazione strutturata, cenni sul teorema di Jacopini-Böhm; approccio top-down alla soluzione di un problema.
2. Il linguaggio C
Organizzazione della memoria di un calcolatore, indirizzi, parole, puntatori. Codifica binaria. Tipi di dato, strutture dati (array, matrici, pile, code, code di priorità, liste, alberi, grafi). Linguaggio macchina, linguaggi di alto livello; compilatori ed interpreti, compilazione ed esecuzione di un programma C in ambiente UNIX/Linux. Il linguaggio C: scopi e principali caratteristiche.
La struttura di un programma C, l’inclusione degli header, dichiarazione delle variabili; le librerie. Tipi di dato elementari in linguaggio C: interi, floating point, double, char. Operatori aritmetici, valutazione di espressioni logiche e connettori logici. Puntatori; aritmetica sui puntatori. Array e matrici e loro rappresentazione in memoria. Strutture dati complesse: liste, alberi, grafi; l’istruzione “struct”. Operatore di assegnazione, operatori aritmetici in C in forma estesa e compatta.
Strutture di controllo: “if ... else ...”, “while ...”, “do ... while”, “for ...”.
Funzioni: funzioni di libreria e funzioni definite dall’utente. Passaggio di parametri per valore e per indirizzo alle funzioni. Funzioni ricorsive. Funzioni di input/output: “printf”, “scanf”, “fprintf”, “fscanf”; funzioni per la gestione della memoria: “malloc”, “free”, “sizeof”; gestione di liste di record collegati tramite puntatori.
3. Algoritmi di ordinamento
Algoritmi di ordinamento elementari: Insertion sort, Selection sort, Bubble sort; l’approccio “divide et impera”, l’algoritmo Quick sort. Strutture di tipo LIFO (Last In First Out), pile; strutture di tipo FIFO (First In First Out), code; code di priorità, gli heap. Algoritmi ottimi per l’ordinamento: Heap sort, Merge sort.
Complessità di un algoritmo nel caso peggiore, la notazione “O grande”, analisi della complessità degli algoritmi di ordinamento.
4. Algoritmi su strutture dati di lista, grafo e albero
Definizioni principali: grafo, grafo orientato; sottografo, sottografo indotto; cammino, cammino semplice, grafo connesso, grafo fortemente connesso, grafo completo, clique, ciclo, grafo aciclico; alberi, foreste, spanning tree di un grafo. Strutture dati per la rappresentazione di grafi mediante un calcolatore: liste di adiacenza e matrici di adiacenza. Algoritmi di visita di un grafo: visita in ampiezza (BFS), visita in profondità (DFS), ordinamento topologico di un grafo orientato aciclico. Problemi di cammino di costo minimo su un grafo, l’algoritmo di Dijkstra.
Analisi della complessità degli algoritmi presentati. Cenni sulle classi dei problemi P, NP, NP-completi. Il problema “P=NP”.
Testi Adottati
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduzione agli algoritmi", McGraw–Hill (Terza edizione)A. Bellini, A. Guidi, "Linguaggio C - Guida alla programmazione", McGraw-Hill (Quinta edizione)
M. Liverani, "Programmare in C", Esculapio (Seconda edizione)
Dispense e altro materiale didattico fornito dal docente e reso disponibile sul sito web del corso (http://www.mat.uniroma3.it/users/liverani/IN110) e sulla piattaforma Microsoft Teams.
Bibliografia Di Riferimento
A.V. Aho, J.E. Hopcroft, J.D. Ullman, "Data structures and algorithms", Addison-Wesley. B.W. Kernighan, D.M. Ritchie, "Linguaggio C", seconda edizione, Pearson - Prentice Hall, 1988. B.W. Kernighan, R. Pike, "Programmazione nella pratica", Addison-Wesley, 1999.Modalità Erogazione
Lezioni di teoria in aula ed esercitazioni di programmazione in laboratorio informatico. Le lezioni sono registrate sulla piattaforma Microsoft Teams e fruibili anche a distanza. Le lezioni si svolgono in lingua italiana.Modalità Frequenza
Le lezioni si svolgono in aula. Le esercitazioni di programmazione in C si svolgono nel laboratorio informatico. La frequenza delle lezioni e delle esercitazioni in presenza è fortemente consigliata a tutti gli studenti.Modalità Valutazione
Esame scritto di programmazione in linguaggio C; esame orale sugli argomenti teorici. Sono previste prove di valutazione "in itinere" con esercizi scritti di progettazione di algoritmi e programmazione in linguaggio C che, se superate, esonerano lo studente dalla prova scritta d'esame.