Lezione 1 - Dipartimento di Informatica

Lezione 1
Informatica e calcolatori
Mauro Piccolo
October 2, 2011
1 / 22
Informatica
⊲ Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
Trattamento automatico delle informazioni
Tre principali tematica
– La codifica delle informazioni
– Gli strumenti di trattamento delle informazioni
– La codifica del trattamento delle informazioni
2 / 22
Informazionie
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
⊲
Creazione, trasmissione e distruzione delle informazioni
Supporto fisico adeguato
Un supporto è adeguato se può assumere diverse
configurazioni
3 / 22
Claude Elwood Shannon (1916 - 2001)
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
⊲
4 / 22
Teoria delle informazioni
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
⊲
Misura della quantità di informazione immagazzinata da un
supporto
n
X
(pi log(pi ))
H=−
i=1
dove n è il numero di configurazione e pi è la probabilità che il
dispositivo assuma la configurazione i in un dato istante.
5 / 22
Un bit
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
⊲
Se il numero di configurazioni n = 2 e le due configurazioni
sono equiproblabili abbiamo |H| = 1 (base del logaritmo
=2).
Un bit è la quantità di informazione che può fornire un
supporto fisico che può assumere due configurazioni (0
oppure 1) che si manifestano in modo equiprobabile.
6 / 22
Origine delle macchine calcolatrici
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine
calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
⊲
Primi dispositivi di calcolo
– Abaco: le posizioni delle perline rappresentano numeri.
– Macchine basate sugli ingranaggi
⊲
⊲
Le posizioni degli ingranaggi rappresentano
numeri.
Blaise Pascal, Wihlem Leibnitz, Charles Babbage.
7 / 22
Un abaco
8 / 22
Primi dispositivi di memorizzazione dati
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi
di
memorizzazione
dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Schede perforate
– Usata da Joseph Jacquard (1801), per memorizzare le
fasi di un processo di tessitura.
– Memorizza i programmi della Macchina alle differenze
di Babbage.
– Molto popolare durante gli anni Settanta.
⊲
Posizioni degli ingranaggi
9 / 22
Primi computer
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
⊲
Basati su relé meccanici controllati elettronicamente.
– 1940: Stibitz ai Laboratori Bell
– 1944: Mark I: Howard Aiken e IBM ad Harvard
Basati su tubi a vuoto.
– 1937 - 1941: Atanasoff - Berry nello stato dell’Iowa
– 1940: Colossus: decodifica dei codici segreti tedeschi
– 1940: ENIAC: Mauchly e Eckert all’Università della
Pennsylvania.
10 / 22
Mark I
11 / 22
Personal Computer
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal
Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
All’inizio usati dagli hobbisti.
IBM cra il primo PC nel 1981
– Successo commerciale
– Il progetto dei moderni desktop si rifà a quello del PC
introdotto da IBM nel 1981
– Molti PC utilizzano software prodotto dalla Microsoft
⊲
12 / 22
Terminologia
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
⊲
Algoritmo: una sequenza di passi che definiscono il modo
in cui viene eseguita un’operazione.
Programma: la rappresentazione di un algoritmo.
Programmazione: il processo di sviluppo e codifica di un
programma.
Software: programmi e algoritmi.
Hardware: dispositivi fisici.
13 / 22
Un algoritmo per un trucco magico
14 / 22
Storia degli algoritmi
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli
algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Lo studio degli algoritmi ha avuto inizio in ambito
matematico.
Il termine deriva dal matematico arabo Muhammad ibn
Musa l-Khwarizmi
Primi esempi di algoritmi
– algoritmo di Euclide
– crivello di Eratostene
⊲
15 / 22
L’algoritmo di Euclide
16 / 22
Il crivello di Eratostene
P1
P2
-
P3
P4
-
P5
-
scrivere la lista dei numeri naturali a partire da 2 fino ad n
scegliere il numero setaccio ns come il numero più piccolo tra quelli
non ancora esaminati
cancellare tutti i multipli di ns dalla lista
se restano ancora altri numeri maggiori di ns e minori di n scegliere
come numero setaccio il più piccolo di questi e tornare a P3, in caso
contrario proseguire
stampare tutti i numeri ancora presenti nella lista
17 / 22
Il crivello di Eratostene (versione espansa)
P1
P2
-
P3
-
P4
-
P5
-
scrivere la lista dei numeri naturali a partire da 2 fino ad n
scegliere il numero setaccio ns come il numero più piccolo tra quelli
non ancora esaminati
(espansione) P3.1 definire il numero corrente nc come ns + ns
P3.2 se nc è minore o uguale ad n proseguire,
in caso contrario saltare al passo P4
P3.3 se esiste nella lista un numero pari ad nc
cancellarlo
P3.4 ridefinire il numero corrente nc come nc + ns
P3.5 tornare al passo P3.2
se restano ancora altri numeri maggiori di ns e minori di n scegliere
come numero setaccio il più piccolo di questi e tornare a P3,
in caso contrario proseguire
stampare tutti i numeri ancora presenti nella lista
18 / 22
Gli algoritmi
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
l’intelligenza di una soluzione è codificata nell’algoritmo
La descrizione formale di un algoritmo non ‘e semplice ne
scontata e pu‘o essere svolta con diversi livelli di
accuratezza
⊲
19 / 22
Il percorso del nostro studio
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
Teoria delle informazioni
– Algebra booleana e circuiti logici
– Codifica delle informazioni
Studio delle macchine calcolatrici
– Architettura degli elaboratori
– Il software di sistema
Algoritmi e programmazioni
– Introduzione a C++
⊲
20 / 22
Legge di Moore
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
⊲
21 / 22
Il futuro
Informatica
Informazionie
Claude Elwood
Shannon (1916 2001)
Teoria delle
informazioni
Un bit
Origine delle
macchine calcolatrici
Un abaco
Primi dispositivi di
memorizzazione dati
Primi computer
Mark I
Personal Computer
Terminologia
Un algoritmo per un
trucco magico
Storia degli algoritmi
L’algoritmo di
Euclide
Il crivello di
Eratostene
Il crivello di
Eratostene (versione
espansa)
Gli algoritmi
Il percorso del
nostro studio
Legge di Moore
Il futuro
⊲
Quali problemi ammettono soluzione algoritmica?
È possibile categorizzare la complessit‘a dei problemi,
individuando tra questi quelli che non ammettono
soluzione?
È possibile a partire da un insieme di conoscienze, trvare
soluzioni a problemi in modo automatico? In altri termini, è
possibile costruire algoritmi in modo automatico?
Come si pu‘o migliorare la ricerca e la descrizione degli
algoritmi? Quali tecniche e linguaggi si addicono
maggiormente alle problematiche del mondo reale?
22 / 22