Enrico Vicario, "Fondamenti di Programmazione, linguaggio c, strutture dati e algoritmi elementari, c++," Editrice Esculapio, Bologna.
Il codice C di diversi esempi svolti a lezione è a disposizione sul sito del docente.
Obiettivi Formativi
Fornire le conoscenze di base relative alla struttura di un calcolatore ed alla esecuzione di un programma.
Conoscenza ed uso del linguaggio C. Capacità di realizzare programma di media complessità in linguaggio C. Conoscenza degli algoritmi per la gestione di strutture dati base, algoritmi di ricerca e ordinamento.
Prerequisiti
I requisiti essenziali sono l’interesse, la capacità di ragionamento logico, la attitudine ai processi di conoscenza deduttivi, la capacità di attenzione e applicazione ai problemi. Molte di queste cose si apprendono nello studio della matematica, che è utile nel formare il metodo e fornire strumenti specifici. Chi ha esperienza nella programmazione, tipicamente gli studenti che provengono da istituti tecnici, è inizialmente facilitato. Il corso è comunque disegnato per studenti che non abbiano alcuna precedente conoscenza in materia di informatica.
Capacità avanzata nell’uso il linguaggio c nello sviluppo di algoritmi, anche di elevata complessità nel livello della programmazione, seppure con minore complessità nella struttura delle funzioni.
Comprensione del rapporto tra linguaggio c e suo ambiente di esecuzione, natura del processo di compilazione, link e assemblaggio, dei principi di funzionamento di un processore.
Capacità di formalizzazione del problema della complessità, inquadramento del concetto di correttezza.
Capacità di progettazione e realizzazione di algoritmi e strutture dati elementari (seppure complesse nel livello di programmazione).
Comprensione del metodo generale di studio di un linguaggio di programmazione.
Comprensione di metodi generali del ragionamento e della progettazione.
Metodi Didattici
Prevalentemente lezioni frontali con presentazione alla lavagna col gesso. Alcune lezioni finalizzate alla esercitazione e svolte in laboratorio. Alcune lezioni svolte con l’ausilio di un portatile collegato a proiettore per illustrare l’uso di compilatore e ambiente di sviluppo.
Commissione:
S. Berretti, P. Pala, C. Colombo, E. Vicario
Modalità di verifica apprendimento
L'esame si compone di una prova scritta e una orale.
La prova scritta consiste in alcuni elaborati di programmazione e nella discussione di contenuti del programma.
I testi assegnati nelle prove scritte sono resi disponibili su internet.
La prova scritta è svolta su carta. Al termine, della prova i candidati ricevono la fotocopia del loro elaborato.
Per accedere alla prova orale, il candidato deve correggere il proprio elaborato, riportando le correzioni in maniera visibile sulla fotocopia. Il candidato deve anche realizzare il programma corretto e funzionante che corregge l'elaborato e lo completa facendone un programma autocontenuto. Il candidato deve infine fornire una autovalutazione del proprio elaborato, in base al valore attribuito a ciascuna parte della prova, alla discussione della soluzione, all'esperienza acquisita nella correzione e realizzazione effettiva del programma.
La prova orale può essere sostenuta a partire dalla settimana seguente alla prova scritta, non oltre la prova scritta successiva.
La prova orale inizia con la discussione dell'elaborato, e prosegue con l'approfondimento di tutti i contenuti del programma.
Programma del corso
PARTE I: RAPPRESENTAZIONE DI BASSO LIVELLO
Introduzione intuitiva al linguaggio c; codifica numerica dei tipi; codifica di basso livello delle istruzioni in forma simbolica (assembler MIPS) e numerica (linguaggio macchina MIPS); architettura di un processore Risc (Risc4000); processo di compilazione e assemblaggio.
PARTE II: LINGUAGGIO C
Definizione di un linguaggio: sintassi, grammatica, albero sintattico, BNF, semantica; Linguaggio c: tipi variabili e costanti, Operatori ed espressioni, Puntatori, Array, Istruzioni, Funzioni, dati strutturati.
PART III: ELEMENTARY DATA STRUCTURE
List: sequential representation, representation with arrays and indexes, linked representation with pointers; iteratite and recursive algorithms.
PART IV: ELEMENTARY ALGORITHMS
Execution cost and complexity; Search algorithms: sequential, binary, jump search; Sorting algorithms: sequential sort, bubble-sort, merge-sort, quicksort, heapsort. Complexity of a problem: the case of sorting.