Kapitoly z diskrétní matematiky, Nešetřil, Matoušek
Tato knížka je naprosto super.
Muzu dvakrat podtrhnout, a dodat, ze to byl prvni dulezity bod, proc se nakonec misto programovanim zivim diskretni matematikou :-)
Já jsem bohužel tu knihu našel až hodně pozdě ...
Mohl bys aspoň obecně popsat co děláš? Jsem programátor, ale začal jsem se (znovu) učit matematiku a doufám, že jednou ji budu používat víc v rámci programování. Dělám GISy, takže se nedá říct, že bych žádnou matematiku nepotřeboval. Potenciál pro daší využití matematiky vidím v implementacích optimalizací v rámci GIS systémů.
Muzu, ale bude to nejspis znit jako odpoved od matematika, tzn. "naprosto presna, a naprosto nanic" - delam akademicky vyzkum v diskretni matematice (
http://honza.ucw.cz/ ).
Ale OK, zkusim napsat i neco, co (mozna?!) ma sanci znit trochu vic "sexy" pro typickeho ctenare root fora: nektere ulohy v diskretni matematice lze prevest na ulohy linearni optimalizace - ta spravna "sprosta" slova jsou linearni programovani -
https://cs.wikipedia.org/wiki/Line%C3%A1rn%C3%AD_programov%C3%A1n%C3%AD, semidefinitni programovani -
https://en.wikipedia.org/wiki/Semidefinite_programming, atd... Vsuvka / SPOILER ALERT - v tomhle kontextu slovo programovani nijak nesouvisi s *programovanim* . Nicmene, pro reseni uloh linearniho a do jiste miry i semidefintniho programovani jsou efektivni algoritmy (teoreticky, a v zasade i prakticky). Takze clovek muze napsat program (ten pocitacovy) co z danyho problemu v diskretni matematice udela zadani pro resic semidefintniho programu, a pak necha pocitac chroupat. A na konci, kdyz ma stesti, vypadne dukaz matematicky vety.
Trochu zjednodusena ilustrace - napr. v tech Kapitolach z DM je uloha "grafy bez ctyrcyklu" , a jeji "ucebnicove" reseni s dukazem. De-facto uplne stejny dukaz je i v knizce od Jukny, viz. obrazek na
https://math.stackexchange.com/questions/4399805/maximal-number-of-edges-in-c-4-free-graph . Po "trose" treninku tenhle dukaz neni vlastne nic jineho, nez fikane pouziti nekolika standardnich nerovnosti, z nichz nejhlubsi je Cauchy-Schwarz. Konecne prichazi moje *punchline* - lze zformulovat semidefitni program, ktery rika "najdi nejlepsi odhad na pocet hran grafu bez 4-cyklu za pomoci ruznych Cauchy-Schwarzu" , pocitac zachroupe, a vyplivne to same. A k cemu to, kdyz tohle je dnes prakticky na kazdy prednasce o Teorii grafu? No tenhle mazany dukaz je dost kratky na to, aby sel udelat rucne, ale nektery vety se umi dokazat sice stejnym zpusobem, ale popis tech nerovnosti ma 100MB ci vic, a to bych teda rucne delat nechtel :-). Zamlcuju tu radu podstatnych detailu, napr. ze ten solver pouziva nepresnou floating point aritmetiku, takze se musi makat trochu vic, aby clovek nakonec vyextrahoval skutecne presne zlomky, ktery davaji spravny vysledek; tohle zrovna ja umim docela dobre :-)
Zkoumam i jiny veci, ale uz takhle nevim, na kolik bylo predchazejici on-topic. Nedavno jsem dostal ukol napsat clanek o necem z vyzkumu do CVUTiho casopisu -
https://media.cvut.cz/cs/publikace/20221209-prazska-technika-6-2022#page/26 (jsou tam popsany docela podobny problemy, jako tahle ilustrace, ale z jinyho uhlu pohledu)
Back to reality - Kapitoly jsou opravdu povedena knizka, ale urcite s primarnim durazem na teorii. Zkusim zde udelat promo trochu praktictejsi (stale vsak zcela rigorozni!) knizce kamaradum "od vedle",
http://pruvodce.ucw.cz/ - PDF je zdarma, tistene prodava vetsina knihkupectvi. BTW, oba autori jsou byvali studenti u Nesetrila, jednoho z autoru Kapitol z DM.
Zobrazit příspěvky
.