Stefano Berretti, Laura Carnevali, Enrico Vicario, "Fondamenti di Programmazione: linguaggio c, strutture dati e algoritmi elementari, c++", Società Editrice Esculapio, Bologna, 2017.
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 con presentazione alla lavagna tradizionale. Il corso prevede 20 ore di lezioni di tutorato (esercitazioni in aula).
Altre Informazioni
Gli studenti sono invitati a prendere visione della pagina del corso su Moodle (https://e-l.unifi.it) per maggiori informazioni.
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. Non è consentita la consultazione di libri, dispense e appunti; non è consentito l'utilizzo della calcolatrice. Il testo, la soluzione e i risultati di ogni prova scritta sono pubblicati sulla pagina del corso prima della successiva prova orale.
- Possono accedere alla prova orale solo i candidati che ottengono una valutazione almeno pari a 15/30 alla prova scritta. Per accedere alla prova orale, i candidati devono implementare la soluzione degli esercizi proposti realizzando dei programmi autocontenuti (usando un qualsiasi ambiente di sviluppo). In sede di prova orale, tali programmi devono essere prodotti su un supporto di memoria USB comprensivo di sorgenti ed eseguibili (oppure sul proprio computer portatile). 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.
Gli studenti che superano la prova scritta hanno facoltà di sostenere la prova orale nel medesimo appello o in uno qualsiasi degli appelli successivi.
Gli studenti che non superano la prova orale devono ripetere la prova scritta.
Programma del corso
1. Rappresentazione di basso livello
- Rappresentazione dei dati: codifica 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
- Definizione 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; libreria standard; chiamate di sistema.
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.