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 e comprensione dei concetti di base dell'informatica e delle principali funzionalità di un sistema informatico di base
- Conoscenza e comprensione dei metodi generali di studio di un linguaggio di programmazione, dell'approccio algoritmico alla risoluzione dei problemi, e dei metodi generali di ragionamento nella progettazione di strutture dati e algoritmi
- Conoscenza e comprensione del linguaggio c
- Conoscenza e 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
- Capacità avanzata nella progettazione e nello sviluppo in linguaggio c di strutture dati e algoritmi
- Capacità di formalizzare il problema della complessità di un algoritmo
- Capacità di formalizzare il concetto di correttezza di un algoritmo
- Capacità di sviluppare, effettuare il debug ed applicare algoritmi di base a casi di interesse ingegneristico per risolvere problemi informativi o numerici
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 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 aggiuntive 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 volte ad accertare le competenze teoriche e pratiche acquisite sugli argomenti del corso.
- 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 sul proprio computer portatile (oppure 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.
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.