Zkouška

Písemná část

písemná část zkoušky
1. upřesnění zadání, pokud je potřeba
2. postřehy
3. algoritmy
  - nevadí, když nevymyslíme nejoptimálnější
  - svou volbu musíme zdůvodnit
4. datové struktury (reprezentace dat)
5. dekompozice programu (objektový návrh)
6. závěr/shrnutí (diskuze)

Ústní část

algoritmizace
- složitost algoritmu, složitost úlohy/problému
- fronta, zásobník, BFS, DFS
- halda
- rekurze
- základní grafové algoritmy
  - hledání nejkratších cest a minimálních koster (Dijkstra, Kruskal, Bellman-Ford, Jarník, Borůvka)
  - topologické uspořádání
  - způsoby reprezentace grafu
- stromové datové struktury a algoritmy na nich
  - BVS
  - AVL-strom
  - A-B-strom
- třídicí algoritmy, vnější třídění
- strom hry, minimax, alfa-beta prořezávání
- memoizace a dynamické programování a typické problémy takto řešené (závorkování násobení matic, celočíselný problém batohu)
programování
- OOP
  - princip/idea
  - dědičnost
  - zapouzdření
  - virtuální metody, abstraktní metody a třídy
- dekompozice
  - funkční
  - objektová (SOLID a spol.)
  - modulární
- diskrétní simulace
- programování řízené událostmi
- C# generické funkce a třídy
- C# delegáty

Výpisky z programování

specifika C#, objektově orientované programování
- C# je staticky typovaný, je překládaný (ne interpretovaný)
- objekt = data + funkce (metody)
- dělíme problém na podproblémy, izolujeme části kódu, ukrýváme vnitřek (= zapouzdření)
- objekty jsou instance třídy
- statické metody a atributy příslušejí přímo třídě
- statické třídy neumožňují vytvoření instance
- modifikátory přístupu (umožňují snazší zapouzdření)
  - public – přístupné všem
  - private – přístupné jen metodám dané třídy (default)
  - protected – přístupné této třídě a potomkům
- konstruktory
  - klíčová slova this, base
- přetěžování metod/operátorů
- předávání proměnné referencí
  - modifikátory ref, out, in (liší se)
- properties – vlastnosti (get, set)
- child class se definuje pomocí dvojtečky (class child:parent)
- virtuální metody
  - zděděné metody v synovských třídách můžeme přepisovat, pokud použijeme v rodiči virtual a v synovi override
    - alternativní (horší) přístup s klíčovým slovem new (schová rodičovskou metodu)
  - virtuální metody jsou reprezentovány odkazy z VMT (virtual method table, tabulka virtuálních metod)
  - VMT přísluší celé třídě (vytváří ji překladač)
  - každý objekt má ukazatel na svou VMT (tudíž syn přetypovaný na otce může podle VMT poznat, že je syn) – umisťuje ho tam konstruktor
  - přepisování metod je potřeba kvůli tomu, že synovské třídy často inicializujeme s typem rodiče (abychom ke všem objektům různých synovských tříd mohli přistupovat jednotně) = polymorfismus
- abstraktní třída – může mít abstraktní metody, nelze přímo vytvořit její instanci
- abstraktní metoda – pouze hlavička funkce, musí být obsažena v abstraktní třídě, nelze ji volat (musí se přepsat)
- modifikátor sealed – u třídy zakazuje dědění, u metody zakazuje override
- interface – vypadá jako abstraktní třída (bez těl funkcí), zachází se s ním podobně
- delegáty
  - chceme předat funkci jako parametr (= zacházet s ní jako s proměnnou)
  - nejdříve musíme definovat datový typ reprezentující danou funkci – pomocí klíčového slova delegate
    - public delegate int compare(object a, object b);
  - pak můžeme uložit odkaz na funkci (metodu) do proměnné s tímto typem
  - odkazy na funkce lze řetězit pomocí operátoru sčítání (odčítání naopak odebírá ze seznamu)
  - klíčové slovo delegate se rovněž používá při definici anonymních funkcí (existují rovněž lambda funkce – u nich je jiný přístup k typování)
- namespace
další prvky C#
- struktury jsou v C# hodnotové typy (na rozdíl od objektů – ty se předávají referencí)
- pole – pevný počet prvků
- obecný seznam – ArrayList ze System.Collections
- typovaný seznam – List<type> (tzv. generická třída)
- logické operátory – pro částečné i úplné vyhodnocení
- try, catch, finally, throw
- paralelní procesy – vlákna, asynchronní volání
diskrétní simulace
- simulujeme mnoho procesů a to, jak se ovlivňují
- nemusíme sledovat celý průběh procesu, zajímají nás jenom důležité chvíle (např. začátek a konec) – tzv. události
- simulační jádro – provádí obsluhu událostí, aktivně je „vykonává“
- kalendář událostí – přehled událostí s časem, kdy mají nastat
- simulační jádro si typicky bere první událost z kalendáře (tedy tu naplánovanou na nejdřívější čas)
- jádro také může události do kalendáře přidávat nebo je rušit
- kalendář je obvykle schopen měřit čas (tedy určit čas simulace)
- simulace končí, jakmile po obsluze události zůstane kalendář prázdný
- každý proces je v nějakém stavu, typické stavy jsou
  - běží (aktivní) – právě se obsluhuje jeho událost
  - naplánovaný – čeká v kalendáři událostí
  - čeká (pasivní) – čeká, až ho někdo vzbudí
  - ukončený – doběhl a nebude mít další události
- pokud simulační jádro běží paralelně ve více vláknech, plynou z toho problémy paralelizace – race condition, deadlock
- možná implementace
  - kalendář událostí = cyklický spoják
  - plánujeme procesy (o jakou událost jde, si pamatuje proces)
  - pokud proces závisí na jiném procesu, tak se jím nechá aktivovat po jeho skončení (= pasivní čekání; aktivně čekající proces by se neustále ptal, jestli může pokračovat, což by zatěžovalo procesor)
programování řízené událostmi = program reaguje na události (obvykle uživatelské nebo simulované – při diskrétní simulaci), zpracovává je a transformuje, předává mezi úrovněmi
objektový návrh
- lze ho pojmout jako návrh hlaviček tříd a metod a definice atributů
- snažíme se problém rozdělit na co nejmenší smysluplné součásti
- UML diagram – krabičky představují třídy, spojnicemi se značí relace (případně komunikace)
- data flow diagram – orientovaný graf, vrcholy představují operace, hrany jsou popsány putujícími daty
SOLID
- single reponsibility – každá entita zodpovídá za jednu věc
- open-closed – entity jsou otevřené rozšíření, ale uzavřené změnám
  - můžeme odvodit novou třídu s více daty a funkcemi, ale rozhraní stávající třídy se nebude měnit
- Liskov substitution – místo rodiče lze použít potomka
  - s objektem synovské třídy lze zacházet jako s objektem rodičovské třídy (Tygra lze použít, jako by to byla Kočka)
- interface segregation – více specifických rozhraní (pro různé klienty) je lepších než jedno univerzální
- dependency inversion – závislost by měla být na abstraktním, ne na konkrétním (implementace se mění často, kdežto abstrakce je trvalejší)
další pravidla
- Deméteřin zákon – funkce by neměla volat jiné funkce, které jsou od ní „příliš daleko“ (měly by být přibližně na její úrovni; porušení zhoršuje udržovatelnost kódu a zapouzdření)
- DRY – neopakuj se
- high cohesion, low coupling – související věci by měly být v programu u sebe, ale měly by být provázané jen zlehka (přes interface)
grafové algoritmy
- reprezentace grafu
  - matice sousednosti – řádky i sloupce odpovídají vrcholům, jednička odpovídá hraně, nula nehraně
  - matice incidence – řádky indexovány vrcholy, sloupce hranami, jednička určuje, že vrchol náleží hraně
  - seznam vrcholů a u každého seznam přilehlých hran