Parte 2
Laboratorio di Informatica
Dott.ssa Elisa Tiezzi
Dott.ssa Elisa Mori
Laboratorio di Informatica
1
Definizione intuitiva di algoritmo
• Elenco finito di istruzioni che specificano una
serie di operazioni, eseguendo le quali e’
possibile risolvere ogni istanza di un problema
di un dato tipo
Laboratorio di Informatica
2
Proprietà degli algoritmi
• FINITI
• NON AMBIGUI
• GENERALI
Laboratorio di Informatica
3
Soluzione di ax2+bx+c=0
1. inizio dell’algoritmo;
2. acquisire dall’esterno i valori dei coefficienti a, b e c;
3. calcolare il valore b2-4ac;
4. se , allora non esistono radici reali: eseguire 8;
5. se , allora x1=x2=-b/2a: eseguire 7;
6. se , allora x1=(-b+)/2a e x2=(-b-)/2a;
7. comunicare all’esterno i valori di x1 ed x2;
8. fine dell’algoritmo.
Laboratorio di Informatica
4
Descrizione degli algoritmi
Diagramma a blocchi (flow chart):
rappresentazione grafica di un algoritmo
che indica il flusso delle trasformazioni
descritte dall’algoritmo che devono essere
eseguite a partire dai dati iniziali per
ottenere i risultati finali.
Laboratorio di Informatica
5
Blocchi elementari
input
azione
begin
falso
end
C
vero
output
Laboratorio di Informatica
6
Esempio su ax2+bx+c=0
begin
a, b, c
b2-4ac
V

F
x1=-b/2a
V

F
x1=(-b+)/2a
x2=(-b-)/2a
x2=-b/2a
x1, x2
radici c.c.
end Laboratorio di Informatica
7
Il gioco dei quindici
Quindici oggetti, ad esempio fiammiferi, sono su una
tavola. Il primo giocatore ne raccoglie 1, 2 o 3. Il secondo
giocatore ne raccoglie a sua volta 1, 2 o 3. Quindi è ancora
il primo giocatore a raccogliere 1, 2 o 3 fiammiferi. I
giocatori alternano le loro mosse finchè sul tavolo non
esistono più fiammiferi. Il giocatore che è costretto a
raccogliere l’ultimo fiammifero è il perdente.
Descrivere una strategia vincente per il primo giocatore
Laboratorio di Informatica
8
Problema delle dodici monete
Tra 12 monete di identico aspetto potrebbe nascondersene
una falsa e pertanto di peso diverso. Disponendo di una
bilancia a 2 piatti per confrontare gruppi di monete, si
vuole individuare la moneta falsa e stabilire se essa pesi
più o meno delle altre, mediante non più di 3 pesate.
Laboratorio di Informatica
9
Soluzione del gioco dei quindici
Siano A il primo giocatore e B il secondo
1. Prima mossa: A raccoglie 2 fiammiferi
2. Mosse successive: se B raccoglie k fiammiferi (k<=3),
allora A raccoglie 4-k fiammiferi
Laboratorio di Informatica
10
Soluzione del gioco delle monete
1, 2, 3, 4 : 5, 6, 7, 8
1L 2L 3L 4L
5P 6P 7P 8P
9L 10L 11L 12L
9P 10P 11P 12P
0
1, 2, 5 : 3, 4, 6
1L 2L 6P
1:2
1L 6P 2L
5P 3L 4L
7P 8P
7:8
1P 2P 3P 4P
5L 6L 7L 8L
1, 2, 5 : 3, 4, 6
5L 3P 4P
7L 8L
3:4
7:8
3:4
8P imp 7P 3L 5P
4L
9L 10L 11P
9:10
9L
9, 10 : 11, 1
4P 5L 3P 7L
12L 12P 0
12:1
1:2
2P 6L 1P
9P 10P 11l
9:10
11P 10L 12L 0 12P 10P 11L
Laboratorio di Informatica
imp 8L
1P 2P 6L
9P
11
Breve storia dei calcolatori
• Primi strumenti di calcolo meccanici
– Abaco
• 1600
– Pascal (somma e sottrazione)
– Leibniz (moltiplicazione e divisione)
• 1800
– Babbage (quadrato e stampa)
– Babbage (macchina analitica)
• Ada Augusta Lovelace (prima programmatrice)
– Schede perforate utilizzate nel 1890 (inizio di IBM)
Laboratorio di Informatica
12
• 1944
– Mark I (primo calcolatore elettromeccanico)
• 1946
– ENIAC
• 1949
– EDSAC (macchina di tipo Von Neumann)
• Anni successivi
– Stessa architettura ma tecnologia più avanzata
• 1960
– Internet (fine anni sessanta per esigenze militari, si
chiamava Arpanet)
• 1989
– www (word wide web: enorme enciclopedia)
Laboratorio di Informatica
13
Hardware
Pezzi fisici tangibili che supportano
l’elaborazione (chip di silicio, fili elettrici,
tastiera, dischi, stampanti….)
Software
I componenti hardware sono inutili se non
ricevono precise istruzioni. Un programma
è una serie di istruzioni che l’hardware
esegue in sequenza.
Laboratorio di Informatica
14
Componenti hardware principali
Organizzazione hardware
standard
• Dispositivi di input
– Ad es.: mouse, tastiera
• Dispositivi di output
– Ad es.: monitor, stampante
• Insieme in uno stesso
contenitore
Memoria
– Processore (CPU)
Dispositivi
di input
Processore
(CPU)
• Central Processing Unit
• Interpreta e esegue le
istruzioni
Dispositivi
di output
– Memoria
Laboratorio di Informatica
15
Due Tipi di Memoria
• Principale
– area di lavoro
– mantiene temporaneamente programmi e dati (mentre il
programma è in esecuzione)
• Ausiliaria
– permanente
– salva programmi e risultati
– Esempi: floppy & hard disk, CD, nastri
Laboratorio di Informatica
16
Organizzazione della Memoria
Principale
• Bit = una cifra binaria
– valori: 0 o 1
• Byte = 8 bit
• La memoria principale è
una lista di locazioni
numerate ciascuna di un
byte
• Il numero di byte
utilizzato per
memorizzare un dato
varia con il tipo di dato
Indirizzo
Dato
3021
1111 0000
3022
1100 1100
3023
1010 1010
3024
1100 1110
3025
0011 0001
3026
1110 0001
3027
0110 0011
3028
1010 0010
3029
…
Laboratorio di Informatica
Dato 1: 2 byte
Dato 2: 1 byte
Dato 3: 3 byte
Dato 4: 2 byte
Etc.
17
Organizzazione della
Memoria Ausiliaria
Radice
File
File
Directory
Directory
Directory
File
Directory
File
Directory
File
Directory
File
Laboratorio di Informatica
18
Programma
• Insieme di istruzioni che il calcolatore deve eseguire
Programma
Input
Calcolatore
Laboratorio di Informatica
Output
19
Tipi di Programmi
• Sistema Operativo
– Programma supervisore
• DOS, Windows, MacOS, UNIX, Linux
• Applicazioni esistenti
– word-processor/editor
– web browser
– compilatori o assembler
• Applicazioni create dall’utente
Laboratorio di Informatica
20
Informazione
Esistono due formati per memorizzare
l’informazione:
ANALOGICO
DIGITALE
L’informazione analogica è continua
e cresce proporzionalmente alla
sorgente di informazione
Es: termometro di mercurio, segnali
elettrici
Laboratorio di Informatica
La tecnologia digitale spezza
l’informazione in tanti pezzi
che rappresenta come numeri
Es: compact disc
21
I computer moderni sono digitali:
Ogni tipo di informazione è spezzato in
blocchi. Ogni blocco è rappresentato da un
numero e l’informazione è memorizzata sotto
forma di sequenza di numeri.
Il computer digitale memorizza l’informazione
sotto forma di numeri binari (base 2).
La singola cifra binaria si chiama bit (binary
digit). La base del sistema indica quante cifre
si hanno a disposizione e il valore posizionale
di ogni cifra in un numero.
Laboratorio di Informatica
22
Sistemi posizionali
Il sistema di numerazione decimale è basato
sull’alfabeto decimale {0,1,2,3,4,5,6,7,8,9} ed
ogni numero è rappresentato come sequenza di
simboli di tale alfabeto. Ad ogni simbolo è
associato un peso a seconda della posizione.
Es:
2863=2 x 103 + 8 x 102 + 6 x 101 + 3 x 100
Laboratorio di Informatica
23
In generale i sistemi numerici posizionali in base
b2 rappresentano ogni numero con m cifre in
base b:
N=cm-1…….c0
Dove i ci denotano elementi di un insieme di b
simboli che corrispondono ai primi b numeri
naturali 0…..b-1.
Vale N=∑cibi
Es:11002=1 x 23+1 x 22+0 x 21+0 x 20
Laboratorio di Informatica
24
Come comunicare
• Linguaggio macchina:
– sequenze di 0 ed 1
– rigoroso
– essenziale
• Linguaggio assembler:
– simbolico
– semplice traduzione aggiuntiva
• Linguaggio naturale:
– linguaggio preferito dall’essere umano
– ambiguo, ridondante, non preciso
• Linguaggio di programmazione ad alto livello
Laboratorio di Informatica
25
Storia Moderna
• PASCAL (1970)
• Programming in Logic (1971)
• C (1974)
• ADA(1980)
Laboratorio di Informatica
26
Storia Contemporanea
• C++ (1985)
• Java (1994)
Laboratorio di Informatica
27
Tipi di programmazione
• Funzionale
• Logica
• Procedurale
• Orientata agli oggetti
Laboratorio di Informatica
28
Traduttori
macchina
traduttore
programma
Codice in l.
macchina
macchina
dati
Codice in l.
macchina
Laboratorio di Informatica
risultati
29
Compilatori ed interpreti
• Compilatore
– programma che traduce un programma in
linguaggio ad alto livello in un programma in
linguaggio più semplice che il calcolatore può
eseguire (più o meno) direttamente.
• Interprete
– programma che traduce ed esegue una dopo
l’altra le istruzioni che compongono il
programma sorgente
Laboratorio di Informatica
30
L’approccio di Java
• Sia compilato che interpretato
• Codice intermedio: “Byte Code”
– codice a basso livello portabile
– simile al codice assembler ma indipendente
dall’hardware
– invisibile ai programmatori Java
• L’interprete traduce dal byte code in un programma nel
linguaggio macchina della macchina specifica
Laboratorio di Informatica
31
L’ambiente Java
Programma Java
Programmi precedentemente
compilati
Dati in input
Compilatore Java
Programma in
Byte-Code
Interprete
Esecuzione
Output
deldiProgramma
Laboratorio
Informatica Java
32