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

qq

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.

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