dovoluji si Vám v souvislosti se zahájeným předběžným zápisem nabídnout možnost zapsat si předmět Algoritmy Vizuálně (BI-AVI.21), který je volným pokračováním předmětů Programování a algoritmizace 1,2 (PA1,PA2) a Algoritmy a grafy 1 (AG1). AVI podobně jako předmět Algoritmy a grafy 2 (BI-AG2.21) tyto předměty dále rozvíjí, ale jde jiným směrem, který lze charakterizovat jako prezentaci pokročilejších algoritmů, které se používají při praktickém využívání informatiky v denním životě, zatímco AG2 jde spíše k teoretickým aplikacím algoritmů. Velmi stručný popis nejzajímavějších algoritmů, přednášených v AVI, najdete na konci tohoto emailu.
S příchodem AI bude podle mého názoru dobrá znalost algoritmů ještě důležitější. Minulý měsíc jsem byl moderátorem panelové diskuse na Global Conference on Computer Science Education, pořádané americkou Association for Computing Machinery; jejím tématem byly změny pohledu na programování s příchodem nástrojů jako je Copilot nebo ChatGPT a převládá názor, že zatímco konečnou implementaci programu v programovacím jazyce převezme patrně úplně AI, návrh koncepce či architektury složitějších programů zůstane ještě velmi dlouho činností člověka a právě při koncepčním návrhu je třeba znát nejrůznější algoritmy na vyšší úrovni abstrakce, tak jak se je snažím vykládat v přednášce BI-AVI.
S tím souvisí experimentální koncept Copilotovaného programování bez programovacích jazyků, který sice zatím není v dosavadním popisu předmětu BI-AVI, ale v cvičení se mu budeme také prakticky věnovat.
Těším se, že se alespoň s některými z Vás setkám v příštím semestru na přednáškách a cvičeních BI-AVI.
S pozdravem
prof. RNDr. Luděk Kučera, DrSc.
katedra teoretické informatiky FIT ČVUT
P.S. Nakonec několik slíbených slov o nejzajímavějších algoritmech ze syllabu BI-AVI:
Toky v sítích nejenom přednáším, ale před několika lety jsem také připravil program pro analýzu toků elektřiny pro společnost, zabývající se obchodováním s el. energií na evropské úrovni. AG2 přináší Ford-Fulkersonův algoritmus, který je základní metodou a má zajímavé matematické důsledky, ale může být pomalý. V AVI uvidíte Dinitzovu implementaci F-F a Goldbergův algoritmus (push-relabel), které zaručují rychlý výpočet. Goldbergův algoritmus je navíc mimořádně jednoduché naprogramovat.
Diskrétní Fourierova Transformace Proč se do Vašeho mobilu vejde tolik fotografií, když foťák 24 Mpixel (se 4 byty na pixel) při jednom jediném snímku vygeneruje 0,1 GB dat? Protože jsou data komprimována formátem JPEG, využívajícím kosinovou transformaci, což je modifikace Diskrétní Fourierovy Transformace (DFT). DFT se užívá i ve formátu mp3, ale její nejdůležitějsí aplikace jsou ve zpracování digitálních signálů. AVI Vám DFT přiblíží, ale hlavně ukáže, jak ji velmi rychle počítat algoritmem FFT - Fast Fourier Transform (jeden z 10 nejvýznamějších algoritmů 20. století).
Conjugate Gradient Method V kterém českém městě se za rok vyřeší nejvíc soustav lineárních rovnic? A jak se podařilo, že když Škoda Octavia I měla koeficient aerodynamického odporu 0,32, Octavia má skvělých 0,24, a přitom Škoda Auto nemá ani klasický aerodynamický tunel? V Mladé Boleslavi mají superpočítač, který za vteřinu umí provést několik miliard milionů aritmetických operací (v případě Vašeho zájmu by bylo možno zajistit exkurzi do datového centra, kde ten superpočítač je) a používají ho jako virtuální větrný tunel: problém obtékání vzduchu kolem virtuální karoserie se přes fyzikální zákony převede na soustavu lineárních rovnic a ta se vyřeší. Nejde to ale naneštěstí Gaussovou eliminací, kterou znáte z Lineární Algebry, ale jedním ze základních nástrojů je CGM - Conjugate Gradient Method, která na první pohled vypadá strašně složitá, ale vizualizace v AVI Vám ukáže, že její princip je vlastně velmi jednoduchý (a je to další z Top 10 algoritmů minulého století).
Kvantové algoritmy Myslíte si, že mají pravdu poplašné články, které popisují zhroucení bezpečné počítačové komunikace za několik let, až přijdou kvantové počítače, které budou umět snadno zlomit současné kryptografické protokoly? Máte představu, jak by to kvantové počítače mohly udělat, když ani největší současné superpočítače na to nestačí? Na závěr AVI se dozvíte o tom, co to je kvantové provázání (entanglement), jak asi by se dalo použít na lámání šifer a jestli se opravdu podaří kvantové registry provázat tak jemně, že by dokázaly rozlomit třeba 2024-bitový RSA protokol (o 8096-bitovém nemluvě).