giuseppina
trifiletti
un bit è una cifra binaria, (in inglese
"binary digit") ovvero uno dei due
simboli del sistema numerico binario
L’informatica
pervade le discipline
4
In che senso l'informatica
pervade le discipline ?
Forse perché tutte
utilizzano tecnologie
informatiche ?
La nostra idea
non è questa.
g. trifiletti
CHIEDE LA SFINGE A PITAGORA
Il pensiero,
la letteratura,
l'arte, ...,
la natura,
nascondono un cuore che
pulsa al ritmo di 0 e 1 ?
Oppure indossando
occhiali digitali
possiamo evidenziare
un cuore digitale ?
Gli occhiali digitali
potrebbero fornire un modo
di
guardare
il
mondo
più
efficace
di quelli utilizzati fino ad ora?
IL SIGNOR Q un uomo
più che discreto e …
densamente razionale,
pazientemente cerca …
Io dico che il
punto c’è.
Non lo vedo
ma ci
credo!!!
retta
numerica
cerca MISTER 
un tipo che
di discreto non ha nulla
ed è tutt’altro che razionale
Che cerchi
pure, io non
sono previsto,
dovrà
inventarmi

NON è un
numero razionale,
ma è irrazionale,
è un numero
reale
r=1
0
0

2
1 2 3
2 e 3 NON sono numeri
razionali, ma sono
irrazionali, sono ambedue
numeri reali
l’insieme dei numeri reali non è
numerabile, non è quindi possibile
metterlo in corrispondenza biunivoca
con i numeri naturali, R ha la potenza
del continuo
-3
-2
-1
0
1
2
3
0
1/16 1/8
1/4
1/2
2/3 5/6
11/12
1
Ci sono punti della retta a cui non corrisponde nessun
numero razionale, Pitagora e quelli della sua setta
rimasero folgorati da questa scoperta.
0
1 2 3
Di numeri irrazionali
ce ne sono infiniti altri …,
anzi ce ne sono molti di più
degli stessi numeri razionali

Questi non sono numeri razionali,
ma numeri irrazionali,
e occupano punti della retta.
MA È SORPRENDENTE!
È NUMERABILE
HA CARDINALITÀ
CIOÈ I NUMERI RAZIONALI SONO TANTI
QUANTI I NUMERI NATURALI !!!
CIOÈ
È
POSSIBILE
METTERE
IN
CORRISPONDENZA BIUNIVOCA, UNO A UNO,
I NUMERI NATURALI E I NUMERI RAZIONALI,
COME SEGUE:
"metodo diagonale" di Cantor
La numerabilità dei razionali
Il fatto che la cardinalità dei razionali sia la
stessa
degli
interi
è
abbastanza
sorprendente,
in quanto si è passati da un insieme
"discreto", cioè con punti staccati uno
dall'altro,
ad un insieme denso, cioè con la
caratteristica
che
tra
due
numeri
qualunque ce ne sono sempre infiniti.
L’ IPOTESI DEL CONTINUO
Cantor ipotizzò che non esistesse nessun
insieme con una cardinalità intermedia
compresa fra quella di ℕ e quella di ℝ
(ipotesi del continuo).
a
segue
immediatamente
Così come i numeri naturali rappresentano il
primo livello di infinito, i numeri reali
rappresenterebbero, secondo tale ipotesi, il
livello immediatamente successivo.
CANTOR E L’INFINITO ATTUALE
TANTI DIVERSI INFINITI, ANZI,
INFINITI TRANSFINITI
Così come i numeri naturali rappresentano il primo livello
di infinito, i numeri reali rappresenterebbero, secondo tale
ipotesi, il livello immediatamente successivo.
Ma ci sono infiniti altri infiniti, basta fare l’insieme delle
parti dell’insieme infinito e si aumenta di un grado l’infinito
Così, ad esempio, il "numero" dei naturali è differente da
quello degli insiemi di naturali e poi da quello degli insiemi
di insiemi di naturali e così via, in un procedimento senza
fine che produce infiniti sempre nuovi.
I reali sono tanti quanti i sottoinsiemi dei naturali
I fisici hanno paura degli
universi discreti e basano
le loro teorie sul continuo
e sulla simmetria
Gli universi discreti sono
molto più complicati degli
universi continui
il continuo nasce dai numeri
naturali con una serie di passi
che
conducono
percorso
postulato:
alla
fine
del
di
un
postulato
di
all’aggiunta
il
continuità della retta
Al di là dei più appariscenti sviluppi
tecnologici,
la
valenza
culturale
dell’informatica si evince dalle sue
potenzialità nel favorire il dialogo fra
scienze esatte e scienze umane
L’Informatica non ha solo un valore
tecnologico-strumentale, ma anche un
valore scientifico e culturale autonomo.
Fornisce una prospettiva sul mondo e
una
chiave di
lettura
della
realtà
originale e irriducibile a quelle fornite
dalla fisica, dalla matematica e dalle
altre scienze.
DIO HA FATTO I NUMERI
NATURALI
TUTTO IL RESTO È
OPERA DELL’UOMO
KRONECKER
Leopold Kronecker (7 dicembre 1823, Liegnitz, Prussia
/ Legnica, Polonia - 29 dicembre 1891, Berlino),
matematico e logico tedesco, noto per la sua
convinzione che l'analisi potesse essere interamente
fondata sui numeri interi, convinzione che viene bene
rappresentata dal suo noto aforisma: "Dio fece i numeri
naturali; tutto il resto è opera dell'uomo".
Questo atteggiamento pose Kronecker in conflitto con
alcune delle estensioni della nozione di numero e della
matematica introdotte da Georg Cantor.
Kronecker, che pure era stato il maestro di Cantor
durante i suoi studi universitari a Berlino, ne rifiutò le
scoperte: "il lavoro di Cantor sui numeri transfiniti e
sulla teoria degli insiemi non è Matematica, ma
misticismo" ed aggiungeva, come già ricordato, che "i
numeri interi positivi sono i soli creati da Dio; tutto il
resto è opera dell'uomo e quindi sospetto".
Altri grandi matematici apprezzarono invece l'opera di
Cantor e la accolsero con entusiasmo. David Hilbert
definiva la teoria dei cardinali "un prodotto sbalorditivo
del pensiero umano" e commentava: "nessuno riuscirà
mai a cacciarci dal paradiso che Cantor ha creato per
noi"
l’informatica si fonda sui
NUMERI NATURALI
trasforma tutto in numero
utilizza la base 2,
solo 0 e 1
La programmazione è un buon medium
per riuscire ad esprimere idee confuse
mal formulate nella forma di metodi chiari
ed efficaci.
marvin minsky
gulp!?!
Trova il
maggiore e il
minore di N
oggetti
diversi, ma
con il minor
numero di
passi!
Rendiamo espliciti i
procedimenti semi-consci
il
nostro
cervello
risolve
automaticamente ogni giorno molti
problemi ma con meccanismi che non
sono completamente consci e quindi
non espliciti:
cercare di far risolvere al computer gli
stessi basilari problemi ci consente
quindi di capire come il nostro cervello
svolge molte funzioni
I problemi proposti sono tutti impostati
sul confronto di oggetti differenti: si
presupponeva di avere otto oggetti
differenti e di avere a disposizione
soltanto una bilancia a due piatti,
senza pesi, per confrontare gli oggetti.
ESPLOSIONE
dell’
informazione
contenuta
in un
confronto
1. Trovare il maggiore tra un insieme
di otto numeri diversi.
2. Trovare il più grande e il più piccolo
tra un insieme di otto numeri
diversi.
3. Trovare i due numeri più grandi tra
un insieme di otto numeri diversi.
1. Presentazione del problema;
2. Analisi del problema e sviluppo di
un algoritmo risolvente;
3. Ottimizzazione dell’algoritmo;
4. Analisi del numero dei confronti in
funzione del numero dei dati;
5. Domanda conclusiva: si può fare
meglio?
Trovare il più grande numero in un
insieme di otto numeri diversi,
potendoli soltanto confrontare a due a
due.
Si può procedere confrontando tutti i
numeri fra di loro ma così avremmo una
sovrabbondanza
di
informazioni
inutilizzate.
Quelli che seguono sono i due alberi
che schematizzano due algoritmi
risolventi ottimali.
ALGORITMO OTTIMALE 1
ALGORITMO OTTIMALE 1
T
O
R
N
E
O
D
I
A
R
T
I
M
A
R
Z
I
A
L
I
OPPURE TORNEO DI TENNIS
Trovare il più grande e il più piccolo
numero in un insieme di otto numeri
diversi, confrontandoli a due a due.
a sinistra procedono i perdenti
P
V
a destra solo i vincenti
Però
così
sovrabbondanza
inutilizzate:
avremmo
una
di
informazioni
dai primi quattro confronti infatti
sappiamo già qual è il maggiore e il
minore di ogni coppia iniziale;
questa informazione ci consente quindi
di eliminare i primi quattro confronti a
sinistra che sono inutili.
ALGORITMO OTTIMALE 2
P
perdenti
V
vincenti
Trovare i due numeri più grandi in un
insieme di otto numeri arbitrari,
potendoli soltanto confrontare a due
a due
Se il maggiore
fosse 
S
V
ALGORITMO OTTIMALE 3
Se
=
V
V
S
Un torneo con 8 tennisti
Il confronto avviene a due a due
Se si desidera trovare solo il
vincitore non serve tenere conto di
coloro che perdono, ma solamente
di coloro che vincono al primo
turno, al secondo turno, al terzo
turno, quello finale. In tutto 7
confronti.
Se si desidera trovare anche il
peggiore, bisogna tenere conto di
coloro che hanno perso al primo
turno per poi confrontarli a due a
due come si fa per i vincitori. In
tutto 10 confronti: 7 per il migliore
più 3 per trovare il peggiore tra i
quattro che hanno perso al primo
turno.
Se si desidera trovare il primo e il secondo
più bravi, bisogna ad ogni turno tenere conto
non solo dei vincitori, ma anche di coloro che
hanno perso, e con chi hanno perso, in modo
tale che, una volta trovato il vincitore, si
possano confrontare tra di loro gli unici
perdenti che possono aspirare al secondo
posto: coloro che hanno perso con il
vincitore. In tutto 9 confronti: 7 confronti per
trovare il migliore più 2 per trovare il migliore
tra i tre che hanno perso con il vincitore nei
tre turni per le selezioni.
E se il numero di oggetti è 15
(nei nostri esempi gli oggetti sono
partite)
quale sarà il minor numero di
confronti nei tre casi esaminati?
E se il numero di oggetti è N
(nei nostri esempi gli oggetti sono
partite)
quale sarà il minor numero di
confronti nei tre casi esaminati?
PRIMO PROBLEMA
N-1
SECONDO ROBLEMA
1. per N pari 3/2*N-2
2. per N dispari 3/2*(N-1)
TERZO PROBLEMA
N-1+log2N-1
log2N pprossimato per eccesso
Perché non si può
fare meglio?
Preziosi
consigli
alla nonna
Appunti tratti da
Progetto SeT
Università di Udine e Liceo Copernico
Scarica

NUMERI e ALGORITMI - matematica-informatica