O číslach: Informatické minimum
Možno sa niektoré čitateľky alebo čitatelia dali mojím júlovým stĺpčekom nahovoriť na dovolenku strávenú s matematikou a na pláži bolo vidno napríklad dámy s logaritmickým pravítkom v ruke. Mimochodom, s ním by vzbudili viac pozornosti ako bez hornej časti dvojdielnych plaviek.
Pred štyridsiatimi rokmi to bolo naopak. Nielen preto, že dnes maturant netuší, čo s ním, ale vtedy to bola bežná pomôcka inžinierok a inžinierov počítajúcich napríklad statiku práve dokončovaného krásneho mosta Coronado v San Diegu či dráhu letu na Mesiac.
Kto sa však matematike či informatike cez leto určite venovať mal, sú študenti, čo nepochodili na štátniciach v riadnom termíne. Aj na „matfyze“, kde učím, sa našli takí. Neuspeli, lebo nevedeli to, čo si my učitelia myslíme, že by mal vedieť každý, kto chce mať diplom našej fakulty.
Ešte by som si mohol ako-tak predstaviť, že by náš absolvent informatiky nemal úplne jasno v triedach zložitosti algoritmov – vyjadrujú, aké je náročné (časovo alebo pamäťovo) nejaký problém vypočítať. Už ťažšia by bola predstava, že študent nepozná najslávnejší otvorený problém súčasnej informatiky, či P = NP – či je rovnako ťažké úlohu vypočítať ako len tipnúť výsledok a ten overiť (ak sa obmedzíme na prakticky riešiteľné, takzvané polynomiálne algoritmy).
No a úplne neprípustná by bola predstava, že by štátnicami prešiel niekto, kto nevie, že existujú a čo sú nerozhodnuteľné problémy. I keď uznávam, nie je ľahko stráviteľné pripustiť ich existenciu.
Medzi najznámejšie patrí Postov korešpondenčný problém (Emil Leon Post, 1897 –1954, poľsko-židovsko-americký matematik): máme niekoľko druhov kariet (a z každého druhu neobmedzene veľa kusov). Na každej karte sú v hornej a dolnej polovici napísané nejaké písmená. Úloha je zistiť, či sa karty dajú vedľa seba poukladať tak, že postupnosť písmen z horných polovíc sa rovná tej z dolných.
Vyzerá to jednoducho, ale neexistuje algoritmus, čo nám povie, či úloha pre zadanú sériu kariet má, alebo nemá riešenie. Študenti, ktorí o tom počas štúdia vraj nepočuli, mali o zábavu na leto postarané.
Ale pozor! Nepopliesť si to! Ak ste videli pri vode mladých ľudí s čertovými obrázkami, ešte nemuseli dumať nad Postovým problémom. Možno len tak mastili karty. Buď mali po skúškach, alebo sa spoliehajú, že im budúcnosť budú zabezpečovať politici – napríklad tak, že zo päťtisíc z nich dostanú na školy a tie navyše časom nazvú univerzitami. Už len aby im minister vlastnoručne pripísal na diplom, že skončili tú najlepšiu na svete. A druhú v okrese.