Doktorské studium

Prvním rokem studuji v doktorském studiu, systém tohoto studijního programu mě značně překvapil. Do tohoto studia jsem se pustil kvůli tomu, že mě studium informatiky baví a chci se dostat alespoň v úzkém výseku vědění na hranu poznání a popř. i něčím zajímavým přispět. Částečně jde i o to, že bych si chtěl zajistit dobrou pozici pro získání zajímavé tvůrčí práce v oboru nejlépe v nějaké větší firmě, která si může dovolit investovat do vývoje.

Student v doktorském studiu má 3 základní zaměstnavatele školu, školitele a komerční sektor. Díky této svaté trojici má na studium daleko méně času než v programu magisterském. A tak tedy není výjimkou, že studenti v doktorském studiu nesetrvávají jmenovité 3 roky, ale i roků 7 a více. Ostatně i jeden profesor se k délce studia vyjádřil, že za 3 roky, disertační práce není ono a že je potřeba aby uzrála a tedy počítat spíše s délkou studia 4-5 let.

Škola se v podstatě o studenta stará jen přerozdělením doktorandského stipendia vypláceného státem. Mimo to škola pořádá výuku jazyků a popř. dalších předmětů a stará se o organizaci studia. Student škole tuto činnost splácí výukou a publikační činností (která bývá podmínkou realizace studijních programů na škole). Většina škol ukládá doktorandům povinnost učit. Lze to sice zdůvodňovat snahou naučit se studenty veřejně vyjadřovat, formulovat myšlenky a vést ostatní v poznání. Možná by i to tak fungovalo, pokud by studenti byli v učení nějak motivování. Praxe je však taková, že kvalita výuky nemá v podstatě žádný vliv na finanční hodnocení doktoranda. Doktorand přípravou cvičení stráví daleko více času než cvičením samotným a celý systém výuky spočívá na svědomitosti doktoranda a jeho zapálení pro předmět. Zajímavé je, že doktorandi opravdu svědomití většinou jsou.

Školitel je člověk, na kterém je (samozřejmě po doktorandovi) nejvíce práce, a v podstatě úspěch doktoranda velmi závisí na výběru tohoto člověka.

Za prvé umožňuje doktorandovi uskutečnit zkoušky u svých kolegů a tím mu umožnit získat vědomosti, které mu škola není schopna poskytnout. Vzájemné zkoušení doktorandů je v akademické sféře reciproční. Protože tato výuka není nijak financovaná, tak se uskutečňuje odkazem na skripta, poskytnutím konzultace a několika hodinami věnovanými na přezkoušení.
Dále školitel vede doktoranda do světa znalostí svého oboru, pomáhá mu zaměřovat se na důležité zdroje a pomáhá mu s publikacemi.
Jedním z nejdůležitějších úkolů školitele je bohužel také zajištění financování, protože účast na konferencích něco stojí (a konference jsou místa, kde lze získat kontakty a navázat spolupráci). Zároveň se školitel stará i o zajištění práce a dodatečný příjem doktoranda, aby nemusel se svým stipendiem žebrat.

Za tuto důležitou činnost je školitel odměněn učedníkem, který je schopen vykonávat libovolné práce nebo popř. spoluautorstvím doktorandem publikovaných příspěvků a článků. Mnozí školitelé se těchto možností zhostí se značnou vervou a jsou schopni si zařídit kompletní učednickou dílnu. Pokud se školitel chová eticky a s rozumem, tak se zpravidla jedná o vzácného člověka, který vede doktorandy z vlastního zápalu (přičemž se mi čim dál víc jeví, že bez velkého zápalu se v akademické sféře nebo vědě zůstat ani nedá).
Školitel se většinou rekrutuje z vědeckého zaměstnance vysoké školy, který tuto činnost vykonává v rámci pracovního poměru, nebo ze zaměstnance instituce zaměřené na vývoj (např. akademie věd). V posledním případě se vedou spory o to, kdo je za vzdělávání doktorandů více zodpovědný zda vysoká škola nebo akademie věd. Tento spor je v podstatě sporem o státní peníze na financování vědy a výuky.

Komerční sektor přichází na řadu tehdy, pokud školitel není schopen zajistit dost financí k přežití doktoranda (tedy placené místo doktorandovi v akademické instituci). Přežít ze stipendia 5000 měsíčně za první rok, 6000 za druhý rok a 7000 za 3. rok studia opravdu bez dalšího financování nebo sponzora (např. podpory rodiny) nelze. Proto si doktorand musí zpravidla najít placené místo alespoň na částečný úvazek a skloubit povinnosti z toho vyplývající s těmi předcházejícími. Škola si kupodivu necení schopnosti doktoranda vydělat si na živobytí sám, ale částečně zabezpečeného doktoranda považuje za zbytečného příživníka na stipendiu, které na něm co nejdříve ušetří. Tím doktoranda vrhne ještě více vstříc komerčnímu sektoru. Pro nedostatek ocenění a perspektivy v tomto systému svaté trojice většinou doktorand odchází do tohoto sektoru ještě před získáním titulu.

Formát a uskutečňování doktorského studia přímo souvisí s kvalitou financování vědy a školství. Je zřejmé, že tato rozpočtová kapitola nikdy nehrála prim a pravděpodobně ani dlouho hrát nebude. Vzdělávání zůstává jen kapitolou, kde mezi sebou bojují různé ideologie, ale zásadní systémové problémy zůstávají neřešené. Což se zákonitě projeví v budoucnu.

Kolize a správná krajtí cesta

V rámci semináře v C++, jsem chtěl probrat algoritmus na zjišťování kolizí N stejně orientovaných kvádrů v lepším než v kvadratickém čase. Algoritmus v základu pracuje s tím, že promítne kvádry do jedné osy, zjistí jaké kvádry se promítají v jedné ose na sebe a dále řeší obdobným způsobem už jen kolizi mezi nimi. Tedy vezme ty co se promítnou na sebe a promítne je zas do jiné osy, zas rozdělí.. a ty které kolidují ve všech průmětech se protínají. Nejhorší čas O(N²), nejlepší O(N) a průměrný O(N.log(N)).

Zadání
Základem algoritmu je tedy umět vzít N intervalů a zjistit, které se překrývají. Vyzkoušel jsem různé postupy a podělím se s vámi o výsledky v pořadí od komplikovaných postupů po nejjednodušší.

Vzorky
Prvně si vygeneruji 100 náhodně rozmístěných intervalů mezi 0 a 1000, délky 10

import random

nsamples = 100
#list of (start position, length, name)
samples = [(random.randint(0,990), 10, i) for i in xrange(nsamples)]

Algoritmy založené na vkládání
Hlavní myšlenkou je rozdělit si intervaly pomocí binárního stromu a testovat kam vložit nový interval. V podstatě se jedná o 3 implementace binárního stromu. Ovšem pro usnadnění testování jsem si vytvořil pomocnou třídu interval.

class Interval:
  def __init__(self, lower, upper):
      self.upper = upper
      self.lower = lower
    
  def union(self, interval):
      '''
      self := self union interval
      '''
      self.lower = min(self.lower, interval.lower)
      self.upper = max(self.upper, interval.upper)
    
  def __cmp__(self, interval):
      if self.upper <= interval.lower:
          return -1
      elif self.lower >= interval.upper:
          return 1
      else:
          return 0

Všechny implementace binárního stromu se budou používat stejně.

tree = BTreeCluster()
for s, e, i in samples:
  tree.append(s, e, i)
tree.write()

1. Implementace
První implementace je jen jednoduše napsaný binární strom, který si vytvoří pod-uzly až teprve po přidání prvního prvku. Tento přístup bude paměťově nejnáročnější. Zato implementace v C++ by byla poměrně přímočará.

class BTreeCluster1:
   '''
   classical Binary tree with interval and intersecting objects in each node
   '''
   def __init__(self):
       #lazy inicialization
       self.left = None
       self.right = None
       self.inter = 0
       self.group = []
      
   def append(self, pos, lenght, name):
       if not self.group:
           self.group = [name]
           self.inter = Interval(pos, pos+lenght)
           self.left = BTreeCluster1()
           self.right = BTreeCluster1()
       else:
           inter = Interval(pos, pos+lenght)
           if self.inter == inter:
               self.group.append(name)
               self.inter.union(inter)
           elif self.inter > inter:
               self.right.append(pos, lenght, name)
           else:
               self.left.append(pos, lenght, name)
      
   def write(self):
       if self.left:
           self.left.write()
       if len(self.group) > 2:
           print 'collision', self.group
       if self.right:
           self.right.write()

2. Implementace
Druhá implementace se snaží více šetřit pamětí a přiřazuje uzlům indexy. Uzel s indexem n má pod-uzly 2n a 2n+1. Protože intervaly mohou do funkce přijít třeba seřazené a vzniklý strom může být značně nevyvážený používám na uložení uzlů hash tabulku (slovník) s indexy na místě klíčů. Protože ve standardní knihovně C++ není implementace hash tabulky, bylo by přepsání složitější. Stejně jako v prvním případě by bylo vhodné občas strom vyvážit, ale pro jednoduchost a lenost to vynechám.

class BTreeCluster2:
   '''
   Binary tree with interval and intersecting objects in each node
   encoded in dictionary (hash table)
   node number i has subnodes 2i, 2i+1
   hash table saves memory even for unballanced tree
   '''
   def __init__(self):
       self.groups = {} #number:interval, group
      
   def append(self, pos, lenght, name):
       inter = Interval(pos, pos+lenght)
       index = 1
       while True:
           if index not in self.groups:
               self.groups[index] = Interval(pos, pos+lenght), [name]               
               return
           iinter, igroup = self.groups[index]
           if inter == iinter:
               igroup.append(name)
               iinter.union(inter)
               return
           elif inter > iinter:
               index = 2*index + 1
           else:
               index = 2*index
      
   def write(self):
       for i,g in self.groups.values():
           if len(g) > 2:
               print 'collision', g

3. Implementace
Narozdíl od prvních dvou jsem se rozhodl strom přerovnávat v průběhu přidávání (halda by byla účinnější). Uzly jsou uloženy v poli srovnaném podle pozice intervalu a pole je prohledáváno pomocí půlení intervalu.

class BTreeCluster3:
   '''
   Binary tree with interval and intersecting objects in each node
   encoded in sorted array of disjunctive intervals
   sorted is archieved by inserting new nodes to right position   
   '''
   def __init__(self):
       self.groups = [] #number:interval, group
      
   def append(self, pos, lenght, name):
       '''
       finding the right position is archieved by iterative interval dividing
       '''
       inter = Interval(pos, pos+lenght)
       if not self.groups:
           self.groups = [(inter, [name])]
           return       
       upper = len(self.groups)-1
       lower = 0
       while True:
           ##print lower, upper
           index = (upper + lower) / 2
           iinter, igroup = self.groups[index]           
           if inter == iinter:
               #exteding existing one
               igroup.append(name)
               iinter.union(inter)
               return
           elif inter > iinter:
               if lower == upper or index == upper:
                   self.groups.insert(index+1, (inter, [name]))
                   print 'including after'
                   return
               lower = index + 1
           else:
               if lower == upper or index == lower:
                   self.groups.insert(index, (inter, [name]))
                   print 'including before'
                   return   
               upper = index - 1
                      
   def write(self):
       for i,g in self.groups:
           if len(g) > 2:
               print 'collision', g

Všechny tyto implementace jsou poměrně rozsáhlé, ale umožňují přidání nového prvku kdykoliv v průběhu programu. Následující postup je jednodušší, ale danou věc neumožňuje. Místo prvních 3 pokusů by možná stálo za to implementovat haldu.

Postupy založené na syntaktickém analyzátoru
Pokud intervaly seřadíme podle počátku lze je sekvenčně procházet, jednoduše testovat kolize a vracet intervaly, které se protínají. Je potřeba si však poradit s tím, kdy začít novou skupinu a také s přečtením posledního prvku.

1. Implementace
Je napsána jednoduše a jistě by šla snadno převést do C++, speciálně při využití knihovny <sort>.

EOF = 'EOF'

def readgroup(token, it):
   '''
   c-like parsing function
   returns last read token and group of intersecting intervals
   '''
   s, e, i = token
   end = s + e
   group = [i]
   for token in it:
       s, e, i = token
       if end <= s:
           return token, group
       else:
           group.append(i)
           end = s + e
   return EOF, group
  
samples.sort()
it = iter(samples)
token = it.next()
while token != EOF:
   token, g = readgroup(token, it)
   if len(g) > 1:
        print 'collision', g

Implementace nepočítá s prázdným vstupním seznamem. Po načtení posledního prvku signalizuje konec speciálním tokenem EOF. Protože se v průběhu funkce readgroup vrací vygenerované skupiny je potřeba vracet i naposledy přečtený token a navázat ve zpracování funkce ve stejném místě. Pokud by funkce vracela seznam seznamů, tak by její implementace byla jednodušší ale paměťově náročnější. Realizace výpisu přímo při nalezení kolize by funkci zjednodušila. Cílem však není výpis ale umožnit s nalezenými skupinami dále pracovat.

2. Implementace
Je první algoritmus přepsaný do Pythonu a využívající techniky generátorů.

def readgroup(samples):
   group = []
   for s, e, i in samples:
       if group and end <= s:
           yield group
           group = []
       group.append(i)
       end = s + e
   yield group
      
samples.sort()
for g in readgroup(samples):
   if len(g) > 1:
        print 'collision', g

Závěr
Možná se zdá, že jsem mohl napsat jen poslední příspěvek. Chtěl jsem však ukázat, jak v závislosti na požadavcích, použitých konstruktech jazyka a přijaté abstrakci lze vytvořit různé implementace, které se liší v rychlosti, použité paměti a délce zdrojového kódu. Předpokládám, že nejsnadněji by v C++ šla vytvořit předposlední implementace. A jaký je Váš názor?

Helmut Herold: Awk&Sed

Podtitul: Příručka pro dávkové zpracování textu

Tato kniha z nakladatelství Addison-Wesley (překlad Computer Press) popisuje dva úlohově orientované jazyky z prostředí UNIX. Na cca 170 stranách je rozepsán programovací jazyk awk a na 64 stranách proudový editor sed. Kniha je brožovaná a obsahuje tak na půl vysvětlující text a na půl příklady. Po učebnicovém vysvětlení základní syntaxe se autor dostává i ke komplikovanějším příkladům. Např. realizaci relačního operátoru JOIN, řešení problému umístění 8mi dam na šachovnici nebo výpisu síťových plánů. V některých příkladech se pak začínají projevovat omezení programovacího jazyka. V knize jsem nenašel využití na zpracování češtiny a jak se sed a awk vyrovná s českým textem. (dle mých pokusů ne moc dobře)

Kniha je přeložena z německé verze, neboť na pár místech překladatel zapomněl názvy přeložit (ausdruck, freiplat). Co je více zarážející je množství překlepů, možná by se měl někdo v nakladatelství naučit používat kontrolu pravopisu (přeci jen to není až tak moderní funkce). V knize jsem nenarazil na logické nesmysly a text knihy je dobře čitelný. Překládat zdrojový kód do češtiny mě zavání nevkusem (v němčině by to však nebylo lepší - řídící konstrukce jsou v angličtině, klíčová slova v angličtině, proč by tedy funkce, komentáře a názvy proměnných měli být v češtině?). V některých příkladech je rozhozené odsazení a zvýraznění klíčových slov ve zdrojovém kódu bych už dnes považoval za standard (avšak tady chybí).

Přesto knihu mohu doporučit, protože poskytuje zajímavý náhled do dvou základních UNIXových nástrojů. A pro ty co nepracují s UNIXem poskytuje ukázku dvou řešení specifických problémů práce s textem. Hlavně bych chtěl vyzdvihnout pěkně zvolené příklady, které jsou občas propojeny zdrojovým kódem BASHe. Domnívám se, že právě pěkně zvolené příklady z praxe jsou na této knize nejpěknější.

Hodnocení 7/10

Umění programování v Unixu - Kapitola 1

Technická polemika - Po zhodnocení formální stránky knihy, bych se rád dostal k zajímavým myšlenkám v knize obsaženým.

Úvodní kapitola se zabývá historií UNIXu jeho postavením mezi ostatními operačními systémy. Snaží se ukázat, že UNIX jako technologie i filozofie musela přijmout spoustu změn a překonat změny trendů. Přechod z prostředí mainframe na osobní počítače, dále do distribuovaného prostředí internetu a nakonec i překonat změnu související se zavedením GUI. Kniha se snaží popsat základní trendy, které si UNIX zachovává a v podstatě dochází k tomu, že je to svoboda práce se zdrojovým kódem systému i programů a dobrý inženýrský návrh, postavený na spoustě malých spolupracujících programů. IMHO: Pravidla uvedená v této kapitole se hodí k návrhu libovolného software a lze je označit za pravidla dobrého návrhu aplikace. Pravidla jsem trošku přeformuloval a mnohdy doplnil svým pohledem, takže se nejedná o překlad knihy, jde spíš rozvití myšlenek v knize obsažených.

Ke konci kapitoly je je uveden krátký popis jiných systémů a v čem se liší. Přijde mi, že tento popis je trošku zaujatý a nejde moc do hloubky, ale nejsem odborníkem na operační systémy.

Pravidla psaní software

Držte se jednoduchých, propojitelných rozhraní – Zde jsou myšlena hlavně rozhraní textová, popř. založená na XML. Rozhraní je to co určuje zda program bude použitelný ve větším kontextu nebo zůstane zastrčený v šuplíku. Složité rozhraní znesnadňuje použití programu v kontextu ostatních programů.

Srozumitelnost je důležitější než efektivita – Prostě jen přeformulované tvrzení D.Knutha: “Předčasná optimalizace je kořenem všeho zla.”. Složitý algoritmus obsahuje více místa pro chyby a hůře se opravuje i rozšiřuje. Zdrojový kód by měl být opatřen komentáři. V knize lze dokonce potkat i myšlenku literárního programování a to v té podobě, že každý algoritmus by měl být snadno vysvětlitelný pomocí přirozeného jazyka a podobným způsobem i zapsán ve zdrojovém kódu.

Navrhuje programy propojitelné s jinými programy – V duchu zásady program má dělat jednu věc dobře a nesnažit se řešit vše. Dokládané je to na možnosti zvolit si editor, který jiné programy budou používat pro vstup a editaci textu. Jiným příkladem je realizace stránkování výpisu na obrazovku, přes příkazy more, less.

Navrhujte jednoduché programy, složité piště jen v případě nutnosti – Zde se lze odkázat na knihu Steve McConell: Odhadování softwarových projektů, kde se dozvíte, že s velikostí programu roste pravděpodobnost překročení rozpočtu i toho, že se program nepodaří dokončit. Přičemž náročnost vývoje s velikostí programu roste kvadraticky! (protože tímto způsobem roste počet možných vazeb v programu)

Navrhujte transparentní programy – Tedy programy, ze kterých lze na základě vstupu snadno zkontrolovat výstup a ověřit, že program plní to co má.

Pravidlo robustnosti – Program se musí vypořádat i s krajními případy a vyprodukovat smysluplný výstup. Při propojení s jinými programy se na vstupu může objevit skoro cokoliv. V podstatě se jedná o defenzivní programování.

Volte deklarativní zápisy ne procedurální – Zápis gramatiky v BNF je daleko snazší než její zápis v syntaktickém analyzátoru. Stejně tak je tabulka jednodušší reprezentací, než složitý příkaz switch nebo mnoho konstrukcí if, else.

Pravidlo nejmenšího překvapení – Rozhraní by uživatele nemělo překvapovat. Snaha dodržovat běžnou kulturu zápisů – způsob značení komentářů, zápisu programu, … Rozhodně se však vyvarujte označování rozdílných věcí stejným způsobem. Příkaz return, který by místo ukončení funkce ukončil program, je takovým příkladem.

Mluvte jen když je třeba – Program má mluvit, jen když je potřeba sdělit něco důležitého. Ukecané programy nikdo neposlouchá. Pokud je však třeba upozornit na chybu, tak nejlépe hlasitě a co nejdříve! Informace o chybě by měla být dostatečně konkrétní. Je velký rozdíl mezi hláškou “Hups chyba!” a “Chyba soubor config.ini: Na řádku 35, je uveden neexistující uživatel pepa3”.

Programátorův čas je dražší než čas CPU – Za 2 roky poběží vaše programy 2x rychleji. A to bez námahy. V podstatě zas odkaz na předčasnou optimalizaci. Optimalizace se totiž řeší až naposled, kdy je jasné jaké části (cca 20% programu) zpomalení způsobují. 80% programu nemá smysl optimalizovat, dokonce to škodí přehlednosti, rozšiřitelnosti a poštu chyb v programu. Pokud program běží dost rychle i tak, lze si ušetřit i optimalizaci těch 20% ;).

Pravidlo generování – Počet chyb na řádku je v podstatě nezávislý na jazyce, snažte se tedy psát úsporně a manuální úkony (jako generování kódu) nechat na počítači. Věřte, že je spolehlivější. Pozn. Výstup generátorů pokud možno neupravujeme! (to bychom se o výhodu malého počtu řádek připravili)

Optimalizace až na konec – už bylo řečeno, ale je potřeba opakovat do zblbnutí ;)

Není jen jeden správný způsob – Snažte se vymyslet různá řešení a vyberte nejlepší ne to první. Nespadněte do pasti prvního návrhu. Nebojte se vymyslet spoustu návrhů a ty ohodnotit.

Navrhujte pro budoucnost – Nechte si otevřená vrátka pro budoucí rozšíření (datových formátů a struktur, protokolů i funkcí). Zde se třeba poznamenat, že váš program se může hodně rozšířit a pak už se zpětně nekompatibilní změny neprovádí bezbolestně.