Lze zbohatnout pomoc´ı matematiky? Ctirad Matonoha ´ ˇ v.v.i., Ustav Informatiky AV CR, Pod Vod´ arenskou vˇ eˇ z´ı 2, 182 07 Praha 8
´ AV CR, ˇ v.v.i. Den otevˇren´ych dveˇr´ı UI 3.-4. listopadu 2011
1 C. Matonoha
DOD 2011
Co je matematika
2 C. Matonoha
DOD 2011
Co je matematika n´ ahodn´y kolemjdouc´ı – zpanikaˇr´ı, rychle uteˇce: ”Matematika je u ´plnˇe zbyteˇcn´ a.” ”Vˇsichni matematici jsou podiv´ıni.” ”Matematika jsou poˇcty.” ”Jde o vˇedu o ˇc´ıslech.”
3 C. Matonoha
DOD 2011
Role matematiky matematik odpov´ı: ”Modern´ı svˇet by nemohl existovat bez matematiky.” ”S matematikou lze pˇredpov´ıdat budoucnost.” ”Pomoc´ı matematiky lze zachraˇ novat ˇzivoty.” ”Matematika zviditelˇ nuje neviditeln´e.”
4 C. Matonoha
DOD 2011
Matematika je vˇsude kolem n´ as
ˇzijeme ve svˇetˇe pln´em informac´ı je d˚ uleˇzit´e, abychom nedˇelali chyby pˇri uchov´ av´ an´ı, ˇs´ıˇren´ı a hled´ an´ı tˇechto informac´ı k tomu n´ am slouˇz´ı matematika matematiku lze aplikovat skoro na vˇsechny probl´emy
5 C. Matonoha
DOD 2011
Proˇ c je matematika d˚ uleˇ zit´ a letadlo udrˇzuje ve vzduchu s´ıla (18. st. D. Bernoulli) gravitaˇcn´ı s´ıla (17. st. I. Newton) r´ adiov´e vlny – televize, telefony, radary (19. st. J.C. Maxwell) v´yzkum vesm´ıru – planety, hvˇezdy, ˇcern´e d´ıry, kvazary v´yroba ˇcip˚ u pˇredpovˇed’ poˇcas´ı
6 C. Matonoha
DOD 2011
Matematika a poˇ c´ıtaˇ ce
Poˇc´ıtaˇce – uˇziteˇcn´y n´astroj k poˇc´ıt´ an´ı, pˇrin´ aˇs´ı komplikace: hled´ an´ı pˇribliˇzn´eho ˇreˇsen´ı (pˇresn´e lze m´ alokdy nal´ezt) pracuj´ı s koneˇcnou dimenz´ı probl´em zaokrouhlovac´ıch chyb (koneˇcn´ a aritmetika) pracujeme s nepˇresn´ymi daty (chyba mˇeˇren´ı nebo d˚ usledek pˇredchoz´ıch nepˇresn´ych v´ypoˇct˚ u) chyby se mohou hromadit (m˚ uˇze doj´ıt k destrukci v´ysledk˚ u) je tˇreba zn´ at odhad chyby v´ypoˇctu probl´em efektivity algoritm˚ u (pamˇet’ov´e n´ aroky, rychlost v´ypoˇctu, numerick´e chov´ an´ı, stabilita) Tˇemito ot´ azkami se zab´yv´ a naˇse oddˇelen´ı V´ypoˇcetn´ıch metod: v´yvoj a anal´yza algoritm˚ u pro ˇreˇsen´ı u ´loh vyskytuj´ıc´ıch se v praxi. 7 C. Matonoha
DOD 2011
Aplikace
Google tomografie stavebnictv´ı a pr˚ umysl zpracov´ an´ı sign´ al˚ u a obraz˚ u pˇredpovˇed’ poˇcas´ı ekonomie dopravn´ı probl´em
8 C. Matonoha
DOD 2011
Google
hled´ a informace uloˇzen´e v mnoha webov´ych str´ ank´ ach n´ azev google vych´ az´ı ze slova googol“ oznaˇcuj´ıc´ıho 10100 ” za u ´spˇechem Googlu je matematika (statistika, numerick´ a matematika) navrhli ho Sergey Brin a Larry Page v r´ amci sv´eho v´yzkumu na Stanfordovˇe univerzitˇe web si lze pˇredstavit jako obrovskou matici, se kterou se prov´ ad´ı urˇcit´e v´ypoˇcty (hled´ an´ı vlastn´ıch vektor˚ u) r. 2002: dimenze 2,7 mld
9 C. Matonoha
DOD 2011
Tomografie
J. Radon 1917 ˇsiroce pouˇz´ıv´ ano v l´ekaˇrstv´ı (CT mozku), archeologii, biologii, geofyzice a mnoha dalˇs´ıch vˇed´ ach zobrazov´ an´ı v ˇrezech, tedy strukturn´ı zobrazov´ an´ı stavby bez fyzick´eho naruˇsen´ı celku umoˇzn ˇuje trojrozmˇern´e zobrazen´ı objekt˚ u nam´ısto dvourozmˇern´eho
10 C. Matonoha
DOD 2011
Stavebnictv´ı a pr˚ umysl stavby most˚ u, budov (povˇetrnostn´ı podm´ınky, tajfuny, zemˇetˇresen´ı, povodnˇe) je tˇreba spoˇc´ıtat zat´ıˇzen´ı, vych´ylen´ı konstrukce, v´ydrˇz nosn´ych ˇc´ ast´ı letectv´ı, automobily, vlaky – proudˇen´ı okolo kˇr´ıdel, aerodynamika vytvoˇr´ı se model, kter´y se testuje pro extr´emn´ı podm´ınky je nutn´e zn´ at jak´e chyby se dopust´ıme vojenstv´ı – radary, (de)ˇsifrov´ an´ı zpr´ av (A. Turing – Enigma) elektronika – pˇren´ aˇsen´ı obrazu a zvuku na televizi, mikrovlnn´ a trouba 11 C. Matonoha
DOD 2011
Zpracov´ an´ı sign´ al˚ u a obraz˚ u
Modelov´y pˇr´ıklad: zlodˇej vykrade banku, ujede autem a je pron´ asledov´ an polici´ı dobr´ a zpr´ ava: policie udˇelala foto ˇspatn´ a zpr´ ava: foto je rozmazan´e ˇreˇsen´ı: vz´ıt na pomoc matematiku
12 C. Matonoha
DOD 2011
Pˇredpovˇ ed’ poˇ cas´ı
progn´ oza poˇcas´ı je zaloˇzen´ a na vyuˇzit´ı poznatk˚ u o fyzik´ aln´ıch z´ akonitostech definov´ ano mnoha faktory (tlakem, vlhkost´ı, teplotou, vˇetry) je tˇreba tyto faktory sledovat pomoc´ı technick´ych zaˇr´ızen´ı a pˇr´ıstroj˚ u vytvoˇr´ı se model a pomoc´ı vztah˚ u mezi faktory se vyˇreˇs´ı urˇcit´e rovnice neust´ ale se aktualizuj´ı data a pˇrepoˇc´ıt´ avaj´ı rovnice
13 C. Matonoha
DOD 2011
ˇ ım se zab´ C´ yv´ am j´ a
Optimalizace
14 C. Matonoha
DOD 2011
Optimalizace Optimalizace – snaha o hled´ an´ı optim´ aln´ıho ˇreˇsen´ı mezi existuj´ıc´ımi ˇreˇsen´ımi. Mnoho u ´loh z re´ aln´eho svˇeta vede na ˇreˇsen´ı u ´lohy optimalizace. ˇ Casto se vyskytuje pˇri modelov´ an´ı fyzik´ aln´ıch jev˚ u, minimalizaci n´ aklad˚ u nebo maximalizaci zisku. Formulace probl´emu: min F (x)
x∈Rn
nebo
max F (x)
x∈Rn
kde F vyjadˇruje napˇr. n´ aklady, v´ydˇelek nebo fyzik´ aln´ı syst´em (objektivn´ı funkce). Matematick´ au ´loha optimalizace – snaha o nalezen´ı takov´ych hodnot promˇenn´ych, pro kter´e dan´ a objektivn´ı funkce nab´yv´ a minim´ aln´ı nebo maxim´ aln´ı hodnoty. 15 C. Matonoha
DOD 2011
Omezen´ı
fyzik´ aln´ı z´ akony nebo jin´e syst´emy rovnic: omezen´ı ve tvaru rovnost´ı c(x) = 0 ”Auto mus´ı m´ıt ˇctyˇri kola.” fyzik´ aln´ı realizovatelnost, spolehlivost, kompatibilita: omezen´ı ve tvaru nerovnost´ı d(x) ≥ 0 ”Auto mus´ı jet alespoˇ n 300 km/h.” s omezen´ımi se mus´ı nakl´ adat opatrnˇe: m´ alo => spousta nekvalitn´ıch ˇreˇsen´ı hodnˇe => vylouˇcen´ı vhodn´ych ˇreˇsen´ı nebo neexistence ˇreˇsen´ı
16 C. Matonoha
DOD 2011
Od re´ aln´ eho probl´ emu k matematice
1
Formulace modelu, syst´emu promˇenn´ych, urˇcen´ı objektivn´ı funkce a omezen´ı
2
Shrom´ aˇzdˇen´ı dat, kter´ a definuj´ı konkr´etn´ı probl´em
3
ˇ sen´ı probl´emu a nalezen´ı optim´ Reˇ aln´ıho ˇreˇsen´ı
4
Anal´yza v´ysledk˚ u zda je to to co chceme
5
Zlepˇsen´ı modelu a dat a opˇetovn´e hled´ an´ı optim´ aln´ıho ˇreˇsen´ı
17 C. Matonoha
DOD 2011
Dopravn´ı probl´ em
F.L. Hitchcock 1941 optimalizace rozvozu napˇr. zboˇz´ı ˇci materi´ alu od dodavatel˚ uk odbˇeratel˚ um c´ılem je minimalizovat celkov´e n´ aklady spojen´e s rozvozem, popˇr´ıpadˇe celkovou vzd´ alenost mˇely by b´yt uspokojeny poˇzadavky odbˇeratel˚ u u ´kolem je tedy stanovit, kolik zboˇz´ı ˇci materi´ alu dod´ a kaˇzd´y dodavatel kaˇzd´emu odbˇerateli
18 C. Matonoha
DOD 2011
Uk´ azka matematick´ e formulace M´ ame d´ ano: m dodavatel˚ u s kapacitami a1 . . . am n odbˇeratel˚ u s kapacitami b1 . . . bn cij cena n´ aklad˚ u spojen´ych s rozvozem zboˇz´ı od i . dodavatele k j. odbˇerateli xij promˇenn´e ud´avaj´ıc´ı mnoˇzstv´ı pˇrepravovan´eho zboˇz´ı od i . dodavatele k j. odbˇerateli ´ Uloha dopravn´ıho probl´emu: min
x∈M
m X n X
cij xij
i =1 j=1
pˇriˇcemˇz mnoˇzina M je pops´ ana omezen´ımi m X i =1
xij = bj ,
n X
xij = ai ,
j=1
m X
ai =
i =1
n X
bj ,
xij ≥ 0.
j=1
19 C. Matonoha
DOD 2011
Pˇr´ıklad dopravn´ıho probl´ emu
Poˇcet tv spotˇrebiˇc˚ u jist´e elektro firmy ve skladech (3 dodavatel´e): Praha Brno Ostrava ...
9 000 3 000 2 000
Do urˇcit´ych region˚ u se m´ a dopravit mnoˇzstv´ı (4 odbˇeratel´e): Olomoucko Budˇejovicko Hradecko Jihlavsko ...
6 4 3 1
000 000 000 000
20 C. Matonoha
DOD 2011
Pˇr´ıklad dopravn´ıho probl´ emu
N´ aklady na dopravu jednoho kamionu (pojme 100 spotˇrebiˇc˚ u):
Praha Brno Ostrava
cij i =1 i =2 i =3
j =1 c11 = 2 800 c21 = 800 c31 = 1 000
OL 2 800 800 1 000
CB 1 600 2 100 3 800
j=2 c12 = 1 600 c22 = 2 100 c32 = 3 800
HK 1 200 1 700 2 400
JI 1 300 900 2 600
j=3 c13 = 1 200 c23 = 1 700 c33 = 2 400
j =4 c14 = 1 300 c24 = 900 c34 = 2 600
21 C. Matonoha
DOD 2011
Pˇr´ıklad dopravn´ıho probl´ emu Objektivn´ı funkci lze napsat ve tvaru: F (x) = 2 800 x11 + 1 600 x12 + 1 200 x13 + 1 300 x14 + 800 x21 + 2 100 x22 + 1 700 x23 +
900 x24 +
1 000 x31 + 3 800 x32 + 2 400 x33 + 2 600 x34 + ... Hled´ ame takov´e hodnoty x11 . . . x34 . . . (poˇcty kamion˚ u), napˇr. x11 – poˇcet kamion˚ u z Prahy na Olomoucko, aby F (x) bylo minim´aln´ı: ? min F (x) ? 22 C. Matonoha
DOD 2011
Pˇr´ıklad dopravn´ıho probl´ emu Pˇrid´ ame dva typy omezen´ı: 1
Praha m´ a na skladˇe 9 000 spotˇrebiˇc˚ u = 90 kamion˚ u: x11 + x12 + x13 + x14 + · · · = 90 Analogicky pro Brno, Ostravu, atd.
2
Na OL se m´ a dopravit 6 000 spotˇrebiˇc˚ u = 60 kamion˚ u: x11 + x21 + x31 + · · · = 60 Obdobnˇe pro Budˇejovicko, Hradecko, Jihlavsko, atd.
Pˇrid´ ame-li poˇzadavek, aby vˇsechny promˇenn´e byly kladn´e: xij > 0
∀i , j,
m´ ame kompletn´ı u ´lohu. 23 C. Matonoha
DOD 2011
Minimalizace n´ aklad˚ u, maximalizace zisku Dopravn´ı probl´em – bˇeˇzn´y u poˇc´ıtaˇc˚ u, telefon˚ u: skl´adaj´ı se z mnoha souˇc´ astek souˇc´ astky se vyr´abˇej´ı po cel´em svˇetˇe vyuˇzit´ı levn´e pracovn´ı s´ıly kompletuj´ı se na jednom, dvou, tˇrech m´ıstech hotov´e se doprav´ı do nˇekolika sklad˚ u dopravn´ı probl´em: jak minimalizovat n´ aklady a t´ım maximalizovat zisk 24 C. Matonoha
DOD 2011
Jak ˇreˇsit optimalizaˇ cn´ı probl´ emy? ´ vyv´ıj´ıme software (L. Lukˇsan – UFO): V UI slouˇz´ı k ˇreˇsen´ı v´yˇse uveden´ych i mnohem obecnˇejˇs´ıch probl´em˚ u obsahuje r˚ uzn´e metody na ˇreˇsen´ı probl´em˚ u metody: navrhujeme, testujeme, srovn´ av´ ame, vylepˇsujeme algoritmy jsou podloˇzeny matematickou teori´ı teorie je ned´ılnou souˇc´ ast´ı v´yzkumu ve srovn´ an´ı s konkurenc´ı je n´ aˇs software velmi u ´spˇeˇsn´y 25 C. Matonoha
DOD 2011
Jak´ a je matematika?
ˇzivot by bez matematiky nemohl existovat 26 C. Matonoha
DOD 2011
Lze zbohatnout pomoc´ı matematiky?
27 C. Matonoha
DOD 2011
Lze zbohatnout pomoc´ı matematiky? ANO Bohatstv´ı = u ´ˇcinn´e n´ astroje v l´ekaˇrstv´ı principy v pr˚ umyslu telekomunikace dopravn´ı probl´em duˇsevn´ı bohatstv´ı
28 C. Matonoha
DOD 2011
Lze zbohatnout pomoc´ı matematiky? ANO Bohatstv´ı = u ´ˇcinn´e n´ astroje v l´ekaˇrstv´ı principy v pr˚ umyslu telekomunikace dopravn´ı probl´em duˇsevn´ı bohatstv´ı Kdo bohatne d´ıky matematice? A. Google, Apple, Microsoft, Intel B. Matematici 29 C. Matonoha
DOD 2011
Lze zbohatnout pomoc´ı matematiky? ANO Bohatstv´ı = u ´ˇcinn´e n´ astroje v l´ekaˇrstv´ı principy v pr˚ umyslu telekomunikace dopravn´ı probl´em duˇsevn´ı bohatstv´ı Kdo bohatne d´ıky matematice?
A. Google, Apple, Microsoft, Intel B. Matematici
30 C. Matonoha
DOD 2011
