Fondamenti di Programmazione

FONDAMENTI DI PROGRAMMAZIONE

Corso di Laurea in Matematica
Anno accademico 2007/2008

Lezioni:
Giovanni Manzini

Esercitazioni:
Michele Albano

Attenzione: materiale utile per il corso sarà distribuito mediante la piattaforma Moodle. Iscrivetevi utilizzando le stesse username e password del portale ALICE.

Scopo del corso. Il primo obiettivo del corso è quello di insegnare il linguaggio di programmazione C. Al termine del corso gli studenti dovrebbero essere in grado di tradurre un metodo astratto di risoluzione di un problema in un programma funzionante. Questa parte del corso è fortemente integrata con il corso di Laboratorio di Programmazione.
Il secondo obiettivo del corso è quello di illustrare alcuni concetti di informatica teorica. In particolare si affronterà la teoria delle degli automi a stati finiti e della NP completezza che costituiscono due importanti esempi di come sia possibile dimostrare matematicamente dei risultati su quello che le macchine calcolatrici possono o non possono fare.

Ricevimento studenti. Martedì dalle 14 alle 15 (studio 296b presso il dipartimento di Informatica) o su appuntamento da concordare mandando un email a manzini@unipmn.it. Il ricevimento del Dott. Albano si tiene il Martedì dalle 15 alle 16.

Modalità di esame. È prevista una prova scritta e un esame orale. Durante l'anno verranno tenuti due compitini che, se superati, permettono di accedere direttamente all'orale. Sono disponibili i testi degli esami scritti assegnati in passato, e alcune soluzioni degli esercizi su automi e grammatiche.

Programma del corso. È disponibile la versione provvisoria del programma del corso.

Materiale bibliografico.

	Testo di riferimento per il linguaggio C [BG] A. Bellini, A. Guidi. Linguaggio C, guida alla programmazione (3a edizione). MCGraw-Hill.
	Materiale di riferimento per gli automi a stati finiti. [HU] J. Hopcroft, J. Ullman Formal languages and their relation to automata. Capitolo 3. Nota: il testo è disponibile in diverse biblioteche, ma non è più in commercio.
	Testo molto bello, purtroppo noi faremo solo poche pagine dei capitoli 6 e 8. [KT] J. Kleinberg, E. Tardos Algorithm Design. Addison Wesley.
	Testo introduttivo alla programmazione con molti esempi istruttivi. [FLRT] G. Fiorentino, M. R. Laganà, F. Romani, F. Turini C e Java - Laboratorio di programmazione. MCGraw-Hill.
	Testo sul C chiaro e completo. [KP] A. Kelley, I. Pohl. C, didattica e programmazione. MCGraw-Hill.
	Testo classico sul C, consigliato a chi già conosce un linguaggio di programmazione. [KR] B. Kernighan, D. Ritchie. Linguaggio C (seconda edizione). Jackson Libri.
	Ambiente di sviluppo C\C++ per Windows. DJGPP è un insieme di strumenti (compilatore, editor, debugger, etc.) completo e affidabile.
	Ambiente di sviluppo C\C++ per Windows. Dev-C++ è un ambiente di sviluppo meno completo di DJGPP, ma più facile da istallare e usare. Leggersi anche le FAQ.

Registro Elettronico delle lezioni. Il corso prevede 30 ore di lezione e 30 di esercitazioni. Nota: i numeri dei capitoli del testo [BG] si riferiscono alla seconda e terza edizione (che hanno la stessa numerazione). Quando possibile ho indicato tra parentesi il numero dei corrispondenti capitoli della prima edizione.

	Argomenti della lezione	Riferimenti
Lezione 1 26/2/08	Introduzione al corso. Primi elementi del linguaggio C: variabili, espressioni aritmetiche.	[BG], Capitolo 3 (1).
Lezione 2 28/2/08	Automi a stati finiti: definizioni ed esempi	[HU] Sezione 3.1.
Lezione 3 (es) 28/2/08	Istruzione if, operatori logici e loro combinazione mediante AND, OR, NOT.	[BG], Capitolo 4 (2).
Lezione 4 (es) 4/3/08	Istruzioni switch/case, for, while. Principali operatori del C.	[BG], Capitoli 4, 5 e 6 (2 e 3).
Lezione 5 6/3/08	Esercizi su costruzione di automi a stati finiti. Dimostrazione esistenza di linguaggi non riconoscibili basata sul concetto di cardinalità.	[HU] Sezione 3.1.
Lezione 6 (es) 6/3/08	Istruzione do/while. Calcolo del fattoriale e del mcd.	[BG], Capitolo 6 (3).
Lezione 7 11/3/08	Esercizi di programmazione su numeri primi e fattorizzazione.	tabella_primi.c
Lezione 8 (es) 13/3/08	Ricerche e ordinamenti.	[BG], Capitolo 8 (5).
Lezione 9 (es) 13/3/08	Esercizi su rappresentazione e operazioni sui polinomi. Stringhe di caratteri.	[BG], Capitolo 9 (6).
Lezione 10 18/3/08	Pumping Lemma: enunciato dimostrazione ed esercizi.	Dispensa sul Pumping Lemma.
Lezione 11 18/3/08	Definizione e uso di funzioni	[BG], Capitolo 10 fino a 10.8 (7 fino a 7.8).
Lezione 12 (es) 1/4/08	Esercizi su funzioni, varabili locali e globali
Lezione 13 3/4/08	Cardinalità del linguaggio riconosciuto da un automa. Unione, intersezione, e complemento di linguaggi regolari.	[HU] Sezioni 3.5 e 3.6.
Lezione 14 (es) 3/4/08	Il tipo `void`. Introduzione alle procedure ricorsive.	[BG] Sezioni 10.9 e da 12.1 a 12.4 (da 10.1 a 10.4).
Lezione 15 8/4/08	Passaggio di array alle procedure. Altri esempi di ricorsione.	gcdex.c, somma.c
Lezione 16 8/4/08	Automi a stati finiti non deterministici. Equivalenza tra automi deterministici e non deterministici. Prodotto e chiusura di linguaggi.	[HU] Sezioni 3.3 e 3.5,
Lezione 17 (es) 10/4/08	Esercizi sulla ricorsione. Backtraking.	[BG] Sezioni 12.6 a 12.7 (10.6 e 10.7).
16/4/08	Primo compitino.
Lezione 18 22/4/08	Correzione del compitino. Altri esempi di ricorsione. Mutua ricorsività.	somme.c
Lezione 19 (es) 14/4/08	Stringhe di caratteri. Puntatori (1).	[BG], Capitoli 9 e 11 fino a 11.5 (6 e 8 fino a 8.5).
Lezione 20 24/4/08	Esistenza di problemi non risolvibili mediante un programma. Il problema della terminazione. Il problema del commesso viaggiatore.	Dispensa, tsp.c
Lezione 21 29/4/08	Puntatori (2). Array bidimensionali.	Allocazione dinamica, Array bidimensionali
Lezione 22 6/5/08	Esercizi sull'uso dei puntatori e sulla ricorsione (LadroPigro e Raggiungibile)
Lezione 23 8/5/08	Riducibilità polinomiale. Il concetto di NP-completezza.	[KT] Sezioni 8.1, 8.2, 8.3
Lezione 24 (es) 8/5/08	Uso delle struct.	[BG] Capitolo 13 (12.1, 12.2).
Lezione 25 13/5/08	Esercizi sulle struct. Calcolo del fattoriale in precisione multipla.	LadroPigro.c, fattoriale2.c
Lezione 26 15/5/08	NP-completezza di CircuitSat, 3Sat, Ciclo Hamiltoniano e TSP.	[KT] Sezioni 8.4 e 8.5 (fino a pag. 479)
Lezione 27 (es) 15/5/08	Uso di argc e argv. Operazioni sui bit.	[BG], Sezione 15.4 (11.4).
Lezione 28 (es) 20/5/08	Uso di puntatori a funzione (cenni).
Lezione 29 22/5/08	Programmazione dinamica. Risoluzione di SubsetSum in tempo pseudo-polinomiale mediante programmazione dinamica.	[KT] Sezioni 6.1, 6.2, 6.4 (disponibili su Moodle), sorgente miriam.c
Lezione 30 (es) 22/5/08	Esercizi di riepilogo.
27/5/08	Secondo compitino (sono ammessi solo quelli che hanno ottenuto la sufficienza nel primo).

Questa pagina è stata composta secondo lo standard HTML4.01 e può essere letta usando un qualsiasi browser.