III. semestr na FIT ČVUT

 Ohlédnutí se za zimním semestrem 2011/2012 

Automaty a gramatiky (BI-AAG)

První ze série předmětů, které rozkrývají asi nejzáhadnější software v počítači – překladač – program, který překládá jiné programy. Radostná zpráva pro každého robinsona v podobě teorie, která staví most mezi „vysokým“ programováním a „nízkým“ strojovým kódem, kterému rozumí procesor. Zpráva o tom, že konstrukce překladače je v principu možná a že je čeho se chytit.

Náplní předmětu ale není návrh překladačů, ale zorientování se v teorii formálních jazyků a gramatik dle Chomského, podrobné zvládnutí nejjednodušší třídy jazyků (regulární jazyky) a úvod do formálních překladů a třídy bezkontextových jazyků. Dozvíte se mimo jiné, jak převádět regulární výrazy na konečné automaty, čehož si dosyta užijete na papíře. V rámci domácího úkolu si vyzkoušíte práci s programem flex pro lexikální analýzu.

Jakkoli se v semestru zdá, že tu jde hlavně o mechanické ovládnutí různých postupů na papíře, ústní část zkoušky s právem veta zkoumá pochopení teorie a velká část studentů se na ni podívá vícekrát. BI-AAG přednáší docenti Holub a Janoušek, z nichž Holub má pověst krutopřísného zkoušejícího a Janoušek zase toho hodného. Pan Janoušek také učí návazné předměty a na FITu patří mezi skvělé učitele.

Databázové systémy (BI-DBS)

Je-li pro vás relační databázový stroj sprosté slovo, v tomto kurzu zjistíte, jak se s ním běžně dorozumět. Je dobře, že na to jde trochu od lesa a nesnaží se co nejdříve o probírání jazyka SQL. Díky tomu je dříve než SQL a jeho stěžejní příkaz SELECT probrána relační algebra, která SELECT poměrně hezky (avšak ne úplně) popisuje řečí matematiky spíše než zdrojového kódu. Také databáze se navrhuje nejdříve konceptuálně a až poté se překlápí do relačního modelu. Dozvíte se, co je to databáze, relační databáze, jak ji navrhnout, jak posoudit kvalitu návrhu (normalizace, funkční závislosti), co je to transakční zpracování a proč se to v praxi někdy chová jinak (aktualizační anomálie), a dozvíte se základní příkazy SQL včetně vyčerpávajícího pojednání o příkazu SELECT.

Přednášky pana Valenty jsou zajímavé, s důrazem na praxi. Díky tomu se také dozvíte, co se v tomto předmětu nedozvídáte – že existují triggery, uložené procedury, že databázový stroj vytváří prováděcí plány atd. Pokročilé věci (které si někteří studenti asi slibovali od tohoto kurzu) se dělají až ve volitelném předmětu Jazyk SQL (BI-SQL).

Praktickou část předmětu tvoří vypracování vlastní databáze od návrhu po dotazy, což je pochopitelně velmi poučné. Pokud se student nerozhodne jinak, pracuje na školní Oracle databázi, což s sebou nese výhodu v podobě pohodlných grafických nástrojů pro návrh databáze (Data Modeler) a ladění dotazů (SQL Developer). Ačkoli má předmět jednou za 14 dní cvičení, nejsou popravdě moc platná, což je asi největší slabina BI-DBS. Naštěstí přednášky a prosemináře ke zvládnutí látky stačí.

Základy diskrétní matematiky (BI-ZDM)

Probírá se matematická indukce, relace, kombinatorika a řešení rekurentních rovnic (přesné a asymptotické). Na nějaké rekurentní rovnice sice došlo už v předmětu BI-ZMA, ale to šlo spíše jen o „strašení studentů“ prvního semestru tím, že v principu lze odvodit složitost algoritmu touto cestou. Zde již nejde jen o princip, ale i o praktickou aplikaci, se kterou počítá třeba předmět BI-EFA. Kombinatorika má zase blízko k různým hádankám a hlavolamům a relace se přímo objevují v předmětech BI-DBS a BI-AAG.

Zatímco Olšákova Lineární algebra (BI-LIN) pevně stojí a trvá na důkazech, diskrétní matematika doc. Koláře na důkazech předkládaných vět nelpí, ale zase lpí na schopnosti dokázat indukcí nějaký konkrétní vztah.

Cvičení s panem Frankem byla sice poznamenána tím, že pro něj šlo o třetí hodinu v řadě, ale dobře látku vysvětlil a doplnil i o širší kontext a různé zajímavosti; šlo spíše o pochopení, než o počítání velkého množství příkladů, což hodnotím kladně. Také zveřejnil seznam kombinatorických hádanek za bonusové body.

Efektivní algoritmy (BI-EFA)

Zde se seznámíte s efektivními datovými strukturami: kruhové pole, rozptylovací tabulky, vyhledávací stromy (B-tree, AVL, červeno-černé, trie), haldy (binomiální a „magické“ Fibonacciho haldy). Rozbory složitostí, rozpitvání řadících algoritmů vč. důkazu, proč je n log n dolní mez složitosti algoritmů řazení, které porovnávají a prohazují prvky. Na konci se dostane i na nějaké další věci jako je dynamické programování a QuadTree.

Pracuje se na papír a na tabuli, ale také jsou dvě programovací úlohy, letos na téma rozptylovací tabulky a B-stromy, které jsou nepovinné, lze za ně však dostat poměrně hodně bodů (při brzkém odevzdání bonus 50 %). Zkouška je příjemná v tom, že po získání minimální hranice z první části už lze skóre pouze vylepšit (srovnej právo veta v BI-AAG a „sázku“ −5 bodů pro absolvování další části zkoušky v BI-ZDM).

Přednášky pana děkana nepatří mezi zvláště zábavné, ale prezentace jsou až vyčerpávajícím zdrojem informací včetně animací a důkazů a pseudokódů. Během semestru došlo k poměrně kuriózní situaci při probírání Fibonacciho hald, jelikož jde zřejmě o poněkud exotickou datovou strukturu, ke které je nedostatek literatury, a tak nebylo zcela jasné, jak přesně má fungovat „magický“ příznak jejích uzlů, který ji udržuje pohromadě. Každopádně pseudokódy byly opraveny a teď už je snad vše, jak má být.

Objektové modelování (BI-OMO)

>>> class Pes:
...     def pozdrav(self):
...         print("Haf haf!")
>>> class Kočka:
...     def pozdrav(self):
...         print("Mňáááu!")
>>> alík = Pes()
>>> micka = Kočka()
>>> domácí_zvířata = [alík, micka]
>>> for zvíře in domácí_zvířata:
...     zvíře.pozdrav()
Haf haf!
Mňáááu!

Objektově orientovaným programátorům dnes patří svět. Předmět dr. Pergla však není kuchařka „1001 návrhový vzor“, ale naopak jde (anebo alespoň míří) do překvapivé hloubky objektově orientovaného paradigmatu.

Příklad výše demonstruje polymorfismus nezávislý na dědění. Programovací část předmětu se ale neodehrává v Pythonu, ale ve Smalltalku, pozoruhodném vývojovém prostředí a jazyku, který v sobě kombinuje λ-kalkulus, přirozený jazyk a přístup „vše je objekt“:

alík := Pes new.
micka := Kočka new.
domácí_zvířata := OrderedCollection with: alík with: micka.
domácí_zvířata do: [ :zvíře | zvíře pozdrav ].

Předmět se zabývá návrhem informačních systémů z pohledu OOP: rozbor slovního zadání, vytvoření konceptuálního modelu (entity a vztahy zanesené do UML diagramu tříd), až po prototyp ve Smalltalku. Na rozdíl od BI-ZSI je návrh systému pojat spíše způsobem „jak se v tom zorientovat, kdybych to měl dělat sám“, UML se neprobírá do šířky.

Přidanou hodnotu předmětu tvoří (kromě Smalltalku) poměrně dlouhá série přednášek na téma ontologického přístupu k tvorbě konceptuálního modelu. Dr. Pergl zde čerpá z práce dr. Giancarla Guizzardiho, který vytvořil nadstavbu UML (OntoUML) obohacenou právě o ontologii (a také teorii okolo, založenou na modální logice).

OntoUML například zdůvodňuje, proč by Student a Učitel neměl být podtyp Člověka: Člověk je objekt, který má identitu sám o sobě, zatímco Student a Učitel jsou role, kterým identitu propůjčuje nějaký Člověk (ani nejsou navzájem exkluzivní). Pokud bychom přesto chtěli použít dědičnost, bude to mít negativní následky: student, který je zároveň učitel, musí být v systému dvakrát, atd. OntoUML mělo letos svůj první běh, takže to místy trochu skřípalo, ale časem se to jistě vyladí.

Základy softwarového inženýrství (BI-ZSI)

Předmět pro studenty mimo obor Softwarové inženýrství, který je má utvrdit v tom, že si zvolili správně :-)

BI-ZSI se podobně jako BI-OMO zabývá tvorbou informačních systémů, ale z jiné strany. Během celého semestru se po skupinách 4–6 lidí vytváří IS: analýza, návrh a část implementace. Stěžejní je projektová dokumentace a funkční ukázka aplikace.

V praxi jde o demýtizaci klasické úlohy „Jeden kopáč kope výkop x hodin, jak dlouho budou kopat tři kopáči?“, kombinované s kreslením roztodivných UML diagramů v mamutím programu Enterprise Architect – fakt, že v BI-OMO se diagramy kreslí v UMLetu, docela vystihuje rozdíl mezi těmito předměty.

Jde o předmět otravný, nicméně vás poměrně podrobně obeznámí s notací UML a nastíní, jak se může dělat „software ve velkém“. A když zahodíte 80 % „byrokracie“, může to snad být k užitku i pro „software v malém“.

 

Odpoledne pana Rybičky

Slaneček mi už pár dní slibuje, že napíše povídku a pošle mi ji. Ve středu jsem dostal nápad na povídku vlastní: o Slanečkovi, jeho práci a múze. Dnes (v pátek) jsem ji vyhotovil a tímto ji posílám do světa. Chcete-li si ji přečíst, o něco lépe vysázená verze než ta níže je zde: Odpoledne pana Rybičky (PDF).

ODPOLEDNE PANA RYBIČKY

Bylo pošmourné lednové odpoledne léta páně 20×× a v šestém patře reálně socialistického věžáku měl zrovna směnu pan Rybička. Obcházel okolo dlouhé kádě uprostřed místnosti, po očku sledoval hodiny na zdi a větrák digestoře ho odnášel pryč, do loňského roku, do jakéhosi lokálu na okraji města…

* * *

Topení bylo zapnuté o trochu víc, než být mělo, a listy větráku ukrajovaly dým u stropu. V místnosti byl bujarý hovor, ale panu Rybičkovi se spíše zdálo, jako by někdo šel dlouhým tunelem a nemaje nic lepšího na práci, kopal před sebou plechovku.

Neměl nic zvláštního proti plechovkám, kouři nebo společnosti, byl však sám a nejraději by odsud bláznivě uprchl do noci, jako by se stalo něco strašného, sám by utíkal prázdnými ulicemi, sám, anebo -

"Tak na zdraví, pane kolego!"

Muž po jeho levici mu podává panáka slivovice.

"Ať slouží!" odpoví pan Rybička.

Na chvíli se obrátí ke společnosti a předstírá zaujetí hovorem, zatímco uvažuje o důvodech, které by jej z této trýznivé noci omluvily.

Ze dveří na druhé straně místnosti vykoukne zvědavá hlava dívky.

"Haló, kluci, nedáme šipky?"

Jakási obrovská síla rozpáře útroby Země, smete toho uličníka s plechovkou a pan Rybička je zachráněn, zvedá se ze sutin a spolu s kolegou po své levici míří ke dveřím, kde čeká ona.

"Kdo vyhraje, může mi koupit panáka," říká pravidla hry.

Parta z šestého patra se staví do řady za tlustou čáru na podlaze.

První na řadě je pan Rybička.

Trefa do černého.

Druhý na řadě je pan Krysa.

Šipka se odrazí od terče a spadne.

"Oú!" kvituje slečna.

Hra pokračuje dál, ale na Rybičku si jen tak někdo nepřijde. Tihle Pražáci nic nevydrží. Pan Krysa si drží druhé místo, a potom…

"Jednu slivku pro krále střelců!"

Pan Rybička se před posledním hodem posilní, soustředí se na techniku - a hodí jen tři body.

Pan Krysa hodí střed, vycení zuby a volá: "Jeden drink pro slečnu Kočičku!"

Slečna se otočí na pana Rybičku a prohodí k němu: "To byl pech. Tak příště," a usměje se.

Pan Krysa vychutnává své vítězství.

* * *

Dvacet minut uplynulo, pan Rybička otočí velkým kohoutkem u stěny nádrže a hladina začne zvolna klesat. Za tři minuty je objemná vana docela prázdná a za další chvíli utichne i digestoř.

Pan Rybička zamíří ke dveřím, jde na druhý konec úzké chodby, do posledních dveří vlevo.

"Ty jsi ten nový, že?" řekl pan Krysa. "Jestli chceš vědět, co je takhle velká káď, tak je to stroj času. Tady na šestém poschodí vypouštíme archiv. Vezmeš šanony z archivu, položíš je na dno - a za dvě hodiny se nic z toho nestalo."

Je to snadné, hrozně snadné…, pomyslel si pan Rybička, když nesl archiválie do místosti se strojem času.

Odpolední směna pomalu plynula a pan Rybička se už těšil domů. Zatímco kyselina obědvala, vytáhl v jedné ze skříní pinzetou proužek stříbrného kovu a ustřihl z něj malý čtvereček. Oficiálně se to samozřejmě nesmělo, ale Rybička musel uznat, že tenhle vynález se Kryse povedl.

Vzal pinzetou čtvereček kovu a hodil jej do kádě.

Jen co se dotkl hladiny, začal kov rejdit sem a tam, vydávajíc oslňující záři…

* * *

Na Silvestra byl také firemní večírek. Jak pan Rybička poznamenal, když poprvé uviděl své pracoviště - tahle firma byla skrz naskrz divná. Kdo dostal pozvánku, na večírek dorazil: snad z úzkosti (nikdo pořádně nevěděl, jaká všechna oddělení existují a co se tam děje); snad proto, že se nikomu nepodařilo slečnu Kočičku zlákat na sou­kromou akci a ona tam měla být.

Oslava se nekonala v jakémsi lokále na kraji města, ale přímo na zrekonstruované střeše reálně socialistického věžáku.

Toho večera páni Rybička a Krysa zaníceně debatovali o filmech Stanleyho Kubricka. Vyrušila je půlnoc, připili si se slečnou Kočičkou a pan Krysa odešel s bratrem o patro níž ladit kytary.

Pan Rybička pozoroval se slečnou Kočičkou ohňostroj a bylo to moc krásné, ale potom pyrotechnika poněkud utichla a vrátili se Krysa s Potkanem. Začali hrát a paní Kočička poslouchala a už to krásné nebylo.

"Co na těch myších vidí…" pomyslel si pan Rybička.

V přestávce mezi písničkami zaslechl tichý hovor za sebou.

"A víš jak slečna Pěnkava přešla na třetí patro? Už má výpověď, bude z ní paní Pěnkava a stěhuje se do Bratislavy."

"Slyšel jsem, že i slečna Kočička se teď někdy stěhuje, že už tam prý stejně napůl bydlí…"

Pan Rybička do sebe rázem otočil svou sklenku, ať už v ní bylo cokoli, a stálo ho nejvyšší úsilí usmát se na paní Kočičku, když se na něj otočila.

* * *

Pan Rybička hleděl na kalnou káď. Pan Krysa byl lepší rozpouštěč než on. Pan Krysa zpíval lépe než on. Aby se však ze slečny Kočičky stala paní Myš, to se mu zdálo tak ohavné, že bylo lze lépe obhájit vraždu, nežli jednu noc slečny Kočičky s tou… s tou…

Ale pan Krysa to snad věděl dříve, než ho vůbec znal, a proto mu tehdy první den v práci řekl: "Pane kolego, povídá se, že v téhle místnosti už cestoval časem i člověk. Ale cestování časem je tuze nebezpečný podnik - pro všechny zúčastněné. Rozumíme si?"

"Ano. Je to snadné. Příliš snadné," pomyslel si pan Rybička.

Ozvalo se zaklepání a ze dveří vykoukla zvědavá hlava dívky.

"Pane Rybičko, vezmete mě do chlaďáku?"

Pan Rybička zvedl hlavu, potěšený návštěvou své múzy.

"Samozřejmě, jen okamžik," řekl, vzal si klíče a vyrazil s paní Kočičkou k výtahu.

Výtahy v budově byly poněkud úzké, ne však tak úzké, aby se slečna Kočička musela cítit nepatřičně. Kabina se rozjela směrem dolů.

"Pan Potkan tu ještě není?"

"Má přijít na pátou, asi za chvíli dorazí."

"Můžete mu vyřídit, aby mi zavolal?"

"Ale jistě."

"Potřebuju, aby mi někdo pomohl s věcmi. Příští týden se budu stěhovat k panu…, ale to vy asi víte, tak co vám to povídám."

"Ano, řekl mi to, než… Stále se neozval?"

"Ne." Měla tvář jako měsíček.

"Určitě je v pořádku."

"Jo, vím že máte pravdu… Snad…"

Dveře výtahu se s cinknutím otevřely ve druhém suterénu.

"Promiňte, že vás s tím takhle obtěžuju, ale kluci z organiky si vzali volno a mně se sem samotné -"

"Je mi ctí vás doprovázet, slečno z organiky," řekl pan Rybička poněkud teatrálně a vykouzlil úsměv na tváři slečny Kočičky. Otevřel kartou masivní dveře a oba vešli do chlazené části podlaží.

Od úst jim šla pára, jak šli kolem regálů s krabicemi a zkumavkami. Po chvíli slečna Kočička odbočila vpravo a jednu po druhé pročítala značky na regálu.

"To je ale kosa, co?" řekla.

"Zahřeji vás," pan Rybička neřekl. Místo toho odpověděl: "Pěkná zima. Pro co vlastně jdeme?"

"Nějaké organické vzorky z ledovce. Je to úžasné, něco jako zkameněliny. Třeba se tam někde zachytí pyl - zůstane genetický materiál - a po tisícovkách let je to ještě 'živé' a dá se to přečíst."

"Zajímavé. Takže můžeme naklonovat rostliny z časů před poslední dobou ledovou?"

"Pracujeme na tom," usmála se slečna Kočička. "Ledovec je vlastně takový stroj času."

Slečna Kočička byla pohledná, ale ještě více poutala Rybičkovu pozornost jakýmsi tajemstvím, které ji provázelo. Nejen, že v práci přiváděla k životu interglaciální rostliny staré sto tisíc let; ona ví, že ledovec je stroj času!

"Ledovec je totiž také stroj času, pane kolego," pomyslel si Rybička, až mu přeběhl mráz po zádech.

Vtom se na konci chodby otevřely dveře chlaďáku. Pan Rybička stál na rohu uličky, ohlédl se a spatřil pana Potkana, jak na něj hledí těma svýma krysíma očičkama a jak ty dveře zase zavírá.

Než stačil cokoli udělat, zhasla světla.

Pan Rybička věděl, že je v loji.