Informatica
A.A. 2009/2010
Parte 1
Introduzione al corso
Corso A: Prof. Stefano Berardi http://www.di.unito.it/~stefano
Corso B: Prof. Ugo de’ Liguoro http://www.di.unito.it/~deligu
Una definizione ricorsiva:
“La curva di Peano”
1-Introduzione
Indice Parte 1:
Introduzione al corso
1. Matematica
e
Calcolo:
perchè
studiare la programmazione?
2. Programmazione e nuovi argomenti
della Matematica.
3. Problemi, algoritmi e programmi.
4. Un cenno sul programma del corso.
5. Struttura del corso: dettagli.
1-Introduzione
1. Matematica e Calcolo
Godfrey H. Hardy,
matematico
“Il matematico, come il pittore
ed il poeta è un creatore di
forme … Certi rami della
matematica applicata sono di
una bruttezza ripugnante, e di
una noia intollerabile.”
• E’ vero, la Matematica non è solo calcolo …
• … ma il calcolo serve al matematico, e non
solo al matematico applicato.
1-Introduzione
Di cosa tratta questo corso
• Il corso (nonostante il suo nome …) tratta
solo marginalmente di Informatica, ossia
della scienza dei calcolatori, e verte invece
sulla Programmazione, ossia sulle tecniche
per tradurre un algoritmo o un’idea in un
programma per calcolatori
Ma se voglio diventare un
matematico, a che mi serve
saper programmare?
1-Introduzione
La Programmazione serve per
fare i calcoli
• L’Analisi, la Geometria e molti campi della
Matematica richiedono calcoli lunghi e
complessi, che è meglio delegare alle
macchine.
• Come esempio, in questo corso vedremo un
programma che risolve i sistemi di equazioni
di 1o grado con il metodo Gauss-Jordan.
1-Introduzione
La Programmazione serve per
la grafica
•Attraverso la programmazione, è possibile
dare rappresentazioni grafiche di concetti
geometrici che altrimenti sarebbero molto
difficili da assimilare.
Tuttavia esistono dei
pacchetti già pronti, dotati di
programmi per tutto quanto
mi serve
1-Introduzione
Anche i software gia’ pronti
come i fogli elettronici …
Esempio di
interpolazione:
per calcolare i
valori di una
tabella …
1-Introduzione
… richiedono da noi un po’ di
programmazione .
Esempio di
interpolazio
ne: per
calcolare i
valori di una
tabella si
usa una
“Macro”,
ovvero un
semplice
programma.
1-Introduzione
Ecco un esempio di
una Macro in Excel
Questo e’ un
esempio di
macro Excel:
un programma
Visual Basic,
che deve
essere scritto
(o piu’ spesso,
scaricato e
poi
modificato)
da noi.
1-Introduzione
Altri esempi di
programmi di calcolo
Anche i
programmi di
calcolo…
… come Matlab e
Mathematica hanno propri
linguaggi di programmazione
1-Introduzione
2. Programmazione e nuovi
argomenti della Matematica
Tecniche studiate in programmazione, come le
definizioni per ricorsione, sono state usate anche
per definire figure di nuovo tipo, e hanno avuto un
ruolo nell’evoluzione dei concetti di area (la curva
di Peano) e di derivata (la curva di Koch).
la curva di Koch
la curva di Peano
1-Introduzione
Programmazione e nuovi
argomenti della Matematica
• Ci sono poi campi della matematica che si sono
sviluppati solo da quando i computers ci hanno
consentito di rappresentarli.
• Per esempio, la Teoria dei Frattali si e’
sviluppata solo da quando si sono scritti
programmi in grado di disegnare queste figure.
Il frattale di Maldenbrot
1-Introduzione
Programmazione e nuovi
argomenti della Matematica
Gli Automi Cellulari sono un modello della capacita’
di auto-organizzazione della vita. Lo studio degli
automi cellulari non sarebbe concepibile senza
scrivere dei programmi capaci di simularne
l’evoluzione
A lato, una tappa
dell’evoluzione di
un “Cyclic Cellular
Automaton”
definito da
Griffeath David
1-Introduzione
Programmi per formulare
e refutare congetture
• Un programma può servire per formulare
una congettura (di solito, non per trovare
la prova), o al contrario per refutare una
congettura (con certezza).
• Es. con quale probabilità due interi sono
primi tra loro? Una prova al calcolatore su
100 milioni di coppie interi direbbe: 60,8%
circa. Questa è la nostra prima congettura.
• Se studiamo il problema, possiamo poi
dimostrare che la probabilita’ esatta e’
6/2 = 0.60792710 … 1-Introduzione
Esistono dimostrazioni con
uso essenziale del computer
• Per dimostrare che ogni cartina geografica
può essere colorata con 4 colori in modo
che regioni confinanti per più di un punto
abbiano colori diversi, ci si riduce al
problema della colorabilità con 4 colori di
633 cartine (Appel e Haken, 1976). Ma per
controllare la colorabilità di queste ultime
dobbiamo scrivere un programma!
1-Introduzione
Esistono dimostrazioni con
uso essenziale del computer
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”
(vedi fig. qui sotto) Nel 2002 si e’ dimostrato che
congettura è vera se e solo se
vale nel caso di 5128 disposizioni
(poi ridotte a 2771). Il controllo
di queste ultime si fa scrivendo
un programma.
3. Problemi, algoritmi e
programmi
• Un problema di calcolo è definito da
una relazione ingresso/uscita
• Gli ingressi possibili si dicono istanze
• Un algoritmo è un metodo meccanico
di calcolo che associa un’uscita ad ogni
entrata.
• Un programma è la codifica di un
algoritmo in un opportuno linguaggio di
programmazione.
1-Introduzione
Dall’astratto al concreto
Non è ovvio come
tradurre
in
un
programma
concetti
matematici, e talvolta
neppure un algoritmo
1-Introduzione
Algoritmi e programmi
Un programma è la codifica di un algoritmo in un
opportuno linguaggio di programmazione. A sinistra
vediamo un algoritmo per il calcolo di ex, a destra la
sua codifica in un programma C++:
Sia data
un’approssimazione
di ex calcolata con la
formula:
n
n/i!
x

i =0
for (i=0, t=1;
i <= n; i++)
{t = t * x/i;
y = y + t;}
1-Introduzione
Linguaggi di programmazione
Un programma si codifica attraverso un
particolare linguaggio di programmazione1-Introduzione
Compilatori
Un programma scritto in qualche
linguaggio di
programmazione deve essere tradotto prima nel
linguaggio “assembly” del sistema operativo,
attraverso un processo detto di “compilazione”, poi
in un linguaggio detto “linguaggio macchina”.
Linguaggio di
programmazione
Linguaggio
assembler
total =
num1+num1;
ADD 20 20
24
Rappresentazione
binaria
00000010
10011000
10100000
1-Introduzione
00100000
La struttura dell’elaboratore
Anche se il programma che scriviamo noi e quello
in linguaggio macchina sono ormai distanti, è
utile sapere com’è fatto il calcolatore per dare
un significato alla nozione di “indirizzo di
memoria”, che usiamo per programmare. Sotto:
un’immagine dell’elaboratore.
In questo corso usiamo il
linguaggio C/C++
Usiamo il C/C++ perché:
• è un linguaggio “universale”, non legato
a particolari applicazioni;
• è molto usato nel calcolo scientifico,
dunque esistono numerose librerie;
• La maggior parte dei linguaggi di
programmazione
(come
Java)
esistente discende dal C/C++.
1-Introduzione
Tuttavia, lo scopo non è
imparare il C++ in quanto tale
Non è vero che per saper
programmare bastino una
buona cultura scientifica e
un manuale di un linguaggio
di programmazione. E non
basta impare le regole del
linguaggio
C++
per
imparare a programmare.
1-Introduzione
L’obbiettivo è imparare la
“logica dei programmi”
inizio
leggi a, b
true
stampa b/a
a0
false
Il vero obiettivo del corso
è impadronirsi della logica
dei programmi e delle
tecniche fondamentali
della programmazione.
stampa “indet. o imposs.”
fine
A sinistra: un “diagramma
di flusso” usato per
spiegare la logica di un
semplice programma
4. Il programma del corso
in 10 punti
1. Introduzione al corso (oggi).
2. La macchina di Von Neumann.
3. Variabili, espressioni assegnazioni
4. Controllo del flusso: programmazione strutturata.
5. Le funzioni
6. Strutture dati statiche: vettori e matrici
7. Iterazione
8. Memoria dinamica.
9. Tempo di calcolo
10. Ricorsione. Algoritmi “Divide et Impera”.
1-Introduzione
L’inizio: le variabili
Indirizzo
0x0064fddc
nome
x
int
tipo
Le variabili e le “assegnazioni” di valori a variabili
sono la base dei linguaggi basati su comandi (detti
anche “imperativi”), come il C++. Sopra: una
rappresentazione delle principali caratteristiche di
una variabile C++.
1-Introduzione
Organizzare un programma:
la programmazione strutturata
• Un modo di descrivere programmi molto brevi
sono i diagrammi di flusso.
• La programmazione strutturata sceglie i
diagrammi di flusso piu’ comuni e introduce dei
comandi che li rappresentano: if, for, while, …,
detti le strutture di controllo.
if … else,
for,
while
1-Introduzione
Le componenti di un programma:
le funzioni
• Un programma ben organizzato delega compiti
ripetitivi a parti specializzate che possono essere
eseguite molte volte: i sottoprogrammi
• Una funzione è un sottoprogramma che comunica
col resto del programma attraverso speciali
variabili dette “parametri”.
• Per imparare a programmare, è essenziale la
capacita’ di saper scomporre il programma in
funzioni, che possano essere usate senza
conoscere i dettagli di come sono state definite.
1-Introduzione
Un programma non scomposto in
funzioni spesso è illeggibile
main() { INPUT(&OK, X, Q, &N);
if (OK) {/* STEP 1 */
for (I=0; I<=N; I++) { /* STEP 2 */
Z[2*I] = X[I]; Z[2*I+1] = X[I];
Q[2*I+1][0] = Q[2*I][0]; /* STEP 3 */
if (I != 0)
Q[2*I][1] = (Q[2*I][0] - Q[2*I-1][0]) /
(Z[2*I] -Z[2*I-1]);}
/* STEP 4 */
K = 2 * N + 1;
Questo è un esempio di
for (I=2; I<=K; I++) Un programma caotico
for (J=2; J<=I; J++)
Q[I][J] = ( Q[I][J - 1] - Q[I - 1][J - 1] )/
( Z[I] - Z[I - J] );}
1-Introduzione
Lo stesso programma scomposto
in funzioni è più comprensibile
void ReadMatrix (Matrix M){…}
bool Quadrata (Matrix M){…}
real Det (Matrix M)
// pre: M e’ quadrata
// post: calcola il determinante di M
{…}
Questo è un esempio di
un programma meglio
int main()
organizzato
{ReadMatrix (M);
if (Quadrata(M) && Det(M) != 0)
real x = 1/ Det(M);
… }
1-Introduzione
Programmi = algoritmi + strutture
dati (citazione da N. Wirth)
• Raramente in un programma si manipolano
semplici numeri o caratteri: in generale
bisogna organizzare i dati in opportune
strutture dati, contenenti molti dati
collegati tra loro.
• La scelta delle strutture dati influenza la
definizione e l’efficienza degli dei metodi
di calcolo o algoritmi.
1-Introduzione
Strutture dati: come e’
organizzata la memoria
Sotto, una rappresentazione di un “vettore” di
numeri nella memoria del computer, attraverso celle
di memoria con indirizzi consecutivi
2 5 9 1
Più sotto, una rappresentazione degli stessi dati
attraverso celle di memoria aventi indirizzi non
consecutivi, ma collegate tra loro con una tecnica
che spiegheremo nel corso.
2
5
9
1 
1-Introduzione
Tempo di calcolo: come la
matematica studia l’efficienza
c g(n)
f (n)
n0
In che senso un programma è più efficiente di un
altro? Una risposta è che, a meno di costanti
moltiplicative, la funzione che ne esprime il tempo di
calcolo del primo programma cresce più lentamente
di quella che esprime il tempo di calcolo del secondo
programma, quando l’argomento tende all’infinito.
L’iterazione
Sotto: un’immagine della iterazione.
L’iterazione è un percorso lineare dai dati al
risultato, possiamo immaginarla come una strada
che percorriamo andando sempre avanti, un
passo dopo l’altro.
1-Introduzione
La ricorsione
Sotto: un’immagine della ricorsione.
La ricorsione utilizza un meccanismo di
semplificazione dei casi più complessi a casi
più semplici. I casi più complessi di un problema
vengono inizialmente “lasciati in sospeso”
finché non siamo in grado di risolverli partendo
1-Introduzione
dalla soluzione di quelli più semplici.
5. Struttura del corso nel
2010/2011
Corso teorico
in aula
4 ore settimanali
Mercoledi’ 11-13
Giovedi’ 09-11
dal 7 Marzo
Esercitazioni in
laboratorio
2 ore settimanali
Il Lunedi’ 11-13
a partire
dal 14 Marzo
Tutorato
2 ore settimanali
Il Lunedi’ 14-16
a partire
dal 28 Marzo
1-Introduzione
Il laboratorio
• Il laboratorio, che si svolgerà per 2
ore e per 11 settimane nelle aule
informatizzate il Lunedi’ ore 11-13,
farà uso del C++
• Alcuni esercizi faranno uso di
contesti, ossia di programmi con
“lacune”, forniti via web dal docente
e che lo studente deve completare.
1-Introduzione
C++ versus C
Chi conosce il C puo’ chiedersi perche’
abbiamo scelto il C++. Qualche risposta:
1. Il C++ include il C
2. Il C++ aggiunge al C caratteristiche di alto
livello (a cominciare da una migliore
gestione dell’Input/Ouput)
3. Il C++ estende il C con le “classi”. Questo
aspetto `e importante per chi continua lo
studio della programmazione, anche se in
questo corso non lo vedremo.
1-Introduzione
Il Dev-C++
• E’ obbligatorio scaricare e istallare il
wxDev-C++. Tutte le istruzioni si trovano
sul sito del corso (vedi oltre).
1-Introduzione
Un testo di consultazione
per il linguaggio C++
Il testo di consultazione per il C++ scelto per
il corso è
J. R. Hubbard,
Programmare in C++
2a ed.
McGraw-Hill 2001
È fuori stampa, ma dovreste
trovarlo usato.
1-Introduzione
In alternativa …
Un testo di consultazione
alternativo
La nuova versione dell’Hubbard è
Joyanes Aguilar Luis
Fondamenti di
programmazione C++
The McGraw-Hill Companies
È in stampa, di circa 600
pagine, ne usiamo la prima
metà.
1-Introduzione
Pagine web del corso nel
2010/2011
Tutto il materiale del corso (dispense,
compilatore, grafica, esercizi, registrazione
delle lezioni del 2009/2010 e se possibile di
quest’anno) puo’ essere trovato sul Web
all’indirizzo:
math.i-learn.unito.it
“Piattaforma”: MOODLE
Nome: Informatica 1 a.a. 2010/2011 (inf12011)
E’ OBBLIGATORIA L’ ISCRIZIONE
1-Introduzione
A MOODLE
Orario Corso del 2010/2011
Dal 7 all’11/03/2011 solo lezione:
1. 11-13 Lunedi’
Aula Magna
2. 11-13 Giovedi’
Aula Magna
3. 09-11 Venerdi’
Aula Magna
Dal 14/03/2010 al 04/06/2010 anche
laboratorio:
1. 11-13 Lunedi'
Laboratorio Aula 5
2. 11-13 Giovedi’
Aula Magna
3. 09-11 Venerdi’
Aula Magna
1-Introduzione
Modalità d’esame
• Test (max. 5 pt.): 10 domande da 0.5 pt. a
risposta chiusa. Minimo: 5 esatte (2.5 pt.)
• Esercizi (max. 20 punti): 4 programmi,
valgono 5 punti ciascuno se: (a) compilano
correttamente; (b) funzionano su esempi;
(c) soddisfano eventuali richieste extra.
Altrimenti 0 pt. Minimo: 2 esatti (10 pt.)
• Domanda scritta di teoria (max. 6 punti).
1-Introduzione
Test (max. 5 punti, min. 2.5)
Consiste di 10 domande a risposta
chiusa da 0.5 punti ciascuna
1. Alcune prese dal testo di Hubbard
(alla fine di ogni capitolo), ma per la
maggior parte …
2. ispirate dagli errori piu’ comuni degli
studenti dell’anno precedente.
1-Introduzione
Scritto (max. 20 pt., min. 10)
Consiste nello svolgimento di 4 esercizi, simili alle
esercitazioni fatte durante il corso. La valutazione
e’ sempre 0 o 5 pt.
real Exp_x (real x, int n)
// pre:
n intero >= 0
// post: calcola e^x con la formula …
{ /*codice da inserire dallo studente*/ }
Il “main” del programma contiene esempi su cui
provare il programma ed è sempre dato allo
studente. Il programma deve funzionare anche su
1-Introduzione
esempi non inclusi.
Domanda Scritta di Teoria
(max. 6 punti)
• Verte sul programma del corso,
programma che forniremo nella sua
versione definitiva a fine semestre.
• Il punteggio finale dell’esame e’ la somma
dei punti delle 3 prove, arrotondata per
eccesso: per esempio, 17.5 diventa 18 (la
sufficienza), mentre 17 o meno resta
insufficiente.
• 30.5 e 31 corrispondono a 30 e lode.
1-Introduzione
Tutorato
• Due ore alla settimana il Lunedi’ 14-16
dal 28 Marzo sono dedicate al tutorato
• Consiste nella discussione degli esercizi
svolti e/o nello svolgimento di ulteriori
esercizi, ed ha lo scopo di sostenere chi
ne ha bisogno
È facoltativo!
1-Introduzione
Domande?
1-Introduzione