1 Storia degli Algoritmi ovvero dal sasso al microcircuito integrato ovvero dal sasso al...
175
1 Storia degli Algoritmi ovvero dal sasso al microcircuito integrato Fara Martuscelli Fara Martuscelli Liliana Murino Liliana Murino Storia dell’Informatica e del Calcolo Automatico Prof. ssa F. PERLA
-
Upload
alessa-d-alessio -
Category
Documents
-
view
220 -
download
3
Transcript of 1 Storia degli Algoritmi ovvero dal sasso al microcircuito integrato ovvero dal sasso al...
1
Storia degli AlgoritmiStoria degli Algoritmi
ovvero dal sasso al microcircuito
integrato
ovvero dal sasso al microcircuito
integratoFara MartuscelliFara MartuscelliLiliana MurinoLiliana Murino
Storia dell’Informatica e del Calcolo Automatico Prof.ssa F. PERLA
2
Lo spirito dell’Aritmetic
a guarda dall’alto la
disputa fra i nuovi
“algorists” che operano con numeri
scritti e i tradizionali “abacists” con i loro
pallottolieri 1504
al-Khwarizmi
algebra al-Jabr
algorismsalgorismusalgorithmus
Non tutti sanno che …
3
Molti considerano l’Aritmetica una cosa banale che i ragazzi imparano e i computer eseguono, ma scopriremo che l’Aritmetica è un argomento affascinante dalle molte interessanti sfaccettature. […] Il modo in cui facciamo aritmetica è strettamente legato al modo in cui rappresentiamo i numeri che trattiamo.
Donald Knuth
Le operazioni aritmetiche hanno origine da esigenze di tipo economico (Divisione Sumera). Gli algoritmi per le operazioni aritmetiche dipendono dai sistemi di numerazione.
Algoritmi per le Operazioni Aritmetiche
L’uso della scrittura evita la ripetizione delle stesse operazioni (Babilonesi e Egiziani - Inverso, Duplation, Mediation). Diversi strumenti sono stati utilizzati, in epoche e luoghi diversi, a supporto dei calcoli (Divisioni – Arco Pitagorico e Abaco Cinese; Moltiplicazione – Tabelle, Napier’s bones). Rappresentazione delle frazioni in notazione decimale (Moltiplicazione – Simon Stevin). Operazioni aritmetiche con numeri binari (Leibniz).
4
2500 a.c. Divisione Sumera
Le tavolette numeriche (trovate a Shuruppak) riguardano lo stesso problema, ovvero la suddivisione del grano di un granaio fra un certo numero di persone in modo tale che ogni persona riceve 7 silà di grano.
1 granaio = 2400 gur e 1 gur = 480 silà
Sulle tavolette non c’è traccia del metodo utilizzato, però i risultati ottenuti sono diversi …
Tavoletta 671
2400/7
342 (con resto 6 ignorato)
342 x 480 = 164160
Tavoletta 50
1.152.000/7
164571 con resto 3
5
(2000-1650) a.c. Calcolo degli inversi Questo algoritmo compare su una tavoletta babilonese (VAT 6505).
Calcola l’inverso di y, y.Moltiplica y per z, otterrai t. Aggiungi 1, otterrai u.Calcola l’inverso di u, otterrai u.Moltiplica u per y. Otterrai v.
Dato un numero x
L’inverso del numero x è v
Calcola l’inverso di 10, 6.Moltiplica 6 per 4, otterrai 24. Aggiungi 1, otterrai 25.Calcola l’inverso di 25, otterrai 2;24.Moltiplica 2;24 per 6. Otterrai 2;24.
Dato un numero 4;10
L’inverso di 4;10 è 2;24
6
(2000-1650) a.c. Algoritmi aritmetici
Gli algoritmi egiziani Duplation e Mediation sono estratti dal Rhind Papyrus.
23
15
130
1
23
110
130
2 1
12
110
4 3
15
8 7
2 = (1 + 1/5 + 1/10) + (2/3 + 1/30)
= 9(7 + 1/5) + (1 + 2/3 + 1/10 + 1/30)
14
128
1
18
156
116
1112
12
12
12
3
14
14
12
Totale
41 1 1
2
7 1
Totale 12
x 10x (2 + 23)
Rhind Papyrus
7
Tabelle di Moltiplicazione
Arabia (13° sec., Ibn al-Banna; 15° sec. al-Kashi) Cina (1450, Wu Jing) – India … - Europa (1300 in Inghilterra 1478 (Treviso) e 1494, Luca Pacioli,Gelosia; 1617, Napier; 1885, Lucas-Genaille)
8
M.E.Algoritmi Aritmetici: Ottimizzazioni
I Metodi di Moltiplicazione Translation e Semi-Translation (Ibn al-Majdi) compaiono già in alcuni manoscritti del MedioEvo (riduzione del numero di passi elementari distinti per eseguire un calcolo aritmetico).
1 2
3 481
9
4 3 8
4 3 8
2571
42
8 4 41 9 1 8
3 2
4 3 8
4 3 8
42
3 481 8
46
4 3 8
4 3 8
1 6
3 2
2571
1 2
Passo 1: moltiplica le cifre della seconda linea (moltiplicando) per 4 e metti i risultati, uno sopra l’altro, nella giusta posizione, quindi aggiungi questi prodotti per ottenere il numero 1752 nella linea in alto.
Passo 2: sposta il moltiplicando di una posizione a destra, scrivi il risultato intermedio 1752 sopra, nella giusta posizione, e ripeti la moltiplicazione, questa volta moltiplicando il numero sotto (moltiplicando) per 3.
4 41 9 1 8
1 6
9
42
. 834 .
46
46
84
8
6
Passo finale: addiziona i termini di ciascuna colonna sopra il numero 348, ottieni 191844
Passo 1: calcola a2 e mettilo nella giusta posizione 4 x 4 = 16
Passo 2: calcola 2a e 2ab; metti 2a = 2 x 4= 8 sotto il numero 438 e 2ab = 8 x 3 = 24 sopra 348 nella giusta posizionePasso 3: calcola b2 = 3 x 3 = 9 e 2ac = 8 x 8 = 64Passo 4: calcola 2b = 2 x 3 = 6 e 2bc = 6 x 8 = 48Passo 5: calcola c2 = 8 x 8 = 64
Passo 3: sposta il moltiplicando nuovamente di una posizione a destra, e ripeti il passo 2.
TRASLAZIONE
Passo 1: moltiplica le cifre della seconda linea (moltiplicando) per 4 e metti i risultati, uno sopra l’altro, nella giusta posizione, quindi aggiungi questi prodotti per ottenere il numero 1752 nella linea in alto.Passo 2: sposta il moltiplicando di una posizione a destra, scrivi il risultato intermedio 1752 sopra, nella giusta posizione, e ripeti la moltiplicazione, questa volta moltiplicando il numero sotto (moltiplicando) per 3. Passo 3: sposta il moltiplicando nuovamente di una posizione a destra, e ripeti il passo 2.
SEMI-TRASLAZIONE
Passo 1: calcola a2 e mettilo nella giusta posizionePasso 2: calcola 2a e 2ab; metti 2a sotto il numero x e 2ab sopra x nella giusta posizionePasso 3: calcola b2 e 2acPasso 4: calcola 2b e 2bcPasso 5: calcola c2
Passo finale: addiziona i termini di ciascuna colonna sopra il numero x
x2=10000a2+10002ab+100(b2+2ac)+102bc+c2
9
Start 1008
180 10=
+
1200. Semplice Divisione per differenze
Questo algoritmo compare in un manoscritto del 1200, tradotto da Michel Chasles nel 1843.
101
8
9
2
102 100
8
9
2
1 8
8
1
2
1
2
1808
900 90=
+
208
100 10=
+
48
20 2=
+
Si definiscono due tipi di numeri: digits e articles. L’algoritmo si applica solo nei casi in cui i divisori sono digits e i dividendi sono articles. (900 : 8)
a.10n-1+(a(10-d)+b).10n-1+k
d
10 – d
d
dividendiquozienti
1. Aggiungi il quoziente parziale a.10n-1 nella 4a riga
2. Metti nella 3a riga il nuovo dividendo, ovvero a.(10-d).10n-1
8
1
2
1
8
1
2
1
4
2
10
1592.Divisione sull’Abaco Cinese Algoritmo di divisione per 7, Suanfa tongzong. (1234:7)
(1) sette-uno? + tre nella pos. inferiore
(7) >= sette? + uno nella pos. superiore
(2) sette-due? + sei nella pos. inferiore
(3) sette-tre? quattro resto due
(4) sette-quattro? cinque resto cinque
(5) sette-cinque? sette resto uno
(6) sette-sei? otto resto quattro
11
1585.Numeri scritti come Decimali
Simon Stevin introduce un metodo di scrittura dei decimali, eliminando le frazioni (La Disme- Definizioni II, III e IV) e fornisce un algoritmo per moltiplicare numeri decimali (La Disme-Proposizione III) .
1 23 7 5 93 4 310
7
100
5
1000
9
10000
3759
10000
(0) (1) (2) 32 5 7 89 4 6
195 4 2 1302 8 29313 26056
29137 1 2 2 (0)(1)(2)(3) (4)
0 364
unità, primo, secondo, terzo, quarto,
…
12
1703.Aritmetica Binaria
G. W. Leibniz scrive (The explanation of binary arithmetic) che secondo la leggenda cinese, il re Fohy (Fu Xi) introdusse la figura delle otto Cova che consiste di alcuni diagrammi con una forma particolare.
?0 1 2
Vantaggi dell’aritmetica binaria.
13
I Quadrati Magici
(1) Scoperto nel 1956
Inciso su placca di ferro con
numeri arabi - del periodo dei
Mongoli
(2) Diagramma del fiume Luo -
della dinastia dei Song (960-1279)
Arabi (13°-14° sec.) Bizantini (14° sec.) Europei (17° sec.)
Melancholia di Albert Durer – incisione su legno del 1514
Metodo di Moschopoul
os
Cornici
Marcatura delle celle
13°-17° sec.
14
13°sec. Quadrati con Cornici
Algoritmo di riempimento delle celle, cornice per cornice, (az-Zinjani).
1
46
2 3
7
4 5 6
121110 9 8
41 42
40
48 47
43 3839
49
44 45
1314
1516
171819 2035
32
3130333637
34
2122
2324 28
26272925
1a cornice
2a cornice
3a cornice
4a cornice
S7 = 7(49+1)/2 = 175
15
1 2 3 4 5 7 6 8 9
11 12 13 14 15 17 16 18 19
10
20
21 22 23 24 25 27 26 28 29 30
31 32 33 34 35 37 36 38 39 40
41 42 43 44 45 47 46 48 49 50
51 52 53 54 55 57 56 58 59 60
61 62 63 64 65 67 66 68 69 70
71 72 73 74 75 77 76 78 79 80
81 82 83 84 85 87 86 88 89 90
91 92 93 94 95 97 96 98 99 100
Le Cornici di Arnauld
Un quadrato magico con le cornici rimane un quadrato magico quando una o più delle sue cornici vengono rimosse.
1 2 3 4 5 7 6 8 9
11 12 13 14 15 17 16 18 19
10
20
21 22 23 24 25 27 26 28 29 30
31 32 33 34 35 37 36 38 39 40
41 42 43 44 45 47 46 48 49 50
51 52 53 54 55 57 56 58 59 60
61 62 63 64 65 67 66 68 69 70
71 72 73 74 75 77 76 78 79 80
81 82 83 84 85 87 86 88 89 90
91 92 93 94 95 97 96 98 99 100
e
e’
è
ò
o’
baw o
y
9 2
8
40
1
4 41 10 11 50 96 95
3
7
20
71
80
31
9060
93
21
61
100
70
30
98
99 92
81
51 97 5 6 9194
12
88 14
86 85 19
17
22
83
79
32
42
52
84 18
89
29
62
161587
59
1382
72
69
49
39
33 74 48 28 77 43
78
25
63
26
682473532758
75
38
76
23 64 36 35 67
44
66 65 37
54
34
57
47 55 56
45 46
1 2 3 4 5 7 6 8 9
11
10
20
21 30
31 40
41 50
51 60
61 70
71 80
81 90
91 92 93 94 95 97 96 98 99 100
e e’
è ò o’
o
b
y
a
w
11
50 10
41
1
40
2 9
8
3
1667.
16
14° sec. Marcatura delle Celle Ibn Qunfudh identifica 4 tipi di quadrati e relativi algoritmi.
Quadrati con n celle dove n è divisibile per 4.
In ogni riga [colonna] metà celle sono marcate e metà sono smarcate.
14
67
1011
3 1316
5 8
9 12
15
2
14
17
14° sec. Procedimento per 2 e per 3 Manuel Moschopoulos descrive due algoritmi. Il primo è relativo alla costruzione di un quadrato magico di ordine dispari (due versioni: procedimento per 2 e per 3; procedimento per 3 e per 5). Il secondo è relativo a quadrati magici di ordine divisibile per 4 (tecnica marcatura delle celle di Ibn Qundfudh).
1 1
2
1
2
3
1
2
3
4
1
2
3
4
5
1
2
3
4
5
6 1
2
3
4
5
6
7
1
2
3
4
5
6
7
9
8
18
Claude-Gaspard Bachet de Méziriac E’ una variazione dell’algoritmo di Moschopoulos. Dei piccoli quadrati vengono aggiunti ai lati di un quadrato ABCD da riempire; quindi si inseriscono i numeri in ordine lungo le diagonali (1,2,3,4,5; 6,7,8,9,10; …). A B
C D
1612.
19
Metodi della Falsa PosizioneA number must be chosen in which the proposed parts appear whole and this is to avoid fractional numbers, and not because it could not just aswell be done with another number but with more difficulty.Francès Pellos
Compendion de l’abaco, 1942
A lance has a half and a third in the water and 9 palms outside. I ask you how long is it? x – 1 x – 1 x = 9
Francès Pellos – 19422 3
Sono algoritmi che usano un valore numerico per l’incognita per risolvere un problema. La loro origine è ancora incerta. La loro storia attraversa molti secoli e molte civiltà.Si distinguono in: Metodo semplice (un solo valore numerico) e Metodo doppio (due valori numerici).
La scelta del valore numerico (falsa posizione) è importante soprattutto per evitare problemi con le frazioni.
Babylonian Tablet
20
1800 a.c. Mesopotamia UNA FALSA POSIZIONE UNA FALSA POSIZIONE
GEOMETRICAGEOMETRICA
Questa tavoletta mostra “chiaramente” l’uso di un algoritmo di falsa posizione per la risoluzione di un problema geometrico.b
l
d
l2 b2+ = 40d =
b = l – l/4 e
b = ? l = ?
l0 = 1 o [60]
l0/4 = 15
b0 = l0 – l0/4 = 45 l02
= 1 o [602]
b02 = 452 = 2025 33;45
b0
2l02+ = 5625 1;33;45d02 =
= 75 1;15d0 = +l02 b02+
d/d0= 1/75 = 48/602 48
d x (1/d0) = 40 x (48/602) = 32/60 32
l = l0 x (d/d0) = 60 x (32/60) = 32
b = b0 x (d/d0) = 45 x (32/60) = 24
3224
b = kl
l2 b2+ = 40d =
l 1 + k2 = d
l/l0 = b/b0 = d/d0
l = l0 x (d/d0) e b = b0 x (d/d0)
21
1800 a.c. Egitto - Rhind Papyrus
I principali testi matematici dell’antico Egitto: Kahun Papyrus, Moscow Papyrus e Rhind Papyrus (problema 26).
x + 1 x = 15 4
x’ = 4
b’ = 5 b/b’ = 15/5 = 3
x = (b/b’) x’ = 3*4 = 1212 + 3 = 15
22
(206 ac-220 dc) Cina – Jiuzhang Suanshu Il capitolo 7 della “bibbia” cinese dell’aritmetica contiene il primo algoritmo sul metodo del doppio errore, o ying bu zu shu (problemi 18 e 19). 9x = 11y
x1 = 3
(10y + x) – (8x + y) = 13 (liang)
y1 = 2 + 5/11
x2 = 2 y2 = 1 + 7/11
e1 = 12/11 – 13/16 = 49/16*11 jin
13 liang = 13/16 jin
e2 = 13/16 – 8/11 = 15/16*11 jin
x = x1*e2 + x2*e1/e1 + e2 = 143/64 jinx = 2jin + 15/(16*4)jin = 2jin + 3/16jin +18/(16*24) jin = 2jin 3 liang 18 zhu …
1 jin = 16 liang e 1liang = 24 zhu
“9 gold coins weigh as much as 11 silver coins. If, in each pile, one gold coin is replaced by a silver coin, and conversely, the gold pile becomes lighter by 13 liang. How much do a gold and silver coin weigh respectively?”
23
12°secolo. India – Bhaskara Nel capitolo 3 del suo libro Lilavati, il matematico Indiano Bhaskara tratta il Metodo semplice che chiama ista karma (operazione con un numero fissato). 1/10[5x - 1/3(5x)] + 1/3x + 1/2x + 1/4x =
70 - 2
x1 = 3 b1 = 17/4
“What is the number, which multiplied by five, and having the third part of the product subtracted, and the remainder divided by ten, and one-third, a half and a quarter of the original quantity added, gives two less than seventy?
ax = b
ax1 = b1
x = b*x1/b1 = (3*68)/17/4
24
9°secolo. Arabia – Qusta Ibn Luqa Il matematico arabo Qusta Ibn Luqa è stato il primo a fornire una dimostrazione geometrica del metodo del doppio errore.
ba g
i
d
k
oszm
c
h
l
n
t
u
x
x”
x’
b
b’
b–b’
b”
b–b” addo
aggt
abbh
= =xb
x’b’
x”b”
= =
x =
area del rettangolo con diagonale ci
lunghezza del segmento cn
= x’ e” – x” e’e” – e’
t
25
13°secolo. Il Metodo della Bilancia Il matematico arabo Ibn al-Banna inventò una tecnica grafica per sviluppare il metodo del doppio errore.
x’ e” – x” e’
e” – e’
errori per eccesso
e” e’
x” x’
b
e”
e’
x” x’
b
errori per difetto
x’ e” – x” e’
e” – e’
e’ per eccesso, e” per difetto
e” e’x” x’
b
x’ e” + x” e’
e” + e’
x =x’(ax’) + (b - ax’)x’
ax’
26
1202. Fibonacci – Regola Elchatayn In Liber Abaci (capitoli 12 e 13) Fibonacci spiega la regola Elchatayn o regola dei due errori.
e”x – x”
5 livres 3 livres
12 deniers
x” – x’
e’ – e”
3*122 sous + 5( )deniers = 7
+2 sous +
( )51 deniers
x” - x’x
= e’ – e”
x” + e”
differenza delle moltiplicazioni
85
3
1 2
less less
16sous
3sous
13
differenza degli errori
1 livre = 20 sous 1 sou = 12
deniers
27
1460. Francès Pellos REGOLA DEL TRE E FALSA POSIZIONE REGOLA DEL TRE E FALSA POSIZIONE
SEMPLICESEMPLICE
In Compendium del l’abaco viene usato il Metodo semplice per sviluppare la regola del tre applicata ai numeri frazionari.
3 + 1 2
3 + 1 2
8 + 1 2
1
28 + 1 6
4 + 1 3
6 + 1 2
==
REGOLA DEL TREREGOLA DEL TRE
14. 3 + 1/2
2= 49/2 = 24 + 1/2
3 + 1 2
x 7
=
14 x’ = b’ = 2
ax’ = b’ x =?
28
1583. Christophore Clavius
In Epitome Arithmaticae Practicae Clavius (capitoli 12 e 13) usa il Metodo del doppio errore per risolvere sistemi di equazioni lineari.
x + 73 = 2(y+z)y + 73 = 3(z + x)z + 73 = 4(x + y)
x1 = 137 = y1 + z1y1 + 73 = 3(1 + z1)
2
35
33
5
32
21
y1 = 101/4
z1 = 263/4
e1 = 543/4
x2 = 3y2 + z2 = 38y2 + 73 = 3(3 + z2)
2
36
42
23
15
42y2 = 121/2
z2 = 251/2
e2 = 361/2
1
101/4
543/4
263/4
3
121/2
361/2
251/2
x =
x2 e1 – x1
e2e1 – e2
y =
y2 e1 – y1
e2e1 – e2
z =
z2 e1 – z1 e2
e1 – e2
= 7
= 17= 23
SOLUZIONE DI UN SISTEMA DI EQUAZIONISOLUZIONE DI UN SISTEMA DI EQUAZIONI
29
Algoritmo di EuclideBy 1950, the word algorithm was most frequently associated with ‘Euclid’s algorithm’. Donald Knuth
The Art of Computer Programming, (v.I, p. 2)
Rappresenta per i matematici il prototipo della procedura algoritmica. Usato non solo nella ricerca del massimo comune divisore (Euclide), ma anche, nella soluzione delle equazioni indeterminate (identità di Bèzout). Per il confronto di due rapporti (Al-Khayyàm); che sarà ancora più chiaro con lo studio delle frazioni continue (Eulero). Ma quello che è stupefacente, è che questo algoritmo viene usato anche per determinare il numero delle radici reali di un’equazione algebrica (Metodo di Sturm).
30
Le due proposizioni su cui si basa la procedura forniscono un metodo per determinare se due numeri sono primi fra loro (Proposizione 1) e se non lo sono, per determinare il massimo comune divisore, MCD (Proposizione 2). Queste due proposizioni sono contenute nel Libro VII di The Elements, che insieme ai Libri VIII e IX formano I Libri Aritmetici di Euclide che mettono le basi della Teoria dei Numeri.
Il processo iterativo di ricerca del MCD è basato sulle ripetute sottrazioni fra il numero più grande e quello più piccolo.
IIIo secolo a.c. Algoritmo di Euclide
31
Nel IXo secolo, al-Mahani identifica l’uguaglianza fra due rapporti con il fatto che essi hanno le stesse sequenze di quozienti corrispondenti.
?. Omar al-Khayyàm
cd
ab =
cd
ab =
Il matematico arabo al-Khayyàm và oltre e identifica la diseguaglianza fra due rapporti.
d
ab
c
=
=
22371
355113
0, 3, 7, 10
0, 3, 7, 16
K = 1 2 3 4
32
Nella ricerca delle soluzioni intere di un’equazione di primo grado ax – by = c, il caso particolare dove a e b sono numeri primi, è noto come Identità di Bézout axo – byo = 1.
1766. Etienne Bézout
I manuali di Bézout hanno avuto un ruolo importante nell’insegnamento della matematica.Nella sua opera Cours d’Algèbre utilizza il seguente esempio 17x – 11y = 542,da cui l’ Identità di Bézout a*2 – b*3 = 1.
Bachet de Méziriac (1624) – dimostrazione laboriosa
Identità di Bézout e polinomi: AU + BV = 1.
33
L’approssimazione dei numeri per frazioni successive è alla base dei calcoli fatti dai primi matematici.
1737. Leonhard Euler
Il primo esempio di numero specificato in questa forma è 4/pi (Lord Brouncker).
Questa teoria viene enunciata da Eulero nel 18o secolo (Fractionibus continuis Dissertazio) e poi completata da Lagrange.
ab
cd
eFG
AB
CD
E
BC
DE
etc.
34
Nel 1815, Cauchy diede, per la prima volta, una soluzione completa al problema di determinare il numero delle radici di un equazione, ma il metodo è troppo complicato per avere un uso pratico.
1835. Charles.-F. Sturm
Nel 1835, Sturm spiega il suo metodo, abbastanza semplice, nella Mèmoire sur la résolution des équations numériques, che gli da la fama di fisico e matematico.Sturm utilizza nel suo metodo l’algoritmo di Euclide applicandolo ad un polinomio V e alla sua derivata V’.Dalle estensioni del teorema di Sturm hanno avuto origine diversi algoritmi e programmi di calcolo, come MACSYMA, REDUCE, MAPLE,e DERIVE.
35
Fece un bacino di metallo fuso di dieci cubiti da un orlo all'altro, rotondo; la sua altezza era di cinque cubiti e la sua circonferenza di trenta cubiti
La Bibbia, I Re 7, 23
Dalla misura del cerchio al calcolo di pi
And he made a molten sea, ten cubits from the one brim to the other: it was round all about, and his height was five cubits: and a line of thirty cubits did compassit round about
The Bible, I Kings 7, 23
Le diverse teorie di pensiero su pi si dividono in tre categorie: 1) fino al 17o
secolo, viene usato un approccio geometrico(lunghezze o aree) – Archimedes, Jiuzhang Suanshu, Descartes; 2) l’avvento del calcolo infinitesimale cambia completamente il tipo di approccio (somme, prodotti, funzioni trigonometriche, approssimazioni per frazioni successive) – Leibniz, Euler; 3) studi più teorici sulla natura del numero pi, che viene approssimato con un numero sempre maggiore di cifre decimali. Lambert (1761) dimostra che è un numero irrazionale, e Lindemann (1882) che è un numero trascendente.
Rhind Papyrus
48
36
Il libro su La Misura del Cerchio consiste di tre proposizioni.
287-212 ac. Archimede
La prima proposizione stabilisce che A = r C .
La terza proposizione stabilisce che
3d + d < C < 3d + d.
1071
17
2
Per ottenere questo risultatoArchimede calcola i perimetri dei poligoni regolari inscritti e circoscritti al cerchio.
37
E’ la più importante e la più conosciuta di tutte le antiche opere matematiche cinesi; scritta durante la dinastia Han, contiene centinaia di algoritmi, fra i quali anche l’algoritmo che calcola l’area del cerchio (pi = 3).
Verso la fine del terzo secolo il matematico Liu Hui ottiene una migliore approssimazione di pi calcolando le aree di una sequenza di poligoni regolari (di 6, 12, 24, 48, 96 e 192 lati) iscritti nel cerchio.
(220 ac – 206 dc)
L’astronomo e inventore Zu Chongzhi (nel quinto secolo) approssima pi a ; e Li Chunfeng (nel settimo secolo) trova la più utile semplificazione a .
355113 22
7
22A = *
c d
Area del cerchio – Jiuzhang Suanshu
38
Il metodo si avvale del principio che, di tutte le figure piane di un dato perimetro, il cerchio ha l’area maggiore (problema degli isoperimetri). Questo cerchio rappresenta il limite di una sequenza di poligoni regolari di uguale perimetro e di lati (4,8,16,32,…), ovvero si ottiene producendo la sequenza dei diametri dei cerchi iscritti in questi poligoni regolari.
p
d
Con il Metodo degli Isoperimetri Descartes mostra come costruire, il diametro d di un cerchio che abbia lo stesso perimetro p di un quadrato dato, ovvero = pi.
1640. René Descartes La quadratrice d’Hippias
La spirale di Archimede
39
1673. G.W. Leibniz
John Wallis (1656)
4/pi
Francois Viète (1593) è il primo a rappresentare pi come un prodotto infinito.
Lord Brouncker (frazioni successive)
4/pi
Leibniz definisce la sua formulaQuadratura Aritmetica
2/pi
40
1748. Serie
Eulero studia la convergenza della serie di Leibniz.
arctan t = t – t3 + t5 – t7 + t9 - … 3 5 7 9
tan pi/6 = 1/
3
arctan 1 = arctan (1/2) + arctan (1/3)
+(-1)n
(2n + 1).22n+1
pi
4=
(-1)n
(2n + 1).32n+1n>
=0n>=0
pi = 2
3 1 (-1)n
(2n + 1).3n
…- 1
3.3 5.32
1+ - + + …
e
pi/4 = arctan (1/5) – arctan (1/239)J.Machi
n pi2/6, pi4/90, pi2/8, pi3/32, …
3,141592653589793238462643383279502884119716939937510582097494459230781640628620899862803482534211706798214808651327230664708446
La 114a cifra dovrebbe essere 8!
M. De Lagny (1719)127 posizioni decimali
41
I Metodi di Newton Esistono due versioni del metodo di Newton: Metodo della Tangente e Poligono di Newton(Soluzione Numerica di Equazioni) (Soluzione Algebrica di Equazioni).
1669 – Approssimazione di Newton
1690 – L’iterazione di Raphson (r. di ricorrenza)
1768 – Mourraille (c. iniziali)
Lagrange (a. geometrico)
1818 – Fourier (convergenza)
1829 – Cauchy (r. complesse)
Idea Moderna dei Frattali.
P(y) = 0 P(x,y) = 0 y = f(x)
…La Riga e Piccoli Parallelogrammi…1850 – Caso generale Puiseux
42
1669. Isaac Newton APPROSSIMAZIONI LINEARIAPPROSSIMAZIONI LINEARI Il metodo di Newton per risolvere un’equazione polinomiale è un metodo per approssimazioni successive. Nel 1669 Newton fornisceun nuovo algoritmo, cheillustra sull’esempioy3 -2y -5 = 0
2+p=y y3
-2y
-5
+8 +12p +6p
2 +p3
-2p-5
Total -1 +10p +6p
2 +p3
+p3
+6p2
-1+10p
Total 0.061+11.23q+6.3q2 +q3
0.1+q=p
-0.0054+r=q
Total +0.0005416 +11.162r
-0.00004852+ s = r
-4
+0.001 +0.03q+0 q.3 2
-1
+0.06 +1.2 +6+1 +10
+q3
+q3
+6.3q2
+0.061+11.23q
Newton non fa uso esplicito della nozione di derivata.
2.09455148
43
1690. Joseph Raphson FORMULE DI RICORRENZAFORMULE DI RICORRENZA
Il metodo introdotto da Raphson semplifica il processo delle approssimazioni di Newton.
x = gx = g +
c + g3 – bg
b - 3g2
an
an+1 = an +
f(an)
f’(an
)
Più tardi Lagrange mostra che i due metodi sono praticamente uguali (algoritmo di Newton-Raphson).
x3 – bx + c = 0
44
1768. Jean-Raymond Mourraille
Per la prima volta viene affrontato il problema della convergenza del metodo di Newton. Mourraille utilizza la rappresentazione geometrica (Metodo della Tangente) per spiegare il comportamento della sequenza iterativa prodotta dall’algoritmo di Newton.
B
M
p P
f’>0, f”>0
B
M
pP
f’<0, f”>0
B
M
p P
f’<0, f”<0
B
M
pP
f’>0, f”<0
CONDIZIONI INIZIALICONDIZIONI INIZIALI
45
1829. Augustin Louis Cauchy CONVERGENZACONVERGENZA
Fourier (1818) prima in Question d’analyse algébrique, e poi in Analyse des équations déterminées (1831), è il primo che affronta il problema della misura della convergenza.In Lecons sur le Calcul Différential, in una nota sulla determinazione approssimata delle radici di un’equazione f(x) = 0, Cauchy specifica le condizioni iniziali, a partire dalle derivate f’ ed f’’.
Nel caso dell’equazione di Newton x3 -2x -5 = 0
f’(x) = 3x2 – 2, f’’(x) = 6x, a=2, i=-f(a)/f’(a)=0.1
46
1979. Radici Complesse
Nel 1979 John Hubbard, matematico americano, si chiese che cosa sarebbe successo applicando il metodo di Newton per la risoluzione delle radici cubiche.
i punti del piano sono “attratti” verso le tre soluzioni del sistema
47
1671. Poligono di Newton
La prima versione dell’algoritmo per ottenere le soluzioni algebriche di un’equazione algebrica P(x,y)=0.
aijxiyjP(x,y)
=
i,j
bkxky =
K>0
A
B
C
0
x
y
x2
y2
x3
y3
x4
y4
xy
x2y
xy2
x3y
x4y
xy3 xy4
x2y2 x2y3 x2y4
x3y2 x3y3x3y4
x4y3 x4y2 x4y4
B
C
*
A
E
D*
* *
* *
Y6 – 5xy5 + (x3/a)y4 – 7a2x2y2 + 6a3x3 + b2x4
= 0
Y6 – 7a2x2y2 + 6a3x3 v6 - 7v2 + 6 = 0 y = v
ax...
48
Risoluzione di Equazioni per Approssimazioni Successive
Approximation, (in Mathematics) is an operation by which one approaches ever more closely to the value of a required quantity, without however ever finding the exact value. d’Alembert -The Encyclopédie
Metodi per l’estrazione delle radici quadrate, (Metodi di Heron e Theon di Alexandria, Ibn al-Banna);
Metodi numerici per la risoluzione di equazioni (Al-Tusi, Viète);
Nel campo dell’astronomia al-Kashi usa questo processo per calcolare il valore di sen 1o, e Keplero per risolvere la sua equazione trascendentale;
Metodi di Bernoulli delle Serie Ricorrenti (Euler) e di Lagrange delle frazioni successive;
Le tecniche di Ruffini, Budan e Horner per la trasformazione delle equazioni polinomiali.
49
Heron di Alexandria
VAT 6598 – (6)
Come i Babilonesi(2000-1700 a.c.).
hanno ottenuto questa formula?
Valore Standard
Heron è stato il primo a proporre unalgoritmo iterativo di approssimazione(Metrica, Schone - 1896).
..
=
= ?
+ /2Aa
a +( )12
= 26*5/6
I° sec. a.c.
50
Theon di Alexandria
Theon propone una versione geometrica di questo algoritmo iterativo (Commentary on Ptolemy’s Syntaxis).
= A – a2
2ax =2x( )a r+ A
A – a2
2ar = a
+
4500
= 67°4’ 55”
I
G F
E
D C
BA
J
H
a
x ax
ax
x2
370 a.c.
51
13°secolo Ibn al-Banna
L’algoritmo binomiale, si basa sull’espansione di (a+x)2, e parte dalla formula x2+2ax=A-a2 per trovare un valore di x tale che x(x+2a) si avvicini a A-a2.Le prime tracce di questa procedura si trovano nel capitolo 4 di Jiuzhanh Suanshu (3° secolo – Liu Hui); nel 13° secolo viene descritto da Ibn al-Banna; è stato insegnato nelle scuole fino al 1960.
c = 3
c = 5
435
Primo passo:
N 18 95 74 2 95(A – a2)102 + C
a4
c(c + 80) < 295
Secondo passo:
N
(A – a2)102 + C
18 95 74 2 95 46 74
a433(3 + 80) < 295c(c + 860) < 4674
nr nr nr
52
Al-Tusi Il principio che è alla base di questo algoritmo (Treatise on Equations) è di utilizzare una tabella per trovare la radice dell’equazione, una cifra alla volta.
x0
a
b
N3 4 3 4 5 3 9 5
3 4
4
°°°
a
b1
N1 6 2 3 4 7 9 5
9 2 4 3 4
4
°°3
x1
a
b2
N2 3 1 5 9 5 5 1 0 4 9 9 4
4
°23 x1
a
b2
N2 3 1 5 9 5 5 1 0 4 9 9 4
4
°23
4
9 2 4 3 4
3
X3 + 12x2 + 102x = 34 345 395
53
Viète
Un metodo generale per trovare le soluzioni positive delle
+(20)5 +32
+31
0 0 0 0 0
+ 500 x 20 +-
1 0 0 0 0
0 5 5 0 4
7 0 0 0 0
4 0 0 0 0- 5 x (20)3
79
47 3 5 5 0 4
- 5.3.(20)2 -
-
6 0 0 0
- 5.3.(20) --
3 0 0
6 3 0 5
5- 5
+500 +
+
5 0 0+ 5. (20)4 + 8
+
0 0 0 0 0
4 0 0 0
8 0 0 0 0+ 10. (20)3
+ 10. (20)2 s + 5. 20 + 1 0 0
+ 8 8 4 6 0 0- 6 3 0 5
7 8 2 9 5 + 8
+800 000s
+ 2
+80 000s2
+ 32
+ 12
0 0 0 0 0
6 0 0 0
8 0 0 0 0+4 000s3
+ 100s4
+ s5
+
+
1 0 2 4+ 2 0 0 0
6 4 6 2 4 + 47
+ 500s
5 5 6 0 02
- 6000s
-
- 300s2
-
-
2 4 0 0 0
3 2 0
4 8 0 0
- 5s3
-
3 5 5 0 4 + 47
9 1 2 02
equazioni, dal secondo grado al sesto grado (On the solution of numerical powers).
x5 – 5x3 + 500x = 7 905 504
Problema XV
Passo 1 – Inizializzazione
ordine di grandezza della radice e la sua prima approssimazione 20
x = 20 + s(20+s)5 – 5(20+s)3 + 500 (20+s) = 7 905 504
sP(1) < sP(s) < s5 + sP(s) = 4 735 504
s < 4 735 504/P(1)
5(20)4s + 10(20)3s2 + 10(20)2s3+ 5.20s4 + s5 – 5.3.(20)2s – 5.3.20s2 – 5s3 + 500s = 4 735 504
P(s) = 5(20)4 + 10(20)3s + 10(20)2s2+ 5.20s3 – 5.3.(20)2 – 5.3.20s – 5s2 + 500s5 + sP(s) = 4 735 504
1600.
54
Al-Kashi e il Sen 1°
Il matematico e astronomo Al-Kashi descrive un algoritmo che gli consente di determinare il Sen 1°, a partire dal Sen 3° (3;8,24,33,59,34,28,15), con notevole precisione (60-7).
x= Sen 1°
P = 47,6;8,29,53,37,3,45
Sen 3a = 3 Sen a -4 Sen3 a
qx = x3 + p
3x = 4 x3 /602 + Sen 3°
q = 45,0
Sen 1° = 1;2,49,43,11,14,44,16,26,17
ovvero 0,017 452 406 437 283 571
1400.
55
Equazione di Keplero
Keplero risolve questa equazione con approssimazioni successive definite da:
xn = F(xn-1) dove f(x) = t – e.Sen x
x = t – e.sen x
Epitomes astronomiae Copernicanae
250 ac.
56
Algoritmi in AritmeticaIl problema di distinguere i numeri primi dai numeri composti, e la decomposizione di questi ultimi in fattori primi, è il più importante e il più utile di tutta l’Aritmetica […]. La dignità di questa scienza esige che noi cerchiamo con tutti i mezzi di risolvere un problema così famoso ed elegante.
Gauss
Disquisitiones Arithmeticae, 1801
Gli algoritmi di Eratostene e Pascal sono utilizzati per determinare i numeri primi. Non è semplice trovare algoritmi efficienti per testare numeri molto grandi.I tests di Lucas e Lehmer e Pépin. I primi due derivano dal teorema inverso del teorema di Fermat e richiedono la fattorizzazione di N+1 o N-1 per determinare se N è un numero primo. Tre algoritmi di fattorizzazione: Fermat (lineare ma efficace solo in alcuni casi particolari); Gauss e Legendre (più complessi ma di più ampia applicazione), utilizzano residui quadratici e frazioni continue.L’algoritmo relativo all’equazione Diophantina di Pell-Fermat, dal quale si sviluppa la ricerca e le soluzioni di Lagrange. La ricerca di algoritmi sempre più efficienti in quest’area deriva anche dal loro utilizzo nella scienza della crittografia, chiave pubblica.
57
Il Crivello di Eratostene
Consente di determinare tutti i numeri primi inferiori ad un numero N prefissato (Nichomachus di Gerasa).
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 …
* * *
* multipli di tre (2)
***
* multipli di cinque (4) * ** *
* multipli di sette (6)
*
39 = 6
N =
1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 …
forma compatta
250 ac.
58
Criterio di Divisibilità - Pascal
Consente di saper se un numero è divisibile per un altro numero senza eseguire la divisione. Blaise Pascal raccoglie tutti i criteri prodotti e fornisce un criterio generale.
10 9 8 7 6 5 4 3 2 1
6 2 3 1 5 4 6 2 3 1
Divisibilità per 7: utilizzo i resti delle divisioni delle differenti potenze di 10.
2 8 7 5 4 2 1 7 8
8 + 21 + 2 + 12 + 16 + 25 + 7 + 24 + 4 = 119La Teoria delle
Congruenze ha origine direttamente da questo algoritmo di Pascal.
1654.
59
Residui Quadratici - Legendre
Legendre, in Théorie des nombres (1798), fornisce un algoritmo per testare se a è un residuo quadratico modulo p, Questo algoritmo si basa sulla legge della reciprocità quadratica (Eulero, 1783).
x2 a (mod p).
p
q=
q
p
p e q numeri dispari che non sono entrambi della forma 4n + 3
altrimenti-p
q=
q
p
= (-1) (p-1)(q-1)/4p
p
sta per il resto della divisionedi a(p-1)/2 per p.
a è un residuo quadratico modulo p se
ap =
1p
a
abc =
c ca b
sea= mc +
rc ca r
=
6011013
… -17
1= -1 =
1013 non è un residuo quadratico di 601
1798.
60
Teorema Inverso di Fermat
Il piccolo teorema di Fermat: se a e p sono due numeri interi primi, allora se p è primo,
Questo teorema non consente di stabilire se un numero è primo, infatti il teorema inverso di Fermat è falso.
Esempio a= 2 N = 341 numero pseudo primo
Per avere un test deterministico sui numeri primi, è necessaria una condizione supplementare che consente di affermare che N è un numero primo (Tests di Lehmer, 1927; Tests di Lucas, 1876).
ap-1 1 (mod p).(es:13)
1640.
61
1877. Test di Pepin
Fn = 22n + 1
Il teorema di Pepin fornisce un algoritmo per testare se un numero di Fermat è un numero primo. Fermat sosteneva che tutti i
numeri in questa forma erano numeri primi (lettera a Carcavi del 1659). 1729. Goldbach attira l’attenzione di Eulero sulle
affermazioni di Fermat
1732. Goldbach dimostra che F5 non è primo
1877. Pèpin propone un semplice test.
Condizione necessaria e sufficiente affinchè il numero
an = 22n + 1 sia primo, per n > 1,
è che il numero 5(an-1)/2+1 sia divisibile per an.
62
Algoritmi di Fattorizzazione
Gauss, in Disquisitiones Arithmeticae (1801), ha proposto due metodi di fattorizzazione, ma egli suggerisce di provare a dividere il numero dato per i più piccoli numeri primi (2, 3, 5, 7, …19) per evitare di utilizzare metodi sottili e artificiali. Dello stesso avviso è Riesel in Prime numbers and computer methods for factorisation (1985).
Un algoritmo di fattorizzazione richiede molti passi in più di un algoritmo per la primalità. Knuth, in The Art of Computer Programming, afferma che la fattorizzazione è più difficile di trovare il MCD tra due numeri.
63
Algoritmi di Fattorizzazione
La maggioranza degli algoritmi in uso è basata sui metodi dovuti a Fermat, Gauss e Legendre.In particolare l’idea di Legendre è stata ripresa nel XX° secolo per realizzare algoritmi ad alte performance.Nel 1975 Pomerance ha costruito un algoritmo basato su metodi statistici.
Esistono, quindi, molti algoritmi di fattorizzazione, ma sono costosi. Miglioramenti degli algoritmi sono giudicati in base alla loro complessità.
64
1643. Fattorizzazione per differenza di due quadrati
Nel 1643 Père Mersenne pone a Fermat la sfida di fattorizzare il numero 100 895 598 169. La sua risposta fornisce un metodo sistematico per fattorizzare un numero.
Il punto di partenza fu di tentare di scrivere il numero N sotto forma di differenza di due quadrati:
N=x2-y2=(x+y)(x-y)
Il numero x è sicuramente maggiore della radice quadrata dell’intero N. E’ sufficiente, quindi, testare uno ad uno i numeri x maggiori di quella radice quadrata per determinare se la differenza x2-N è, o no, un quadrato.
65
1643. Fattorizzazione per differenza di due quadrati
Fermat fornisce un algoritmo molto semplice per svolgere con successo tutti calcoli. Tuttavia il metodo di Fermat richiede una grande quantità di calcoli. I suoi successori hanno cercato di trovare altri modi di scrivere N come differenza di due quadrati.
1805. Kausler
1840. Collins
1911. Kraitchick
1974. Sherman Lerman riprende il metodo di Fermat. La sua idea è di eliminare i casi sfavorevoli (N ha fattori primi piccoli).
66
1801. Fattorizzazione per quadrati residui
Nel 1801 Carl Frederich Gauss, in Disquisitiones Arithmeticae propone due nuovi metodi di fattorizzazione. Il primo dei due è basato sulla ricerca dei più piccoli quadrati residui del numero da fattorizzare.
Il metodo usato da Gauss è un metodo per esclusione. Utilizzando i quadrati residui è possibile escludere molti fattori primi di N.
a è un quadrato residuo di N se esiste un x tale che x2 a(modN)
67
1931. Fattorizzazione per frazioni continue
L’idea di utilizzare l’espansione di frazioni continue della radice quadrata di N era stata proposta da Legendre, come osservazione, nella Thèorie des nombres, nel 1798.
Ripresa da molti matematici, raggiunge il posto d’onore in un articolo del 1931 di D.H.Lehmer e R.E.Powers: On factorising Large Number, Bulletin of the American Mathematical Society.
Con l’avvento dei computer l’algoritmo ha attirato notevoli interessi, nei venti anni successivi sono stati fatti miglioramenti per produrre algoritmi molto potenti.
68
1657.L’Equazione Pell-Fermat
x2 – ay2 = 1 ay2 + 1 = x2
6° secolo. Brahmagupta 12° secolo. Bhaskara
1657. Fermat pone la sfida ad altri matematici di dimostrare che questa equazione possiede sempre un numero infinito di soluzioni. La dimostrazione che Fermat affermava di avere non è mai stata trovata. 1766. Lagrange da la prima dimostrazione. Egli ha pensato che la soluzione al problema di Fermat era la chiave per risolvere tutti i problemi di questo tipo. 1798. Legendre utilizza il metodo di Lagrange per dare le condizioni per la risolvibilità di equazioni Diofantine quadratiche.
dove a è un intero non quadrato.
69
250. L’Aritmetica di Diophantus
I libri dell’ Arithmetica di Diophantus (AD 250) sono proposti sotto forma di una serie di problemi risolti.
Nel risolvere i problemi, Diophantus tratta circa 40 equazioni della forma ay2+by+c=x2. In particolare in un lemma offre una famiglia di problemi che hanno soluzioni infinite. Questo lemma fornisce un metodo per risolvere alcune equazioni di Pell-Fermat.
70
1766-1769. Il risultato di Lagrange
Il lavoro fatto da Lagrange sulle equazioni Pell-Fermat fu pubblicato in una memoria del 1776-1769.
Ogni equazione Pell ha una soluzione con i mezzi per trovarla.
Trovata una soluzione è possibile trovarne infinite
Tutte le soluzioni possono essere trovate dall’espansione di radici continuate della radice quadrata di a con un algoritmo per trovarle.
Egli dimostra tre risultati principali con tutto il rigore e la generalità possibile:
71
Sistemi di Equazioni Lineari
E’ solo verso la fine del 17° secolo che appaiono sistemi di equazioni lineari con coefficienti letterali. Anche Leibniz utilizza doppia indicizzazione.
… l’eliminazione è la parte più difficile e lunga del lavoro, così tanto che si è riluttanti a desiderare che la scienza possa scoprire i mezzi per fare ciò che potrebbe essere utile come l’invenzione dei logaritmi lo è stato per le moltiplicazioni….
Christian Ludwig Gerling
Die Ausgleichung-Rechungen, 1843
La soluzione ad alcuni antichi problemi può essere considerata, oggi, come la soluzione di sistemi di equazioni lineari. Abbiamo incontrato tali problemi con i matematici Babilonesi ed Egiziani, con i matematici indiani nel Medio Evo, nei paesi islamici e in Europa.
72
Sistemi di Equazioni Lineari
Nel 1730 Maclaurin calcola la soluzione di sistemi di due e tre equazioni e fornisce le formule per induzione per la soluzione di 4 equazioni.
L’astronomia e la geologia richiedono la soluzione di sistemi con un gran numero di equazioni, e il numero di operazioni necessarie per la loro soluzione cresce rapidamente. I metodi successivi cercano di ridurre il numero di operazioni (metodo pivot di Gauss) o di fornire soluzioni per approssimazioni successive (metodo dei Minimi Quadrati).Nel 19° secolo sono stati sviluppati metodi iterativi.
Nel 1750 Cramer fornisce le formule generali (regola di Cramer) per qualsiasi numero di equazioni, anche se non offre una dimostrazione.
73
1750. Regola di Cramer Cramer fornisce le formule per dare soluzioni per un sistema di n equazioni, per qualsiasi n. Tali formule sono ottenute per induzione dai casi particolari di n=1,2 e 3. Le soluzioni sono date sotto forma di un quoziente di due polinomi omogenei di grado n. Ulteriori lavori sulle formule danno origine alla teoria dei determinanti.1815. Cauchy ha dato la prima dimostrazione della regola di Cramer, stabilendo l’attuale notazione e cominciando uno studio sistematico dei determinanti.1850. Sylvester ha introdotto il termine matrice.
74
1805. Metodo dei minimi quadrati
Il metodo, descritto da Legendre nel 1805, è stato usato da Gauss almeno dal 1801 per determinare l’orbita del pianeta Ceres.
Nel 1809 Gauss giustifica il suo metodo e nel 1821 dimostra che la sua scelta di combinazioni lineari corrisponde a quella con minore probabilità di errore, in accordo con Seidel.
Il metodo consiste nel sostituire un sistema di n equazioni iniziali con un sistema di sole k equazioni (k incognite).
75
1810. Il metodo pivot di Gauss
Nel 1807, C.F.Gauss diventa direttore dell’osservatorio astronomico di Gottingen. Egli si propone di determinare l’orbita precisa del pianeta Pallas e spiega il suo approccio in una memoria datata 1810.
Gauss riutilizza il metodo dei minimi quadrati utilizzando un’altra somma di quadrati, in modo tale che ad ogni passo scompaia un’incognita (eliminazione Gaussiana). Così arriva ad un sistema triangolare di equazioni.
Uno dei più notevoli metodi cinesi (fangcheng) è di ridurre la matrice del sistema in forma triangolare e quindi di calcolare le incognite per successive sostituzioni.
Administrator
76
1823. Metodo Iterativo di Gauss
Gauss, in una lettera a Gerling, nel 1823, spiega l’idea base sul metodo conosciuto come metodo Gauss-Seidel. Egli parla di un metodo “indiretto” per risolvere il sistema di equazioni derivante da misurazioni della superficie della terra.16°sec. Tycho-Brahe mappa della superficie della terra17°sec. Picard misura l’arco del meridiano nei dintorni di Parigi per fissare il valore del raggio della Terra18°sec. Spedizioni in Lapponia e in Peru per determinare l’estensione dell’appiattimento della TerraIn tutti i casi erano usate triangolazioni e il risultato ottenuto con il metodo dei minimi quadrati.
Dal 1820 al 1825 Gauss si occupa di un lavoro sulla triangolazione di Hanover. Il sistema di equazioni da risolvere diventò enorme per cui Gauss propose metodi iterativi per velocizzare i calcoli.
77
1845. Metodo di Jacobi
Carl Gustav Jacobi aveva necessità di trattare con sistemi lineari di equazioni quando considerava sistemi fisici soggetti a piccole oscillazioni. Egli descrive un metodo iterativo valido quando i coefficienti della diagonale sono in preponderanza. In caso contrario egli usa la rotazione degli assi, in modo da eliminare i coefficienti più grandi che non sono sulla diagonale.
78
1874. Metodo di Seidel
Ludwig Seidel, alunno di Jacobi, ha effettuato una gran quantità di calcoli per lui. In particolare doveva risolvere un sistema di equazioni con 72 incognite per uno studio sulla luminosità delle stelle. Seidel ha proposto una tecnica iterativa per trovare la soluzione ad un sistema di equazioni. La sua ispirazione viene dall’idea di Jacobi di approssimazioni successive e dal metodo “pivot” di Gauss.
79
1885. Nekrasov
Alexander Ivanovich Nekrasov esamina il metodo di Seidel dietro richiesta dell’astronomo Tzeraki. In un articolo del 1885, egli solleva la questione della velocità di convergenza.
Dopo aver fornito esempi in cui la convergenza è molto lenta, Nekrasov dimostra che la scelta ottimale indicata da Seidel non accresce significativamente la velocità di convergenza.
80
1923. Metodo di Cholesky
In contrasto ai metodi iterativi la tecnica di Cholesky porta, come una regola, ad una soluzione esatta.Il metodo del comandante Cholesky consiste nel confrontare le equazioni con altre equazioni derivate da un sistema di equazioni lineari già risolto.
“Il comandante di artiglieria Cholesky, dell’ Army Geographic Service, morto durante la grande guerra, durante le sue ricerche sulle correzioni delle curve terrestri, ha concepito una procedura molto ingegnosa per la soluzione delle cosidette equazioni normali, ottenuta con l’applicazione del metodo dei minimi quadrati ad equazioni lineari in numero minore del numero delle incognite. Da ciò aveva derivato un metodo generale per la soluzione di equazioni lineari.” (Commandant Benoit)
81
Tavole e Interpolazione
La costruzione di tavole è di fondamentale importanza per facilitare i calcoli e per evitare di ripetere le stesse operazioni molte volte.
La teoria dell’interpolazione….. la scienza di leggere tra le linee di una tavola matematica.
E.T.Whittaker
The Calculus of observations
Quello che accade generalmente è che, dopo un certo numero di valori calcolati, gli altri valori sono ottenuti come interpolazione dai valori calcolati precedentemente.
Tavole per calcolare inverso (Babilonesi) Tavole trigonometriche Tavole delle corde (Tolomeo – 2° secolo) Tavole decimali (Briggs – 17° secolo)
Formule d’interpolazione di Gregory-Newton Formule d’interpolazione polinomiale di Newton e Lagrange Funzioni d’interpolazione (Cauchy) Algoritmo di Neville – Algoritmo CORDIC
82
150 AD. Tavole delle Corde di Tolomeo
Tolomeo ha scritto Mathematical Syntaxis nel 150 AD, detto Almagest (dall’arabo “il più grande”), considerato il lavoro di riferimento per l’astronomia.Tolomeo ha spiegato come costruire una tavola delle lunghezze delle corde di un cerchio in funzione dei valori degli archi corrispondenti.
Sono le più antiche tavole note di questo tipo, anche se Ipparco (2°sec A.C.) e Menelao (1°sec A.C.) hanno usato tavole di questo tipo.La costruzione delle tavole di Tolomeo richiede una teoria di trigonometria piana che è presentata nell’Almagest.
83
1624. Briggs e i logaritmi decimali
Nel 1614 Napier pubblica una tavola di logaritmi ottenuta per successive estrazioni di radici quadrate nel suo Mirifici logarithmorum canonis Descriptio. Queste tavole ebbero grande successo e furono pubblicate molte altre versioni.
The word algorithm itself is quite interesting: at first glance it may look as though someone intended to write logarithm but jumbled up the first four letters .
Donald D.Knuth
The Art of Computer Programming (vol.I,p.1)
Henry Briggs pubblica Logarithmorum Chilias Prima nel 1617, ma il suo lavoro più importante fu Arithmetica Logarithmica nel 1624. Questi nuovi logaritmi differiscono da quelli di Napier perché utilizzano 0 e 1 per i logaritmi di 1 e 10 e quindi sono logaritmi decimali.
84
1670. La formula Gregory-Newton
Gregory e Newton hanno scoperto la formula indipendentemente. Il primo ne parla in una lettera a Collins nel 1670. Il secondo in una lettera a John Smith datata 8 maggio 1675.
L’interpolazione lineare non è sempre sufficientemente accurata per ottenere valori intermedi buoni. Per questo i matematici sviluppano processi più rifiniti attraverso l’utilizzo di differenze finite.
85
1687. Interpolazione polinomiale di Newton
Isaac Newton è stato il matematico che ha dato il maggior contributo alla teoria dell’interpolazione e delle differenze finite.
1675 – lettera a John Smith (8 maggio)1676 – Methodus Differentialis (apparso nel 1711)1676 – lettera ad Oldenburg (24 ottobre)1687 – Philosophiae naturalis principia mathematica
Lemma V. Trovare una linea curva di tipo parabolico che passa attraverso un dato numero di punti.
86
1795. Interpolazione polinomiale di Lagrange
Lagrange affronta il problema, trattato precedentemente da Newton, di utilizzare una curva parabolica per interpolare una curva, ossia interpolare una funzione per mezzo di una funzione polinomiale. Egli è motivato da un problema pratico di sopravvivenza:
Da un punto la cui posizione è sconosciuta, sono osservati tre oggetti le cui distanze relative sono note e i tre angoli formati dai raggi visuali dall’occhio dell’osservatore a questi tre sono stati determinati. Vogliamo trovare la posizione dell’osservatore rispetto a questi stessi oggetti.
87
1795. Interpolazione polinomiale di Lagrange
Gli elementi della base di Lagrange sono così definiti:
è il polinomio interpolante.
Lagrange propone una soluzione tramite tentativi ed errori, questo porta ad una curva degli errori attraverso un numero finito di punti, i punti corrispondono ai tentativi. Infine, per risolvere il problema la curva deve essere approssimata da una polinomiale. Questa interpolazione polinomiale di Lagrange, non è diversa dalla polinomiale di Newton, ma espressa in modo differente.
88
1840. Limite superiore di errore (Cauchy)
Se vogliamo che il valore interpolato sia una buona approssimazione del valore esatto, dobbiamo determinare un limite superiore per l’errore. Cauchy ha fornito delle formule per calcolare tale limite.
89
1933. Algoritmo di Neville
L’interpolazione polinomiale di Lagrange è inadatta a un calcolo iterativo che va da n a n+1 punti. E.H.Neville propone una procedura per rimediare a questo inconveniente.Funzioni polinomiali e razionali comportano grandi quantità di moltiplicazioni e divisioni con notevole costo in termini di spazio e tempo.Nel 1959, J.Volder ha proposto un metodo per calcolare funzioni trigonometriche che utilizza solo addizioni, sottrazioni e shift. L’algoritmo CORDIC (Coordinate Rotations on a Digital Computer) ha rivoluzionato il calcolo dei valori di funzioni con notevole risparmio di tempo e di spazio.
Funzioni polinomiali e razionali comportano grandi quantità di moltiplicazioni e divisioni con notevole costo in termini di spazio e tempo.Nel 1959, J.Volder ha proposto un metodo per calcolare funzioni trigonometriche che utilizza solo addizioni, sottrazioni e shift. L’algoritmo CORDIC (Coordinate Rotations on a Digital Computer) ha rivoluzionato il calcolo dei valori di funzioni con notevole risparmio di tempo e di spazio.
90
Quadrature approssimate
L’origine del significato di quadratura è di trovare un quadrato con la stessa area di una data figura geometrica (quadratura del cerchio).Si tratta di stabilire un rapporto tra due figure piane.
I geometri greci utilizzavano un metodo esaustivo (Archimede). Lo stesso utilizzato nel 9° secolo dai matematici Arabi Banu Musa, Thabit ibn Qurra, Ibrahim ibn Sinan e nel 10° secolo da Ibn al-Haytham e al-Mutaman.
91
Quadrature approssimate
Nel 17° secolo altre formule per le aree sono state date da Gregory, Newton, Cotes e Stirling.
Nel 17° secolo è stato introdotto il metodo degli indivisibili. Nel 1639 Cavalieri ha usato un metodo noto come metodo di Simpson.
Nel 18° secolo Gauss da una nuova formula di quadratura. Il russo Chebyshev determina una scelta di punti per le formule di Newton-Cotes o di Gauss per evitare che si generino errori significativi.
Alla fine del 17° secolo l’invenzione di Newton e Leibniz del calcolo infinitesimale fornisce un algoritmo per il calcolo esatto di un’area sotto una curva.
92
1670. Formula di Gregory
Nel 1670 James Gregory, professore di matematica a St.Andrews e membro della Royal Society di Londra, scrive a James Collins, Segretario della Società. La lettera descrive il suo lavoro, confronta il suo lavoro con quello dei contemporanei (Newton, Barrow, Briggs, Mercator, Keplero, …) ma non contiene dimostrazione dei risultati perché queste erano considerate lunghe e tediose. Gregory si interessava di sviluppo in serie di funzioni e la loro applicazione a problemi geometrici come la rettificazione di curve.
93
1711. Regola di Newton tre-otto
1669 De Analysi per Aequationes Numero Terminorum Infinitas1687 Principia1711 Methodus Differentialis
Se ci sono quattro ordinate posizionate ad intervalli uguali, sia A la somma della prima e della quarta, B la somma della seconda e terza, ed R l’intervallo tra la prima e la quarta, l’area totale tra la prima e la quarta sarà
A+3B
8R
94
1722. Formule Newton-Cotes
Sebbene il trattato di Roger Cotes sul Metodo Differenziale di Newton (De Methodo Differentiali Newtoniana) fu pubblicato postumo nel 1722, esso probabilmente fu scritto nel 1709. L’autore dice, in un post-script, di aver composto il suo teorema nel 1707, prima del testo di Newton.
Cotes da una spiegazione del metodo e fornisce le formule per le aree sotto curve per i casi da 3 a 11 punti equidistanti, il tutto senza il supporto di calcoli.
95
1730. Formule Correzione di Stirling
Il Treatise on the Summation and Interpolation of Infinite Series di James Stirling fu pubblicato nel 1730. Egli da le formule di Newton-Cotes, senza menzionare Cotes, e una Tavola di Correzioni da applicare alle approssimazioni.
Stirling non da spiegazioni per i risultati, ma semplicemente una descrizione di come usare le tavole con alcuni esempi.
96
1743. Regola di Simpson
La formula nota come Regola di Simpson è la prima delle formule di Newton-Cotes. Il contributo di Simpson fu solo di fornire una dimostrazione geometrica del risultato. La sua idea fu di dividere l’intervallo in considerazione in parti uguali, sufficientemente piccole perchè una parabola possa essere una buona approssimazione al grado di accuratezza richiesto, ed applicare la prima formula ad ognuna di queste sezioni (metodo composto).
L’idea di dividere l’intervallo in parti uguali fu usata nello stesso periodo da Maclaurin.
97
1816. Formule di Quadratura di Gauss
In una comunicazione alla Gottingen Society del 1816, Gauss, partendo dalle formule di Cotes, da una valutazione dell’errore relativamente al metodo. Fornisce, così, una formula che ottimizza l’approssimazione.
L’articolo di Gauss non è semplice da leggere. Jacobi fornisce un approccio più semplice in un articolo del 1826.
98
1874. La scelta di Chebyshev’s
In un articolo pubblicato nel 1874 nel Journal de Liouville, Chebyshev si propone di determinare una nuova formula di quadratura in cui ognuno dei valori della funzione in punti particolari abbia lo stesso peso. Con la formula di Gauss c’è rischio di errore.
Nel 1880 R.Radau ha pubblicato una sintesi delle formule di quadratura nel Journal de Liouville. In particolare ha definito il grado di precisione.
Nel 1880 R.Radau ha pubblicato una sintesi delle formule di quadratura nel Journal de Liouville. In particolare ha definito il grado di precisione.
99
Soluzioni approssimate di Equazioni Differenziali
I metodi di soluzioni approssimate, utilizzati da Eulero per la prima volta nel 18° secolo, sono stati perfezionati verso la fine del 19° secolo.
I metodi delle differenze finite forniscono lo stimolo per ulteriori miglioramenti che portano ai lavori di Adams (metodo multi-step), Runge, Heun e Kutta (metodo one-step).
Il problema dei tre corpi ha molta importanza per l’astronomia, e allo stesso tempo è molto difficile, per cui tutti gli sforzi dei geometri sono stati per lungo tempo diretti verso di esso. Essendo un’ integrazione completa e rigorosa manifestamente impossibile, è stato fatto appello alle procedure di approssimazione.
Henri Poincarè
Les méthodes nouvelles de la Mécanique céleste, 1892, vol.I,p.1
L’uso di questi metodi, datati un centinaio di anni, oggi è molto esteso (dal 1950). Essi si adattano bene ad essere gestiti con i computer.
100
1768. Metodo di Eulero
In un capitolo intitolato On the integration of differential equations by approximation del suo lavoro Institutionum Calculi Integralis del 1768, Eulero nota l’aspetto insoddisfacente dell’utilizzo delle serie e descrive il metodo noto come “metodo di Eulero”.
equazione differenziale del primo ordine
condizioni iniziali
101
1835. Cauchy (Esistenza di una soluzione)
“A.L.Cauchy ha posto la teoria generale delle equazioni differenziali su una base indistruttibile” afferma Paul Painlevé in un articolo nella Encyclopédie des Sciences mathématiques. Infatti per primo, Cauchy ha posto e risolto il problema dell’esistenza di una soluzione di una equazione differenziale del primo ordine che soddisfa una condizione iniziale, fornendo due dimostrazioni del risultato.
Il lavoro di Picard fornisce il completamento della teoria dell’esistenza di soluzioni. In una memoria del 1890 C.E.Picard da una terza dimostrazione di esistenza.
102
1895. Metodo di Runge
C.Runge propone metodi per la soluzione di equazioni differenziali che offrano maggiore accuratezza.
Riassumiamo i 3 metodi proposti da Runge.
103
1900. Metodo di Heun
Nell’articolo di Runge abbiamo visto che si può migliorare l’ordine di approssimazione dei metodi di soluzione considerando combinazioni di approssimazioni. Nel 1900 Karl Heun sistematizza questa possibilità. Egli prende ispirazione dal metodo delle quadrature di Gauss.
Heun, successivamente, mostra la possibilità di gestire il caso di sistemi di equazioni. Inoltre il metodo di Heun fu usato per la prima integrazione di un sistema di equazioni differenziali da un calcolatore ENIAC.
104
1901. Metodo di Kutta
M.W.Kutta ha proposto nel 1901, un modo di perfezionare le formule di Heun.
Non è semplice fare una distinzione tra i metodi di Heun, Kutta e Runge. Più che una progressione nel tempo ogni autore, raffinando i metodi, si riferisce al lavoro di un predecessore.
105
1883. John Adams (differenze finite)
Nel 1883 Adams, analogamente alle quadrature approssimate, ha proposto di utilizzare le differenze finite (Gregory). Adams ha proposto due formule che forniscono valori sufficientemente accurati.
Mentre i metodi di Runge, Heun e Kutta erano ispirati ai metodi di Eulero e Gauss di tradizione tedesca, i metodi multi-step presentati da Adams derivano dalle formule Gregory-Newton di tradizione inglese.E’ significativo notare, alla fine del 19° secolo, l’utilizzo di tali metodi da parte di Sheppard per migliorare le tavole numeriche e dell’astronomo Darwin per calcolare le orbite dei pianeti.
106
Approssimazione di Funzioni
L’idea di approssimare una funzione è stata già introdotta con l’interpolazione. Con l’interpolazione costruiamo una funzione che assume valori specifici per un numero finito di valori della variabile, con l’approssimazione, invece, cerchiamo una funzione che approssimi al meglio i valori di altre funzioni, per tutti i valori di un certo intervallo.
… per mostrare i difetti dei risultati che essi (i fisici) accettano senza domande, non è necessario estirpare funzioni mostruose come funzioni continue senza derivate; il fenomeno Runge mostra che la procedura di interpolazione polinomiale classica può sicuramente essere divergente per funzioni analitiche che sono eccellenti come desiderato.
Jean Diedonné, Calcul Infinitésimal, 1968
Approssimazione Uniforme (Taylor, Lagrange, Chebyshev, Schoenberg)
Approssimazione Quadratica Media (Fourier)
107
1715. La formula di Taylor
La formula di Taylor era già nota a James Gregory (lettera a Collins del 15 febbraio 1671), ma fu pubblicata per la prima volta nel 1715 da Brook Taylor nel suo Methodus incrementorum directa et inversa.
Le varie varianti della formula di Taylor producono approssimazioni polinomiali di funzioni, purchè siano sufficientemente differenziabili.
Pn(x) = f(x0)+f'(x0)(x-x0)+ 1/2!f''(x0)(x-x0)2+ 1/3!f'''(x0)(x-x0)3+ ....+ 1/n!f(n)(x0)(x-x0)n
Pn(x) = f(x0)+f'(x0)(x-x0)+ 1/2!f''(x0)(x-x0)2+ 1/3!f'''(x0)(x-x0)3+ ....+ 1/n!f(n)(x0)(x-x0)n
108
1797. Il resto di Lagrange
Joseph-Louis Lagrange ha pubblicato un lavoro didattico nel 1797, La Théorie des Fonctions analytiques, nel quale propone di porre i fondamenti del calcolo differenziale. Egli dimostra il teorema di Taylor e prevede un intervallo limitato per il resto nell’espansione di Taylor.
109
1859. Polinomiale di Chebyshev’s
Chebyshev affronta, nel 1854, il problema di ridurre a zero l’errore per una polinomiale di grado n e, nel 1859, lo tratta in modo più generale.
110
1940. Spline-Fitting
La ricerca per la migliore approssimazione uniforme di funzioni continua al principio del 20° secolo, in particolare con Charles De la Vallée-Poussin e con Sergei Bernstein.
Le funzioni “spline” sono state definite e studiate per la prima volta da Schoenberg nel 1940.
111
1807. Serie di Fourier
Eulero ha esaminato le serie trigonometriche dal 1730 ed ha prodotto espansioni di funzioni periodiche come serie trigonometriche nella sua Memoria del 1749 sull’irregolarità delle orbite di Saturno e Giove.Subito dopo Clairaut ha prodotto espressioni per i coefficienti di Fourier di una funzione.Nello stesso periodo, d’Alembert studiava il problema delle stringhe vibranti.Nel 1753, Daniel Bernoulli si propone di trovare soluzioni in forma di serie trigonometriche.
112
Serie di Fourier
La teoria non aveva solide basi fino al lavoro di Fourier. L’essenza delle sue idee è contenuta in una memoria proposta all’Accademia delle scienze di Parigi nel 1807 e di nuovo nel suo lavoro del 1822, Theorie analytique de la Chaleur.
Poisson e Cauchy hanno contribuito allo studio delle serie di Fourier.Dirichlet dal 1822 al 1826 ha condotto un rigoroso studio sulla convergenza delle serie di Fourier.
113
1965. Fast Fourier Transform
Le trasformazioni di Fourier richiedono un numero di moltiplicazioni pari a N2.Cooley e Tukey hanno descritto, nel 1965, un metodo migliorativo che richiede un numero di moltiplicazioni pari a NlogN. Il metodo è noto come Fast Fourier Transform o algoritmo FFT.
114
Accelerazione di convergenza
Sebbene il primo uso del termine convergenza può essere attribuito a Gregory nel 1668, il concetto di convergenza, come è utilizzato oggi, non è stato definito esplicitamente fino al 19° secolo. Poincaré ha avuto un ruolo fondamentale nella teoria delle somme. Egli, nel Les methodes nouvelles de la Mécanique céleste, spiega gli approcci differenti al significato di convergenza.
115
1730. Metodo di Stirling
Nella prefazione del Tractatus de Summatione et Interpolatione Serierum Infinitarum (1730) J.Stirling annuncia i suoi obiettivi.
Poiché spesso accade che le serie convergono così lentamente da non arrivare a termine come se fossero divergenti, egli fornisce dei teoremi per raggiungere velocemente i valori di quelle serie il cui approccio è più lento.
116
1742. Formula Eulero-Maclaurin
Nel 1734, Bishop George Berkeley critica l’assenza di fondamenti rigorosi al lavoro di Newton. Per rispondere a queste critiche MacLaurin scrive il suo Treatise on Fluxions nel 1737, ma appare nel 1742.
117
1736. La costante di Eulero
Nel 1736, Leonhard Euler ha pubblicato nei Commentarii academiae scientiarum Petropolitanae, un articolo riguardante la dimostrazione e l’applicazione della formula Euler-Maclaurin.
118
1926. Il metodo di Aitken
In un articolo pubblicato nel 1926, Aitken ha proposto una estensione del metodo di Bernoulli delle serie ricorrenti.
119
1926. Il metodo di estrapolazione di Richardson
L’idea del metodo è di utilizzare una combinazione lineare di formule per poter affinare l’approssimazione. Il metodo fu stabilito formalmente nel 1911 da Richardson. La teoria fu presentata di nuovo da Richardson nel 1927, questa volta prendendosi cura di spiegarla.Applichiamo la formula all’integrale
Diamo una tabella per mostrare la velocità di convergenza:
per n = 1, 2, 4, 8, 16
120
1955. Il metodo di integrazione di Romberg
Il metodo di Romberg è semplicemente la formula di Richardson applicata iterativamente alla funzione approssimata trapezio T(h).
121
Verso il concetto di algoritmo
La maggior parte di algoritmi erano utilizzati molto tempo prima che si sia reso necessario dare una chiara definizione del significato di algoritmo.
Oggi un algoritmo è definito come un insieme finito e organizzato di istruzioni, in grado di fornire la soluzione ad un problema.
Il termine algoritmo, che significa procedimento di calcolo, è una versione moderna del termine latino medioevale algorismus, che deriva dal nome del matematico Mohammed ibn-Musa-al-Khowarismi, vissuto nel IX secolo d.C. e famoso per aver scritto un noto trattato di algebra.
122
17° secolo. Leibniz immagina un linguaggio a carattere universale capace di ridurre i ragionamenti matematici a semplici calcoli.
1821. Charles Babbage spiega come i ragionamenti matematici possono essere trasformati quasi meccanicamente utilizzando simboli algebrici.
Nel 1930 i matematici sentono il bisogno di ricercare che cosa precisamente costituisce un algoritmo e proporre una definizione del concetto di algoritmo.
123
1885. Pierce estende la logica algebrica alla teoria delle leggi di De Morgan e introduce le Tavole di Verità.
1879. Frege da una prima logica formalizzata.
1889. Peano introduce un linguaggio formalizzato per l’aritmetica.
1854. Boole propone una algebrizzazione della logica. Inoltre introduce una notazione formale per decidere se una proposizione è vera o falsa.
124
Nel 1890 Hilbert sviluppa una concezione formale della matematica. Nel 1904 spiega che vorrebbe ridurre tutta l’aritmetica a logica e formalizza ciò nel 1922. Al congresso internazionale del 1928 Hilbert ha proposto un programma di ricerca in forma di problemi. Egli pone tre questioni fondamentali di matematica:
1928. Hilbert
Meno di dieci anni più tardi si è visto che non era possibile dare una risposta affermativa alle domande di Hilbert.
1. La matematica è completa, ossia ogni statement matematico può essere dichiarato valido o non valido ?
2. La matematica è consistente, ossia è impossibile dimostrare sia uno statement che la sua contraddizione ?
3. La matematica è decidibile, ossia esiste una procedura con la quale si può decidere se uno statement matematico è vero ?
125
Nel 1931 Kurt Godel dimostra l’incompletezza dell’aritmetica: esistono proposizioni in aritmetica per le quali è impossibile dimostrare se sono vere o false. Per dimostrare il teorema Godel introduce la nozione di funzione ricorsiva. Nel 1934 egli da una corso a Princeton e definisce il concetto generale di funzione ricorsiva.
1931. Godel
126
Il lavoro di Godel ha inspirato le ricerche di Alonzo Church, Stephen Kleene, Alan Turing ed Emil Post.Questi matematici dimostrano che esistono problemi indecidibili, ossia proposizioni matematiche per le quali non esistono procedure con le quali possiamo dire se la proposizione è vera o falsa. Per fare ciò ognuno da un concetto di algoritmo.
Il concetto di funzione ricorsiva è l’argomento centrale del lavoro di Church.
1936. Church
127
L’articolo di Kleene del 1936, intitolato Funzioni Generali Ricorsive di Numeri Naturali, riguarda principalmente il concetto di funzione ricorsiva e l’equivalenza tra definizioni differenti.
1936. Kleene
Il problema dell’equivalenza tra tutti i concetti di calcolabilità stabiliti tra il 1931 e il 1936 è fondamentale:
Garantisce la coerenza dei risultati ottenuti
Conferma se il concetto di algoritmo corrisponde alla nozione di algoritmo e alla nozione intuitiva che abbiamo di esso.
128
Il concetto di macchina è l’idea chiave dell’articolo di A.M.Turing del 1936. Il problema è di specificare precisamente cosa significa “con un effettivo processo di calcolo” o “un algoritmo per calcolare”. Questa questione porta Turing a definire ciò che oggi chiamiamo la “macchina di Turing”.
1936. La macchina di Turing
Una macchins di Turing è composta di: un nastro composto di celle contenenti
simboli appartenenti ad un alfabeto finito un’unità centrale che può assumere un
numero finito di stati una testina di lettura-scrittura che permette
la comunicazione tra l’unità centrale e il nastro
129
Pochi mesi dopo Turing e abbastanza indipendentemente, Emil L.Post propone una macchina per definire un processo che potrebbe risolvere un problema generale.
1936. La macchina di Post
Post non parla di macchina sebbene le sue descrizioni somigliano al nostro concetto di computer. Quello che Post chiama box può essere la nostra memoria, che può essere vuota o contenere un valore. Il suo insieme di istruzioni può essere confrontato ad un programma con salti. E’ appropriato descrivere questa formulazione minimale come formulation 1. Infatti solo un simbolo alla volta può essere immesso in memoria e questo può essere spostato solo ad una cella contigua.
130
Il campo degli algoritmi.
Con l’introduzione del concetto di algoritmo si introduce un nuovo campo di scienza: il campo degli algoritmi.
Pur se la teoria degli algoritmi si è andata assestando nella prima metà del XX° secolo, le tecniche per progettare algoritmi e per analizzarne la correttezza e l’efficienza si sono evolute nella seconda metà del secolo, grazie alla enorme diffusione dei calcolatori elettronici.
131
Il campo degli algoritmi.
Gli algoritmi vengono comunemente descritti tramite programmi, che si avvalgono di istruzioni e costrutti dei linguaggi di programmazione e che devono essere eseguiti da calcolatori elettronici.
Lo studio degli algoritmi coinvolge il concetto di complessità di un algoritmo ossia il costo in termini di tempo e quantità di memoria richiesta.
132
1945. Merge Sort Sembra che J. Von Neumann, uno dei pionieri dell’informatica, abbia scritto nel 1945 un programma di merge sort per il calcolatore EDVAC.
1 2 2 3 4 5 6 6
2 4 5 6 1 2 3 6
2 5 4 6 1 3 2 6
5 2 4 6 1 3 2 6
Tempo di Esecuzione: O(nlgn)
Divide et Impera
Algoritmo di sort
133
1947. Algoritmo del simplesso
Nella teoria dell’ottimizzazione matematica l’algoritmo simplex di George Dantzig è la tecnica fondamentale per soluzioni numeriche dei problemi di programmazione lineare.
Dato un sistema di disequazioni lineari su un numero n di variabili reali, l’algoritmo fornisce un metodo pratico per trovare la soluzione ottimale rispetto ad una funzione lineare fissata.
134
L’algoritmo di codifica di Huffman sviluppato da David A. Huffman nel 1952 è un algoritmo usato per la decompressione dei dati.
1952. Huffman coding
L’algoritmo trova il sistema ottimale di codificare stringhe basato sulla frequenza relativa di ogni carattere.
135
1954. Radix Sort
Un algoritmo per il radix sort fu inventato nel 1954 al MIT da Harold H. Seward. Tuttavia l’ordinamento radix sort rispetto alla cifra meno significativa sembra che fosse un algoritmo noto, già ampiamente usato da operatori di macchine meccaniche ordinatrici di schede.Secondo Knuth la prima pubblicazione su questo metodo si trova in un documento del 1929 di L.J.Comrie che descrive le macchine perforatrici di schede.
Algoritmo di sort
136
Il radix sort ordina una sequenza di numeri di n cifre ordinando prima sulla cifra meno significativa, poi l’intero blocco è ordinato di nuovo sulla seconda cifra meno significativa e cosi via.
329
355
720
457
657
839
436
329
355
720
457
657
839
436
457
329
720
839
355
657
436
720
355
329
457
657
839
436
Radix Sort
Algoritmo di sort
137
1954. Counting Sort
Knuth attribuisce ad H.H. Seward sia la progettazione del counting sort (1954), sia l’idea di combinare il counting sort con il radix sort.
Il counting sort si basa sull’ipotesi che ognuno degli n elementi di input sia un intero nell’intervallo da 1 a k. L’idea di base è di determinare, per ogni elemento x di input, il numero di elementi minori di x. Questa informazione può essere usata per porre l’elemento x direttamente nella sua posizione nell’array di output.
Tempo di Esecuzione: O(k+n)
Se K=O(n) Tempo di Esecuzione: O(n)
Algoritmo di sort
138
1956. Algoritmo di Kruskal
L’algoritmo di Kruskal, sviluppato da Joseph Kruskal nel 1956, è un’elaborazione dell’algoritmo generico per trovare un albero di copertura minimo.
Algoritmo sui grafi
Tempo di Esecuzione : O(ElgE)
dove E è il numero di archi
139
1956. Bucket Sort
L’algoritmo Bucket Sort fu proposto da E.J.Isaac e R.C.Singleton.
Il bucket sort assume che l’input sia generato da un processo casuale che distribuisce gli elementi in modo uniforme sull’intervallo [0,1). L’idea del bucket sort è di dividere l’intervallo [0,1) in n sottointervalli di uguale dimensione, detti bucket (secchi), e quindi distribuire gli n numeri nei bucket. Per produrre l’output, si ordinano i numeri di ogni bucket e quindi si elencano gli elementi di ogni bucket prendendoli in ordine.
Tempo di Esecuzione nel caso medio: O(n)
Algoritmo di sort
140
1957. Algoritmo di Prim
L’algoritmo, sviluppato da Robert Prim nel 1957, è un’elaborazione dell’algoritmo generico per trovare un albero di copertura minimo.
Algoritmo sui grafi
Tempo di Esecuzione : O(ElgV)
dove V è il numero di vertici
ed E è il numero di archi
O(E+VlgV) se si usa un heap di Fibonacci
141
L’algoritmo sviluppato da R. Bellman and L. R. Ford calcola il cammino più corto in un grafo pesato.
1957. Algoritmo di Bellman-Ford
Tempo di Esecuzione : O(VE)
dove V è il numero di vertici
ed E è il numero di archi
Algoritmo sui grafi
142
1959. Algoritmo di Dijkstra
L’algoritmo sviluppato da Edsger Dijkstra risolve il problema di cammini minimi con sorgente singola su un grafo orientato e pesato G=(V,E) nel caso in cui tutti i pesi degli archi siano non negativi.
Algoritmo sui grafi
Tempo di Esecuzione : O(V2)
143
1959. Shell Sort
L’algoritmo fu sviluppato da D.L. Shell.
Lo shell sort è una variante dell’algoritmo di insertion sort. Esso usa insertion sort su sottosequenze periodiche dell’input ottenendo un algoritmo di ordinamento più veloce.
3
5
1
2
4
5
1
2
4
3
2
1
5
4
3
2
1
4
5
3
Algoritmo di sort
144
1962. Quicksort L’algoritmo sviluppato da Charles Antony Richard Hoare utilizza il paradigma divide-et-impera.
4 2 3 5 1
1 2 3 5 4
1 2 3 4 5
pivot
Algoritmo di sort
145
1962. Ford-Fulkerson
L’algoritmo sviluppato da L. R. Ford e D. R. Fulkerson risolve il problema di flusso massimo per reti di flusso. Esistono diverse realizzazioni dell’algoritmo con differenti tempi di esecuzione.
Algoritmo sui grafi
146
1964. Heapsort L’algoritmo heapsort fu progettato da J. W. J. Williams che descrisse anche come realizzare una coda con priorità tramite uno heap. La procedura BUILD-HEAP fu proposta da Floyd.
14
8
2 4
7
1
16
8
2 4
16
8
4
2 1
7
14
10
9 3
14
8
4
2
7
10
9
1 3
16
Algoritmo di sort
147
14
8
4 7
9
3
1 2
1610 14
7
4 2
8
3
1
1610
9
14
4
1 2
7
3
1610
98
14
2
1
4
3
1610
987
14
2
3
1
1610
9874
14
1
2
1610
9874
3
14
1
1610
9874
32
Heapsort
148
1965. Cooley-Tukey
L’algoritmo riscoperto da James Cooley and John Tukey è il più comune algoritmo fast Fourier trasform (FFT).
Algoritmo FFT
L’algoritmo era già noto nel 1805 per opera di Gauss, ma diventa popolare nel 1965 quando J.W.Cooley dell’IBM e J.W.Tukey di Princeton lo reinventano per eseguirlo su un computer.
149
1965. Distanza di Levenshtein
La distanza di Levenshtein tra due stringhe è data dal numero minimo di operazioni necessarie per trasformare una stringa in un’altra, dove un’operazione è un inserimento, una cancellazione o una sostituzione.
Algoritmo su stringhe
int LevenshteinDistance(char s[1..n], char [1..m]) declare int d[0..n,0..m] declare int i, j, cost for i := 0 to n
d[i,0] := i for j := 0 to m
d[0,j] := jfor i := 1 to n for j := 1 to m if s[i] = t[j] then cost := 0 else cost := 1 d[i,j] := minimum(d[i-1,j ] + 1, // ins. d[i, j-1] + 1, // canc.
d[i-1,j-1] + cost) // sost. return d[n,m]
caso
casa
cassa
22
150
1965. CYK
L’algoritmo Cocke-Younger-Kasami, sviluppato da T.Kasami, determina se e come una stringa può essere generata da una data grammatica context-free.
Algoritmo su stringhe
Tempo di Esecuzione : O(n3)
dove n è la lunghezza della stringa
Lo stesso algoritmo (CYK) è stato sviluppato indipendentemente da D. H. Younger nel 1967.
151
1967. Viterbi
L’algoritmo proposto da Andrew Viterbi è un modo per trovare la sequenza più probabile di stati nascosti che risultano in una sequenza di eventi osservati.
L’algoritmo trova la sua applicazione nella decodifica di codici nei cellulari digitali GSM, modem, satelliti, comunicazioni spaziali, ecc…
152
1972. Graham
L’algoritmo Graham scan sviluppato da Ronald Graham è un metodo per calcolare l’inviluppo convesso di un dato insieme di punti nel piano.
Algoritmo geometrico
Tempo di Esecuzione : O(nlogn)
dove n è il numero di punti
153
1973. RSA
L’algoritmo di crittografia RSA, sviluppato da Clifford Cocks, è un algoritmo asimmetrico per crittografia a chiave pubblica, ampiamente usato nel commercio elettronico.
Algoritmo di crittografia
L’algoritmo fu descritto nel 1977 da Rivest, Shamir e Adleman; le lettere RSA sono le iniziali dei loro cognomi.Cocks, un matematico inglese che lavorava per GCHQ, ha descritto un sistema equivalente in un documento interno nel 1973. A causa della classificazione top-secret, la sua scoperta non è stata resa nota fino al 1997.
154
1973. Jarvis
L’algoritmo Jarvis, sviluppato da R. A. Jarvis, calcola l’inviluppo convesso di un insieme Q di punti attraverso una tecnica conosciuta come impacchettamento.
Algoritmo geometrico
Tempo di Esecuzione : O(NK)
dove N è il numero di punti
e K il numero di vertici di CH(Q)
155
1975. Algoritmo genetico
L’algoritmo genetico (GA), divulgato da John Holland, è un algoritmo usato per trovare soluzioni approssimate a problemi difficili da risolvere attraverso l’applicazione dei principi di biologia evolutiva alla scienza dei computer.
156
1975. Aho-Corasick
L’algoritmo Aho-Corasick, sviluppato da Alfred V. Aho and Margaret J. Corasick, è un algoritmo di ricerca stringhe che esamina un testo per un elemento di un insieme finito di stringhe.
Algoritmo su stringhe
157
1976. Knuth-Morris-Pratt
L’algoritmo Knuth-Morris-Pratt, sviluppato da Donald Knuth and Vaughan Pratt e indipendentemente da J. H. Morris, è un algoritmo per la corrispondenza tra stringhe.
Algoritmo su stringhe
Tempo di Esecuzione : O(n+m)dove n è la lunghezza della stringa
principale
e m è il numero di caratteri nella stringa
158
1977. LZ77 1978. LZ78
LZ77 e LZ78, sviluppati da Abraham Lempel e Jacob Ziv, sono algoritmi di compressione dati lossless (bassa perdita).
Algoritmo di compressione
Questi due algoritmi formano la base per la maggior parte delle variazioni LZ compreso LZW, LZSS ed altri.
159
1981. Quadratic Sieve
Quadratic Sieve (QS), sviluppato da Carl Pomerance, è un algoritmo di fattorizzazione di un intero. Il tempo di esecuzione dipende dalla grandezza dell’intero.
Algoritmo di teoria dei numeri
160
1983. Simulated annealing
Simulated annealing è un approccio probabilistico generico al problema di ottimizzazione globale. L’algoritmo è stato sviluppato indipendentemente da S. Kirkpatrick, C. D. Gelatt ed M. P. Vecchi nel 1983 e da V.Cerny nel 1985.
1 T := T0 2 S := S0 3 E := objective(S) 4 k := 0 5 while terminal condition not true 6 S_new := move(S, T) 7 E_new := objective(S_new) 8 if E_new < E or random() < acceptor(E_new - E, T) 9 S := S_new 10 E := E_new 11 T := schedule(T0, k) 12 k := k + 1
161
1984. LZW
LZW (Lempel-Ziv-Welch) , sviluppato da Terry Welch, è un algoritmo di compressione dati lossless (perdita minore). Quest’algoritmo deriva dagli algoritmi LZ77 e LZ78.
Algoritmo di compressione
162
1988. SNFS
Special Number Field Sieve, sviluppato da John Pollard, è un algoritmo di fattorizzazione di un intero.
Algoritmo di teoria dei numeri
Tempo di Esecuzione :
163
1990. GNFS
General Number Field Sieve, sviluppato dal SNFS da Carl Pomerance, Joe Buhler, Hendrik Lenstra, e Leonard Adleman, è il più efficiente algoritmo conosciuto per fattorizzare interi.
Algoritmo di teoria dei numeri
L’algoritmo utilizza
O(exp( ((64/9) n)1/3 (log n)2/3 ))
passi per fattorizzare l’intero n.
164
1991. IDEA
IDEA (International Data Encryption Algorthm) è stato progettato da Xuejia Lai e James L. Massey.
Algoritmo di crittografia
165
1991. MD5
L’algoritmo MD5 è un algoritmo message digest con un valore hash a 128 bit. Esso è uno della serie di algoritmi message digest sviluppati dal professor Ronald Rivest del MIT.
Algoritmo di crittografia
MD5 è stato ampiamente utilizzato ed era ritenuto crittograficamente sicuro. Nel 1994 si scopre una debolezza che rende l’ulteriore utilizzo del MD5 discutibile. In particolare si è visto che era possibile generare collisioni.
166
1992. Deutsch-Jozsa
Deutsch-Jozsa, proposto da D. Deutsch e R. Jozsa, è un algoritmo quantum. E’ uno dei primi esempi di algoritmi quantum (migliori degli algoritmi convenzionali).
Algoritmo quantum
Un computer quantum è un dispositivo di calcolo che fa uso di fenomeni di meccanica quantistica. In un computer classico i dati sono misurati in bit. In un computer quantum i dati sono misurati in qubit
167
1994. Burrows-Wheeler
Burrows-Wheeler transform (BWT), sviluppato da Michael Burrows and David Wheeler, è un algoritmo usato nelle tecniche di compressione dati.
Algoritmo di compressione
La trasformazione avviene ordinando tutte le rotazioni della stringa e prendendo l’ultima colonna.
168
1995. SHA-1
SHA-1 (Secure Hash Algorithm) è un algoritmo “message digest” progettato dalla NSA (National Security Agency) e pubblicato da NIST (National Institute of Standard and Tecnology).
Algoritmo di crittografia
169
1996. RIPEMD-160
RIPEMD-160 (RACE Integrity Primitives Evaluation Message Digest) è un algoritmo message digest a 160-bit, sviluppato da Hans Dobbertin, Antoon Bosselaers, e Bart Preneel.
Algoritmo di crittografia
170
1999. Yarrow
Yarrow, progettato da Bruce Schneier, John Kelsey e Niels Ferguson, è un generatore di numeri pseudo-casuali crittograficamente sicuro.
Algoritmo di crittografia
Il nome deriva dalla pianta yarrow, i cui steli sono seccati e utilizzati come agente casuale nella divinazione “I Ching”.
171
2000. Rijndael
Rijndael cypher, sviluppato da Joan Daemen e Vincent Rijmen, è un algoritmo block cipher a chiave simmetrica.
Algoritmo di crittografia
Dopo una competizione Rijndael fu selezionato come il successore di DES ed è diventato Advanced Encryption Standard (AES).
172
2001. AES
AES (Advanced Encryption Standard) cypher è un algoritmo basato sul Rijndael e adottato dal NIST (National Institute of Standards and Technology).In crittografia AES è un block cipher adottato come standard dal governo US. Si pensa che venga utilizzato in modo universale e analizzato radicalmente.
Algoritmo di crittografia
173
2002. AKS
AKS (primality test), sviluppato da Manindra Agrawal, Neeraj Kayal e Nitin Saxena del IIT Kanpur, è un algoritmo deterministico di tipo polinomiale che determina se un numero è un numero primo.
Algoritmo di teoria dei numeri
AKS ha una differenza chiave rispetto ad altri algoritmi precedenti sulla primalità: non richiede alcuna ipotesi non dimostrata per ottenere un tempo polinomiale su tutti gli input.
174
http://www.cut-the-knot.org/Curriculum/index.shtml
http://it.wikipedia.org/wiki/Storia_della_matematica
http://www.utm.edu/research/primes/prove/proving.html
http://faculty.ed.umuc.edu/~swalsh/Math%20Articles/MathArt.html
Link
175
www.informationblast.com/Timeline_of_algorithms.html
encyclopedia.thefreedictionary.com/Timeline%20of%20algorithms
www.nationmaster.com/encyclopedia/Timeline-of-algorithms
phatnav.com/wiki/wiki.phtml?title=Timeline_of_algorithms
Link
A History of Algorithms: From the Pebble to the Microchip
by Jean-Luc Chabert, E. Barbin
Introduzione agli algoritmi Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest
Jackson Libri
Il Teorema del pappagallo Denis Guedj
Bibliografia
