MATEMATICA E INFORMATICA - eventi.uniurb.it · Cosa ci serve per valutare la complessità di un...

MATEMATICA E INFORMATICA

alessandro bogliolo

http://codemooc.org/algomooc/

Urbino 2 febbraio 2018

La complessità nascosta degli algoritmi che ci semplificano la vita

1506 . UNIVERSITA DEGU STUDI DI URBINO CARLO BO

alessandro.bogliolo@uniurb.it

Uno più uno

alessandro.bogliolo@uniurb.itCont

2 https://blockly-demo.appspot.com/static/demos/code/index.html

51 2 3 4

calcola 3 p i ù 2 : annulla i l risultato ripeti 3 volte

incrementa risulta t o ripeti 2 volte

incrementa ris u lta t o mostra risultato

ca lcola3piu2

Next i • 1 to 3

Done risulato = risuftato+1

Next i • 1 to2

Done risulato = risuftato+1

Output risultato

( End )

alessandro.bogliolo@uniurb.itCont

somma A e B : annulla risultato ripeti A volte

incrementa risultato ripeti B volte

incrementa r isul t ato restituisci il risultato

somma (lnteger A, lnteger 6)

risultato• risulato+1

( Return lnteger risultato )

Output somma(3,2)

alessandro.bogliolo@uniurb.itUsia

l’ass

1 somma A e B : 2 assegna A a r is u l t a t o 3 ripeti B volte 4 5

incrementa risultato restituisci il risul t ato

somma ( lnteger A , lnteger 6 )

y t,1ext

i = 1 toB

Done r isuttato • r isultato+1

Return lnteger r isultato

Output somma(3,2)

1 somma A e B : 2 se A< B allora 3 assegna Ba risul t a t o 4 assegna A a inc 5 altrimenti 6 assegna A a risul t a t o 7 assegna Ba inc 8 ripeti inc volte 9 incrementa risul t a t o

10 restituisci risul t a t o

a 3 4 7 6 +5 8 3 1 =

Il Il Il Il

Complessità

alessandro.bogliolo@uniurb.itIn te

Cosa ci serve per valutare la complessità di un algoritmo?

Dimensione dei dati su cui opera

Numero di passi elementari espressi in funzione di n Funzione monotona crescente

alessandro.bogliolo@uniurb.itIn p

! " = 5 ! " = %&( ) ( )

! " = 2 + " ∗ 2 + 1 = " ∗ 2 + 3 ! " = )* + )+"( ) ( )

! " = 2 + &(") ∗ 2 + 1 = &(") ∗ 2 + 3 ! " = ,- + ,.&(")( ) ( )

alessandro.bogliolo@uniurb.itCom

! " = 2 + " ∗ 1 + " ∗ 2 = 2 + 3 ∗ "

! " = )* + )+," + )+-"

! " = 2 + " ∗ (" ∗ 1) ! " = *+ + " ∗ *, + " ∗ *- = *+ + *," + *-"-( ) ( ) ( ( ))

! " = 2 + " ∗ " ∗ (2 + " ∗ 1 + 1)

! " = *+ + *," + *-"- + *.".

alessandro.bogliolo@uniurb.itCos’

quantità

valore

dimensione

alessandro.bogliolo@uniurb.itPer e

Operazione elementare: incremento unitarion = secondo addendo

1 somma A e B :

2 assegna A a ris u ltat o 3 ripeti B volte 4 incrementa risulta t o 5 restituisci il risultat o

alessandro.bogliolo@uniurb.itO g

! " ∈ %(# " ) ( ) # "

( ) ( )

=le > O, no E N: 'rin > no, lf(n) I < clg(n) I

alessandro.bogliolo@uniurb.itO g

e! " = 2 + " ∗ " ∗ (2 + " ∗ 1 + 1)

! " = 2 + " ∗ " ∗ 2 + " ∗ 1 + 1 = 2 + 3 ∗ "+ + ",./(",)

( ) ( )

alessandro.bogliolo@uniurb.itOpe

Incremento

Addizione a una cifra

Addizione a un numero limitato di cifre

Moltiplicazione a un numero limitato di cifre

ESPERIMENTON. 1Calcolatrice

Quando ti tocco la testaAppoggia la mano sinistra sulla spalla destra della persona davanti a te

Quando ti toccano la spalla destraAppoggia la mano destra sulla spalla destra della persona davanti a te

Quando ti tocco la testaAppoggia la mano sinistra sulla spalla sinistra della persona davanti a te

Quando hai un numero dispari di mani che ti toccanoAlza la mano sinistra

Quando hai più di una mano che ti tocca Con la mano destra tocca il braccio del vicino alla tua destra

8 4 2 1

alessandro.bogliolo@uniurb.itQua

alessandro.bogliolo@uniurb.itE’ a

Caso ottimo

Caso medio

Caso pessimo

Due per due

alessandro.bogliolo@uniurb.it2x3

6 passi

alessandro.bogliolo@uniurb.itA*B

ti rip

i 1 moltiplica A e B : 2 annulla ri s u lta t o 3 ripeti B volte 4 ripeti A volte 5 incrementa risultato 6 restituisci risultato

alessandro.bogliolo@uniurb.itA*B

1 moltiplica A e B : 2 annulla risultato 3 ripeti B volte 4 incrementa risultato di A 5 restituisci risultato

3 2 1 x2 3 =

lii lii lii lii

alessandro.bogliolo@uniurb.itMa

321x23

3 2 1 x2 3 =

9 6 3 +6 4 2 _ =7 3 8 3

1 2 3 4 5 6 7 8 9 101 1 2 3 4 5 6 7 8 9 102 2 4 6 8 10 12 14 16 18 203 3 6 9 12 15 18 21 24 27 304 4 8 12 16 20 24 28 32 36 405 5 10 15 20 25 30 35 40 45 506 6 12 18 24 30 36 42 48 54 607 7 14 21 28 35 42 49 56 63 708 8 16 24 32 40 48 56 64 72 809 9 18 27 36 45 54 63 72 81 9010 10 20 30 40 50 60 70 80 90 100

L’im

lle ta

alessandro.bogliolo@uniurb.itL’im

lle ta

1 2 3 4 5 6 7 8 9 101 1 2 3 4 5 6 7 8 9 102 2 4 6 8 10 12 14 16 18 203 3 6 9 12 15 18 21 24 27 304 4 8 12 16 20 24 28 32 36 405 5 10 15 20 25 30 35 40 45 506 6 12 18 24 30 36 42 48 54 607 7 14 21 28 35 42 49 56 63 708 8 16 24 32 40 48 56 64 72 809 9 18 27 36 45 54 63 72 81 9010 10 20 30 40 50 60 70 80 90 100I

0 1 2 3 4 5 6 7 8 9 100 0 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 9 102 0 2 4 6 8 10 12 14 16 18 203 0 3 6 9 12 15 18 21 24 27 304 0 4 8 12 16 20 24 28 32 36 405 0 5 10 15 20 25 30 35 40 45 506 0 6 12 18 24 30 36 42 48 54 607 0 7 14 21 28 35 42 49 56 63 708 0 8 16 24 32 40 48 56 64 72 809 0 9 18 27 36 45 54 63 72 81 9010 0 10 20 30 40 50 60 70 80 90 100

L’im

lle ta

0 1 2 3 4 5 6 7 8 90 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 92 0 2 4 6 8 10 12 14 16 183 0 3 6 9 12 15 18 21 24 274 0 4 8 12 16 20 24 28 32 365 0 5 10 15 20 25 30 35 40 456 0 6 12 18 24 30 36 42 48 547 0 7 14 21 28 35 42 49 56 638 0 8 16 24 32 40 48 56 64 729 0 9 18 27 36 45 54 63 72 81

L’im

lle ta

0 1 2 3 4 5 6 7 8 90 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 92 0 2 4 6 8 10 12 14 16 183 0 3 6 9 12 15 18 21 24 274 0 4 8 12 16 20 24 28 32 365 0 5 10 15 20 25 30 35 40 456 0 6 12 18 24 30 36 42 48 547 0 7 14 21 28 35 42 49 56 638 0 8 16 24 32 40 48 56 64 729 0 9 18 27 36 45 54 63 72 81

L’im

lle ta

nepassi

moltip

licazione

addizio

Chi cerca trova

alessandro.bogliolo@uniurb.itTutt

0 1 2 3 4 5 6

alunno[i]

altezza[i]

taglia[i]

peso[i]

175 165 110 180 150 100 170

0 1 2 3 4 5 6

indice

altezza

175 165 110 180 150 100 170

0 1 2 3 4 5 6

dell’a

indice

altezza

-1posizione

n = numero di elementi

Complessità: O(n)

1 2 3 4 5 6 7

trova h in altezza : N = l u ng hezza di a l te zz a ; po si z i one = -1 ; per i da O a N- 1

se altezza [i] == h allora . . . po sizi one= i

restituisci p o sizi on e

175 165 110 180 150 180 170

0 1 2 3 4 5 6

dell’a

indice

altezza

-1posizione

Quale posizione restituisce la funzione?

1 2 3 4 5 6 7

trova h in altezza : N = l u ng hezza di a l te zz a ; po si z i one = -1 ; per i da O a N- 1

se altezza [i] == h allora . . . po sizi one= i

restituisci p o sizi on e

175 165 110 180 150 100 170

0 1 2 3 4 5 6

o l’a

indice

altezza

posizione

Complessità: O(n)

Caso ottimo: O(1)Caso medio: O(n/2) = O(n)Caso pessimo: O(n)

1 2 3 4 5 6 7 8 9

trova h in altezza : N = l u nghezza di altezza ; p o sizi o ne = - 1 ; i= O; finché i <N e p o sizi o ne== - 1

se altezza[i] == h allora . . . p o siz i one= i ;

i= i+l ; restituisci o sizi o ne

175 165 110 180 150 180 170

0 1 2 3 4 5 6

indice

altezza

posizione

1 2 3 4 5 6 7 8 9

trova h in altezza : N = l u nghezza di altezza ; p o sizi o ne = - 1 ; i= O; finché i <N e p o sizi o ne== - 1

se altezza[i] == h allora . . . p o siz i one= i ;

i= i+l ; restituisci o sizi o ne

175 165 110 180 150 100 170

0 1 2 3 4 5 6

ax? indice

altezza

posizione

i1 trova massimo di altezz a : 2 N = l unghezz a di al tezz a ; 3 po si z i on e = O; 4 per i da O a N- 1 5 6 7

se altezza[ i] > a l tezza [pos i z i one] . . . pos i zione= i

restituisci po si z i one

100 110 150 165 170 175 180

0 1 2 3 4 5 6

l’ar

indice

altezza

Complessità: O(n)

Caso ottimo: O(1)Caso medio: O(n/2) = O(n)Caso pessimo: O(n)

1 trova h in altezza : 2 N = lunghezza di altezza ; 3 posizione= - 1 ; 4 i= O; 5 finché i <N e altezza[i]<=h 6 se altezza[i] == h allora 7 posizione= i ; 8 i= i+l ; 9 restituisci os izi one

100 110 150 165 165 175 180

0 1 2 3 4 5 6

l’ar

indice

altezza

1 trova h in altezza : 2 N = lunghezza di altezza ; 3 posizione= - 1 ; 4 i= O; 5 finché i <N e altezza[i]<=h 6 se altezza[i] == h allora 7 posizione= i ; 8 i= i+l ; 9 restituisci os izi one

100 110 150 165 170 175 180

0 1 2 3 4 5 6

indice

altezza

inizio

1 trova h in altezza : 2 N = lunghezza di altezza; 3 i nizio = O; 4 f i ne= N-1 ; 5 finché inizi o< fine 6 mezzo= int ((inizio+ fine) /2) ; 7 se altezza[mezzo] >= h allora 8 fine = mezzo ; 9 altrimenti

10 inizi o = mezzo+l ; 11 se altezza[mezz o] = h allora 12 13 14 15

posizione - mezzo ; altrimenti

posizione - - 1 ; restituisci posizione

100 110 150 165 170 175 180

0 1 2 3 4 5 6

indice

altezza

inizio

1 trova h in altezza : 2 N = lunghezza di altezza ; 3 i nizio= O; 4 fine= N-1 ; 5 finché inizi o< f i ne 6 mezzo= int((inizi o+ fine)/2) ; 7 se altezza[mezzo] >= h allora 8 fine = mezzo ; 9 altrimenti

10 inizi o = mezzo+l ; 11 se altezza[mezzo] = h allora 12 posizione - mezzo ; 13 altrimenti 14 posizione - - 1; 15 restituisci posizione

100 110 150 165 170 175 180

0 1 2 3 4 5 6

indice

altezza

inizio

100 110 150 165 170 175 180

0 1 2 3 4 5 6

indice

altezza

inizio

Complessità: O(log(n))

100 110 150 165 170 175 180

0 1 2 3 4 5 6

? indice

altezza

1 trova h in altezza: 2 N = l unghezza di al t ezza ; 3 se N > 1 allora 4 mezzo = i nt((N-1)/2) ; 5 se altezza[mezzo] >= h allora 6 pos i zione= trova h in a l tezza [ O, mezzo] ; 7 altrimenti 8 pos i z i one += trova h in a l tezza[mezzo + l , N-1 ]; 9 altrimenti

10 se altezza[O] - h allora 11 12 13 14

pos i z i on e - O; altrimenti

pos i zione -1 ; restituisci posizione

Mettiamo in ordine

7+6+5+4+3+2+17*6/2

2(1)IN

3(1)IN

4(3)IN

5(4)IN

6(1)IN

1+1+3+4+1+4<7*6/2

La rete, lo spazio e il tempo

ESPERIMENTON. 2Routing

Quando un tuo vicino ti tocca la spallaSe sei sedutoAlzatiRicorda posizione del tuo vicinoFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto

seduto

alzato

seduto

alzato

seduto

alzato

seduto

alzato

seduto

alzato

seduto

alzato

seduto

alzato

seduto

alzato

seduto

alzato

0••••••••••••• ••••••• •••••• •••••••••••••• •• • •••• •••••• ••••••• ••••••

1••••••••••••• ••••••• •••••• • ••• •••••••••• • • • • ••• •••••• • ••• ••• ••••••

2••••••••••••• ••••• •• •••••• • ••• • ••••••••• • ••• • •• •••••• • ••• • •• ••••••

3•••••• ••••••• ••••• • • •••••• ••••• • •••••••• ••••• • • •••••• ••••• • • ••••••

4•••••• • •••••• •••••• • •••••• •••••• • ••••••• •••••• • •••••• •••••• • ••••••

5••••••••••••• ••••••• •••••• ••••••• • •••••• ••••••• •••••• ••••••• ••••••

6••••••••••••• ••••••• • ••••• •••••••• • ••••• ••••••• • ••••• ••••••• ••••••

7••••••• •• •••• ••••••• • • •••• ••••••••• • •••• ••••••• • • •••• ••••••• •• ••••

8••••••••• • ••• ••••••• •• • ••• •••••••••• • ••• ••••••• •• • ••• ••••••• •• • •••

9•••••••••• • •• ••••••• ••• • •• ••••••••••• • •• ••••••• ••• • •• ••••••• ••• • ••

10••••••••••• • • ••••••• •••• • • •••••••••••• • • ••••••• •••• • • ••••••• •••• • •

11•••••••••••• • ••••••• ••••• • ••••••••••••• • ••••••• ••••• • ••••••• ••••• •

TUTocca a te, ma…Quando dico «Via!»Se sei AnnaAlzatiFinchè ci sono tuoi vicini sedutiTocca la spalla di un tuo vicino seduto

Quando un tuo vicino ti passa il suo messaggiopassa il messaggio al vicino di cui ricordi la posizione

sorgentedestinazione

••••••••••••• ••••••• •••••• ••••• ••• •••••• •• • •• •• •• •••• ••••••• •• • •••

alessandro.bogliolo@uniurb.ithttp://informatica.uniurb.it/

http://codemooc.org/algomooc/

’att

MATEMATICA E INFORMATICA - eventi.uniurb.it · Cosa ci serve per valutare la complessità di un...

Documents

Transcript of MATEMATICA E INFORMATICA - eventi.uniurb.it · Cosa ci serve per valutare la complessità di un...

Dipartimento di Matematica e Informatica

Corso integrato di Matematica, Informatica e Statistica Informatica di base Linea 1 Daniela Besozzi Dipartimento di Informatica e Comunicazione Università

VADEMECUM della Facoltà di SCIENZE POLITICHE - uniurb.it · LA GUERRA FREDDA RESPONSABILE URBINATE: prof. Massimiliano GUDERZO E-mail: m.guderzo@uniurb.it . 5 FACOLTÀ DI SCIENZE

Matematica per leconomia e le scienze sociali Gian Italo Bischi Dipartimento di Economia, Società e Politica Università di Urbino Carlo Bo gian.bischi@uniurb.it.

Università degli studi di Catania - INFORMATICA MATEMATICA ... · Università degli studi di Catania - INFORMATICA A.A. 2014-2015 MATEMATICA E INFORMATICA - Y70 INFORMATICA [X81]

la prova di matematica al BAC europeo · 2014. 10. 7. · Dipartimento di Matematica e Informatica Matematica&Realtà Esami senza frontiere: la prova di matematica al BAC europeo

Bioinformatica: un mix tra Biologia, Matematica e Informatica. Luca Bortolussi Dipartimento di Matematica e Informatica, Universita di Udine. luca.bortolussi@dimi.uniud.it.

Analisi di situazione · 10.30/11.00 ITALIANO MATEMATICA INGLESE MATEMATICA INFORMATICA SCIENZE ... 14.30/15.00 SCIENZE GEOGRAFIA STORIA INFORMATICA LABORATORIO ... un’idea di un

Riccardo Moschetti Matematica, ﬁsica, informatica UNIPR ...

Laboratorio di Informatica - di.univaq.it · Laboratorio di Informatica Corso di Laurea in Matematica A.A. 2007/2008 Dott. Davide Di Ruscio Dipartimento di Informatica Università

Matematica Matematica con Informatica Matematica e … · 2020. 11. 27. · ISTITUTO d’ISTRUZIONE SUPERIORE “E.TORRICELLI” MILANO MODELLO PRO -DID MAT Progettazione didattica

MATEMATICA PER INFORMATICA - ripmat.it PER INFORMATICA.pdf · Prof. Dino Betti-Ripasso di matematica: MATEMATICA PER INFORMATICA-PDF elaborato da Vincenzo Solimando 3 raggruppati,

INTERNET - Dipartimento di Matematica e Informatica

DIPARTIMENTO DI MATEMATICA, INFORMATICA ED ECONOMIA

Corso zero 2007 - Dipartimento di Matematica e Informatica

Elementi di matematica e informatica - Unicamcomputerscience.unicam.it/marcantoni/restauro/lezione00.pdfElementi di matematica e informatica modulo informatica fausto.marcantoni@unicam.it

Matematica di base - Profs Area Scienze ed Ingegneriaprofs.sci.univr.it/~gregorio/MatematicaDiBase.pdf · Dipartimento di Informatica — Settore di Matematica Matematica di base

DiMaI - Dipartimento di Matematica e Informatica "Ulisse Dini"

Matematica con elementi di Informatica - MathUniPDvargiolu/MatCTF/CTFIntegrali.pdf · 2019-12-06 · Teoria dell’integrazione Matematica con elementi di Informatica Tiziano Vargiolu

Corso integrato di Matematica, Informatica e Statistica Informatica di base Linea 1