Enrico Vicario, "Fondamenti di Programmazione: linguaggio c, strutture dati e algoritmi elementari, c++", Società Editrice Esculapio, Bologna, 2011.
Obiettivi Formativi
- Conoscenza del linguaggio c e padronanza di una terminologia corretta e dei concetti di base dell'informatica.
- Capacità avanzata nella progettazione e nello sviluppo in linguaggio c di strutture dati e algoritmi (anche di elevata complessità nel livello della programmazione seppur di minore complessità nella struttura delle funzioni).
- Capacità di formalizzazione del problema della complessità di un algoritmo.
- Capacità di inquadramento del concetto di correttezza di un algoritmo.
- Comprensione dei metodi generali di studio di un linguaggio di programmazione.
- Comprensione dei metodi generali di ragionamento nella progettazione di strutture dati e algoritmi.
- Comprensione della struttura e dei principi di funzionamento di un calcolatore, del rapporto tra il linguaggio c e il suo ambiente di esecuzione, e del processo di compilazione, assemblaggio e collegamento.
Prerequisiti
Il corso è indirizzato a studenti che hanno capacità di ragionamento logico, attitudine ai processi di conoscenza deduttivi, capacità di attenzione e applicazione ai problemi. Gli studenti che hanno esperienza nella programmazione (tipicamente gli studenti che provengono da licei tecnologici) sono inizialmente facilitati. Il corso è comunque disegnato per studenti che non hanno alcuna conoscenza di informatica.
Metodi Didattici
Le lezioni sono tenute prevalentemente con presentazione alla lavagna tradizionale. Alcune lezioni sono svolte con l'ausilio di un computer portatile collegato ad un proiettore per illustrare l'uso di compilatore e debugger attraverso l'ambiente di sviluppo Eclipse.
Altre Informazioni
Gli studenti sono invitati a prendere visione della pagina del corso per maggiori informazioni: http://stlab.dinfo.unifi.it/carnevali/foundations_computer_programming.html
Modalità di verifica apprendimento
L'esame si compone di una prova scritta ed una orale.
- La prova scritta consiste nella soluzione di esercizi di programmazione in linguaggio c e nella discussione di contenuti del programma. La prova scritta è svolta su carta e ha una durata di 1h - 1h 30'. Non è consentita la consultazione di libri, dispense e appunti. Non è consentito l'utilizzo della calcolatrice. Al termine della prova scritta, i candidati ricevono la soluzione degli esercizi di programmazione c. Il testo, la soluzione e i risultati di ogni prova scritta sono pubblicati su questa pagina prima della successiva prova orale.
- Possono accedere alla prova orale solo i candidati che ottengono una valutazione sufficiente alla prova scritta. Per accedere alla prova orale, i candidati devono implementare la soluzione degli esercizi proposti realizzando dei programmi autocontenuti. In sede di prova orale, tali programmi devono essere prodotti su un supporto di memoria USB comprensivo di sorgenti ed eseguibili. La prova orale inizia con la discussione dell'elaborato e prosegue con l'approfondimento di contenuti del programma.
- Il corso non prevede il salto appello (gli studenti che ottengono una valutazione non sufficiente ad una prova scritta o orale hanno facoltà di presentarsi alla prova scritta successiva).
Programma del corso
1. Rappresentazione di basso livello
- Rappresentazione dei dati: codi ca posizionale; algoritmi di conversione della base di rappresentazione; interi senza segno; caratteri; interi con segno; valori in virgola mobile.
- Rappresentazione delle istruzioni: linguaggio assembler e linguaggio macchina (istruzioni aritmetiche, di lettura /scrittura in memoria, e di controllo del flusso); esecuzione su un processore; compilazione, assemblaggio e collegamento.
2. Rappresentazione di alto livello
- De nizione di un linguaggio: sintassi; grammatica; albero sintattico; il metalinguaggio BNF; semantica.
- Linguaggio c: tipi, variabili e costanti; operatori ed espressioni; puntatori; array; istruzioni; funzioni; dati strutturati.
3. Strutture dati e algoritmi elementari
- Liste: rappresentazione in forma sequenziale, collegata con array e indici, collegata con puntatori.
- Schemi di programmazione iterativa e ricorsiva.
4. Algoritmi elementari
- Costo di esecuzione e complessit à.
- Algoritmi di ricerca: sequenziale, binaria, a salti.
- Algoritmi di ordinamento: sequential-sort, bubble-sort, merge-sort, quick-sort.
- Complessità minima di un problema: il caso dell'ordinamento.