Title: Corso:
Author: Dipartimento di Matematica
Last saved by: stefano berardi
Company: Universita' di Torino

Presentazione del Corso:
Informatica I
Corso di Laurea in Matematica
Anno 2006-2007
Università di Torino

Il corso di Informatica I, e il suo seguito, il corso Informatica II, a dispetto del nome, non trattano propriamente di argomenti di Informatica, ma piuttosto di Programmazione. I due corsi dovrebbero piuttosto essere chiamati, pertanto, Programmazione I e Programmazione II.

La Programmazione non è l’Informatica.  Solo per notizia, l’Informatica è una scienza che comprende, tra l’altro: 
-	lo studio delle reti di calcolatori e dei sistemi operativi (come Windows) che li fanno funzionare. 
-	l’Intelligenza Artificiale, ovvero l’elaborazione di programmi che simulino alcune attività della mente umana; 
-	lo studio del concetto matematico di calcolo (dei “fondamenti” concettuali dell’informatica), e il conseguente sviluppo di nuovi linguaggi di programmazione.
La Programmazione, invece, è un’attività pratica: è l’arte di scrivere programmi per risolvere svariati problemi nei più diversi campi dell’attività umana. La Programmazione, dunque, è solo uno strumento, utilizzato sia dall’informatico, che dal matematico, dal fisico, dall’ingegnere, dalll’economista, dal linguista, e da molti altri. 

È doveroso aggiungere, naturalmente, che un informatico ha un diverso e a volte più profondo grado di conoscenza della programmazione rispetto ad altri studiosi. Un informatico, infatti, studia anche come un linguaggio di programmazione nasce e si sviluppa, anziché limitarsi ad usarlo.

Precisato dunque il contenuto del corso (per maggiori dettagli rimandiamo alla scheda analitica al fondo di questa presentazione) chiediamoci ora: perché la Programmazione dovrebbe servire ad un matematico? 
La Matematica è una scienza astratta, mentre la Programmazione è un’attività pratica. Esistono tuttavia diversi modi in cui la seconda può essere utile alla prima.

1. La programmazione serve per fare i calcoli. Innanzitutto, l’Analisi Matematica e la Geometria richiedono calcoli lunghi e complessi. Di conseguenza, in ogni corso di Analisi ci sono numerosi esercizi la cui soluzione richiede di saper scrivere, o almeno saper usare, dei programmi di calcolo. Questo primo utilizzo della programmazione da parte del matematico appare evidente ed è ben noto a tutti. Tuttavia, non si tratta dell’utilizzo principale. Infatti, i calcoli richiesti, poniamo, dall’Analisi Matematica tendono ad essere sempre gli stessi. Di conseguenza, ci conviene, anziché scrivere dei programmi noi stessi, comprare un “pacchetto” di programmi già pronti da usare a tale scopo.

In questo periodo, un pacchetto che si è rivelato molto utile per ogni genere di calcolo scientifico è il pacchetto chiamato Mathematica, distribuito dalla Wolfram Company.

In altre parole: per svolgere i calcoli richiesti dall’Analisi Matematica non dobbiamo necessariamente saper programmare. Ci basta saper usare programmi scritti da altri.

2. La programmazione serve per spiegare concetti geometrici. Una motivazione più robusta perché il matematico impari a programmare è che, attraverso la programmazione, è possibile dare rappresentazioni visive di concetti geometrici che altrimenti sarebbero molto difficili da assimilare. Per esempio, un intero nuovo ramo della Matematica, lo studio dei Frattali, si è sviluppato solo quando è stato possibile disegnare le figure geometriche di dimensione “fratta” (non intera, in altre parole, né 0 né 1 né 2). Fino ad allora la mancata comprensione intuitiva del concetto non rendeva facile neppure decidere quali domande porsi sull’argomento.
Disegnare una figura di dimensione fratta, d’altra parte, richiede calcoli così laboriosi da rendere necessario l’uso di un programma.

3. La Programmazione serve per controllare o formulare congetture. La programmazione è anche un aiuto al lavoro di ricerca di un matematico. Supponiamo di voler dimostrare una congettura, del tipo: ogni intero, ogni reale, ogni funzione soddisfa una certa proprietà. Prima di dedicarvi molto tempo, è bene controllare che la congettura non si possa demolire facilmente. Per far ciò, è necessario cercare un intero, un numero reale o una funzione che non soddisfi la proprietà che si vorrebbe dimostrare. In altre parole, è necessario scegliere molti interi, o reali, o funzioni, e controllare se essi soddisfano la proprietà oppure no. Questo lavoro, se svolto a mano, consente di effetturare ben pochi controlli; se affidato a un programma, invece, ne consente milioni o miliardi, e diventa ben più attendibile.
Un programma, inoltre, può anche servirci a formulare una congettura. Immaginiamo di voler studiare la probabilità che due numeri interi, scelti a caso, siano primi tra loro (non abbiano divisori in comune, tranne +1 e -1). Possiamo scrivere un programma che consideri 100 milioni di coppie di numeri interi, e ci dica in quale percentuale essi sono primi tra loro.  Il programma ci risponderà: il 60,8 % (circa) delle coppie di interi sono prime tra loro. Ora spetta a noi congetturare qualche sia esattamente la  probabilità che due interi siano primi tra loro. Ogni congettura che faremo, tuttavia, dovrà essere in (ragionevole) accordo con i dati empirici. Solo per curiosità: la probabilità esatta che due interi siano primi tra loro si dimostra essere:
6/^2      =      0.60792710 …

4. Un programma può svolgere il ruolo di una prova. Infine, esistono prove matematiche (non molte, per ora) che sono in parte costituite da programmi. 

Un esempio è la congettura dei 4 colori: ogni carta geografica è colorabile con solo 4 colori, in modo che ogni regione abbia un solo colore, e che due regioni confinanti abbiamo  colori diversi. Si può dimostrare (Appel e Haken, 1976), che esiste un insieme di 633 cartine che è in certo senso “critico” per la congettura: se ogni carta dell’insieme è colorabile nel modo richiesto, allora tutte le infinite cartine possibili lo sono. Oppure, detto in un altro modo, se la congettura ha dei controesempi, almeno uno di essi si trova tra le 633 cartine.
Di conseguenza, per decidere se la congettura è vera o falsa, è sufficiente scrivere un programma che controlli tutte le colorazioni possibili con 4 colori per ognuna delle 633 cartine. Ogni cartina ha un numero molto grande ma tuttavia finito di colorazioni possibili. 
Se ognuna delle 633 cartine ha almeno una colorazione del tipo richiesto (con 4 colori, ogni regione ha un solo colore, due regioni confinanti hanno  colori diversi), allora la congettura dei 4 colori è vera non solo per le 633 cartine, ma per tutte le infinite cartine possibili. 
Se invece almeno una delle 633 cartine non ha una colorazione del tipo richiesto, allora la congettura dei 4 colori è ovviamente falsa (ha almeno un controesempio).
Scritto il programma, la congettura risulta vera. Non esiste, tuttavia, una prova matematica di questo fatto. Per essere più precisi: ogni prova nota della congettura dei 4 colori include, come parte ineliminabile di sé, il programma che controlla che tutte le 633 cartine abbiano almeno una colorazione del tipo richiesto. Anzi: la prima prova richiedeva un controllo ancora piú esteso: 1476 cartine.

Una situazione analoga si è ripetuta per la seguente congettura di  Keplero, provata nel 2002: “la disposizione di sfere di egual diametro nello spazio, che consente di occupare il massimo di spazio, si ottiene quando le sfere sono tangenti,  e quando i loro centri formano un reticolo tetraedrico.”
Questa congettura è stata provata di recente, ma anche in questo caso la prova del Teorema consiste nel definire un insieme di 5128 disposizioni di sfere,  insieme che contiene un controesempio alla congettura nel caso ne esista uno. Controllare che nessuno di tali possibili controesempi demolisca la congettura equivale quindi a provare la congettura stessa. Anche qui, con tempo si è riusciti a ridurre il numero di disposizioni da controllare (Nipkow ha di recente provato che è sufficiente controllare un insieme di 2771 disposizioni di sfere), ma anche cosí, provare la congettura di Keplero ancora oggi include, come parte ineliminabile di sé, un programma.

È possibile che in futuro le prove matematiche diventino sempre piú una combinazione di ragionamento umano e di ragionamento automatico (magari molto semplice, ma talmente esteso da non poter essere controllato da un essere umano).

Nome CORSO  Informatica I
SSD:……………………………………
Numero codice: M8507

1.Docenza

Docente: prof. Berardi
Dipartimento di Informatica
Tel.: 011 670 67 50
Fax:  011 751603
e-mail: stefano@di.unito.it

2.Finalità 
Insegnare a scrivere semplici programmi per risolvere problemi di calcolo matematico, e di raccolta e manipolazione di dati.

3. Obiettivi 
Apprendere parte del linguaggio di programmazione C: istruzioni di input/output, tipi, cicli for e while, definizione di funzioni.

 4. Pre-requisiti in ingresso e competenze minime in uscita

Pre-requisiti (in ingresso)
Una conoscenza della matematica a livello di scuola secondaria

competenze minime (in uscita) | Insegnamenti fruitori
Cicli e funzioni in C | Informatica II

5.  Metodologia didattica

La metodologia didattica impiegata consiste in:
•	Lezioni frontali (N.ore 2*13 = 26)
•	Pratica di laboratorio (N.ore 2*13 = 26): 
•	Esercitazioni teoriche (N.ore 2*13 = 13): 

6. Programma, articolazione e carico didattico

Argomento

Ore
Lez.

Ore
Esercit.

Ore Laboratorio

Totale Ore di Car. Didattico

1.	Variabili, constanti, I/O. | 2 | 1 | 2 | 5
2.	Istruzione IF, istruzioni composte, IF annidati, espressioni, variabili carattere, switch. | 2 | 1 | 2 | 5
3.	Istruzione FOR, incrementi e decrementi, fattoriale, istruzioni WHILE, DO-WHILE, operatore virgola, cicli annidati, salti condizionati e non, variabili in virgola mobile, operazioni in virgola mobile, zeri di una funzione. | 2 | 1 | 2 | 5
4.	Array,  esempi di array, inizializzazione di array, matrici, esempi di matrici. | 4 | 2 | 4 | 10
5.	Ricerche di un elemento in un vettore, ricerca completa, ordinamenti, ricerca binaria, fusione. | 2 | 1 | 2 | 5
6.	Stringhe, esempi di stringhe, funzioni predefinite su stringhe. | 4 | 2 | 4 | 10
7.	Funzioni,  concetto di sottoprogramma, in C, dichiarazione di una funzione, visibilità, istruzione RETURN, chiamata di una funzione, passaggio dei parametri, il tipo VOID, la scomposizione funzionale, gestione di una sequenza. | 6 | 3 | 6 | 15
8.	Preprocessore C,  direttive, #define, #include. (sezioni 8.4-8.10 omesse). | 2 | 1 | 2 | 5
9.	Puntatori,  definizione, array e puntatori, aritmetica dei puntatori, passaggio di parametri per indirizzo. (sezioni 9.5-9.7 omesse). | 2 | 1 | 2 | 5
Totale | 26 | 13 | 26 | 65

7. Materiale per lezioni e esercitazioni:
 Per preparare l'esame e' necessario aver svolto degli esercizi di C al calcolatore, o durante le esercitazioni, o al tutoraggio, oppure a casa. Per esercitarvi a casa, qualunque compilatore C va bene. Potete scaricare da http://www.di.unito.it/~stefano/devcpp4.zip da la versione in uso fino al 2006. Oppure potete trovare nel sito http://www.bloodshed.net una versione piu' aggiornata. L'aula informatica 1del Dipartimento di Matematica (a sinistra entrando in via Carlo Alberto 10 per lo scalone grande) e' a vostra disposizione quando non ci sono lezioni. Per segnalare malfunzionamenti, rivolgetevi al Prof. Baldi (ufficio nel Centro di Calcolo, a destra entrando per lo scalone grande).

8. Materiale didattico
Pagina Web del corso: http://www.di.unito.it/~stefano (seguire il link: Informatica I).
Il tesoi base consigliato per il corso è: 
Alessandro Bellini, Andrea Guidi: Linguaggio C, guida alla programmazione, Mc Graw-Hill, consultabile all'indirizzo web: http://www.hyperbook.it . 

9. Modalità di verifica/esame
·  E' necessario essere iscritti a Moodle per sostenere l'esame, scrivete al docente per sapere come fare. 
·  L'esame, riservato ai soli iscritti Moodle, consiste in un test scritto a risposta chiusa (da 0 a 10 punti); poi in 3 esercizi pratici, svolti al calcolatore , che richiederanno di scrivere delle procedure in linguaggio C (da -1 a 7 punti per domanda, dunque 21 punti al massimo). 
·  Il totale dei punti di: tests + 3 esercizi pratici (al massimo 10+7+7+7=31) da' il voto dello scritto in trentesimi, 31 vale come 30 e lode. Chi ha preso 28 oppure 29 oppure 30 puo' chiedere una domanda all'orale per alzare il voto. 
·  Argomenti di teoria richiesti all'Esame. Gli argomenti di teoria richiesti all'Esame sono: ricerca lineare e binaria, ordinamento bubblesort e per inserzione da destra, visibilita'' di variabili, gestione a stack delle chiamate di funzione/procedura .