Questa è la pagina web del Corso di Informatica, tenuto nell'ambito del Percorso Abilitante Speciale (PAS) dell'Università degli Studi Roma Tre per la Classe A048 “Matematica Applicata” dell'anno accademico 2013-2014, promosso ed organizzato dal CAFIS (Centro di servizio di Ateneo per la Formazione e lo sviluppo professionale degli Insegnanti della Scuola secondaria).

In questa pagina è possibile trovare informazioni sul corso, materiale didattico relativo al corso, alcuni riferimenti bibliografici utili per svolgere eventuali approfondimenti inerenti gli argomenti trattati nel corso ed eventuali comunicazioni relative al corso stesso.

È possibile contattare via e-mail il prof. Marco Liverani, docente del corso di Informatica, al seguente indirizzo di posta elettronica: liverani@mat.uniroma3.it.

Informazioni sul corso

Il Corso di Informatica è riservato agli iscritti al percorso PAS nella classe della “Matematica Applicata”. L'obiettivo è quello di costruire una competenza di base inerente il concetto di algoritmo e più in generale la capacità di progettare ed analizzare una procedura per il calcolo automatico della soluzione di un problema. Il corso si propone anche di fornire chiavi di lettura degli argomenti trattati e degli spunti didattici utili nell'ambito di corsi di Matematica nelle scuole tecniche secondarie.

Il corso si tiene nell'aula B3 dell'edificio aule del Dipartimento di Matematica e Fisica, di L.go San Leonardo Murialdo n.1, a Roma. Le lezioni si svolgono il venerdì dalle ore 16:45 alle ore 19:00 nelle seguenti date:

1. venerdì 21 marzo 2014 ✓
2. venerdì 28 marzo 2014 ✓
3. venerdì 4 aprile 2014 ✓
4. venerdì 11 aprile 2014 ✓
5. venerdì 9 maggio 2014 ✓
6. venerdì 16 maggio 2014 ✓

Diario delle lezioni

Lezione n.1: venerdì 21 marzo 2014

Presentazione del corso, del calendario delle lezioni, degli obiettivi didattici e degli argomenti che saranno proposti nelle lezioni.

Introduzione informale al concetto di algoritmo, come procedura per il calcolo automatico della soluzione di un problema; cenni sulla necessità di definire un “modello di calcolo” e un formalismo per definire le capacità dell'esecutore e la modalità di rappresentazione dell'algoritmo stesso; cenni sulla Macchina di Turing, sul λ-calcolo, sul modello di Von Neumann; caratteristiche positive e negative del nostro modello di esecutore di riferimento.

Lezione n.2: venerdì 28 marzo 2014

Formalizzazione di un algoritmo mediante un linguaggio; linguaggi dichiarativi e imperativi; istruzioni fondamentali di un linguaggio imperativo, il concetto di variabile e di assegnazione di un valore ad una variabile; calcolo del minimo comune multiplo tra due interi, crivello di Eratostene per il calcolo dei numeri primi minori o uguali ad n; diagrammi di flusso, strutture condizionali e iterative attraverso alcuni esempi: massimo tra due numeri, massimo fra tre numeri, massimo fra n numeri.

Lezione n.3: venerdì 4 aprile 2014

Formalizzazione del concetto di algoritmo; programmazione strutturata, struttura sequenziale, iterativa e condizionale nella rappresentazione di un algoritmo mediante un diagramma di flusso; programmazione strutturata, cenni sul Teorema Fondamentale della Programmazione Strutturata di Corrado Böhm e Giuseppe Jacopini.

Problemi, istanza di un problema, dimensione dell'istanza di un problema; calcolo del numero di operazioni elementari svolte da un algoritmo per risolvere un'istanza di dimensione n di un problema; complessità computazionale di un algoritmo, classi di complessità e notazione “O grande”.

Lezione n.4: venerdì 11 aprile 2014

Complessità di algoritmi e complessità di problemi; le classi di complessità P, NP, NP-completi; il problema “P=NP?”, esempi di problemi NP completi.

Il problema dell'ordinamento (sort), definizione del problema, algoritmo elementare di ordinamento per selezione (selection sort), strategia risolutiva, pseudo-codice dell'algoritmo, esempi, complessità computazionale; l'algoritmo di ordinamento a bolle (bubble sort), strategia risolutiva, esempi e complessità computazionale; l'algoritmo di ordinamento per fusione (merge sort), strategia risolutiva, esempi, complessità computazionale.

Lezione n.5: venerdì 9 maggio 2014

Cenni sulla teoria dei grafi e sull'importanza dei modelli basati su grafi e alberi per la risoluzione di problemi complessi; definizione di grafo, cammino, albero, proprietà di connessione e di aciclicità. Rappresentazione di grafi attraverso matrici di adiacenza, il problema della “visita” di un grafo; algoritmo di visita in ampiezza; cenni sull'algoritmo per la visita in profondità.

Lezione n.6: venerdì 16 maggio 2014

Linguaggi di programmazione, linguaggi di alto e di basso livello, paradigmi di programmazione, processo di compilazione e di interpretazione/esecuzione di un programma, compilatori ed interpreti. Cenni sul linguaggio di programmazione Python, le istruzioni fondamentali del linguaggio, esempi.

Materiale didattico

Appunti sintetici degli argomenti presentati nelle lezioni del corso.

1. Modelli di calcolo: appunti sui modelli di calcolo, sulla Macchina di Turing e sul modello di Von Neumann.
2. Algoritmi e diagrammi di flusso: appunti sulle caratteristiche e le capacità dell'esecutore, sugli algoritmi codificati con un linguaggio imperativo, sui diagrammi di flusso.
3. Complessità computazionale: appunti sul concetto di complessità computazionale di un algoritmo e di un problema.
4. Algoritmi di ordinamento: appunti sul problema dell'ordinamento e su alcune strategie risolutive per la soluzione del problema: ordinamento per selezione (selection sort), ordinamento a bolle (bubble sort), ordinamento per fusione (merge sort).
5. Algoritmi su grafi: appunti su grafi e alberi e sugli algoritmi che affrontano problemi legati ai grafi e agli alberi. Si veda anche il breve dossier sui grafi pubblicato sul n. 7/8 del 2008 della rivista di divulgazione matematica “Per la Tangente”, su alcuni problemi fondamentali sui grafi.
6. Linguaggio di programmazione Python: linguaggi di programmazione, paradigmi di programmazione, compilatori e interpreti, cenni sul linguaggio Python ed esempi. È disponibile anche una raccolta di esempi in linguaggio Python visti a lezione. Per installare l'interprete del linguaggio Python (per Microsoft Windows, Apple OS X o Linux) si deve scaricare il pacchetto di installazione dal seguente link sul sito della comunità italiana del linguaggio Python: http://www.python.it/download/.

Bibliografia

Di seguito sono riportati alcuni riferimenti bibliografici interessanti per compiere alcuni approfondimenti sui temi della teoria degli algoritmi e sulla matematica.

Teoria degli algoritmi

1. A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data structures and algorithms, Addison-Wesley, 1987.
2. A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
3. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati, Terza Edizione, McGraw-Hill, 2010.

Testi di divulgazione scientifica nell'ambito degli algoritmi e della calcolabilità

1. R. Courant, H. Robbins, Che cos'è la matematica?, Universale Scientifica Boringhieri, 1985.
2. M. Davis, Il calcolatore universale, Adelphi, 2012.
3. M. Frixione, D. Palladino, Funzioni, macchine, algoritmi, Carocci, 2004.
4. P. Gritzmann, R. Brandenberg, Alla ricerca della via più breve - Un'avventura matematica, Springer, 2005.
5. M. Liverani, Qual è il problema? - Metodi, strategie risolutive, algoritmi, Mimesis, 2005.
6. F. Luccio, L. Pagli, Algoritmi, divinità e gente comune, Edizioni ETS, 1999.
7. J. MacCormick, 9 algoritmi che hanno cambiato il futuro, Apogeo, 2013.
8. G. Spirito, Matematica senza numeri, Newton & Compton Editori, 2004.

Matematica dilettevole

1. K. Devlin, I problemi del millennio, Longanesi, 2005.
2. A. Doxiadis, Zio Petros e la congettura di Goldbach, Bompiani, 2001.
3. R. Kanigel, L'uomo che vide l'infinito, Rizzoli, 2003.
4. S. Singh, Codici & segreti, Rizzoli, 2001.

Comunicazioni