PRG031 - Co bylo na přednášce - paralelka úterý 14:00 S3

přednáška 17.února
přednáška 24.února
přednáška 2.března
přednáška 9.března
přednáška 9.března 15:40 - místo algebry
přednáška 16.března
místo přednášky 23.dubna je algebra
přednáška 30.března
přednáška 30.března 15:40 - místo algebry
místo přednášky 6.dubna je algebra
přednáška 13.dubna
přednáška 20.dubna
přednáška 20.dubna 15:40 - místo algebry
přednáška 27.dubna
přednáška 4.května
místo přednášky 11.května je algebra
přednáška 18.května

Hromadná konzultace 21.4. ve 14.00 v S3

přednáška 17.února
- Poznámky k testům a zkouškám
- Náplň letního semestru
- Opakování
  - Způsoby předávání parametrů v Pascalu hodnotou, referencí a const
  - Vypouštění z binárního vyhledávacího stromu.
    Vypuštění prvků z intervalu - "nejprve podstromy, pak kořen";
    vypouštění kořene - raději pomocí parametru předávaného referencí než pomocí ukazatele na předchůdce
- Vkládání do kořene binárního vyhledávacího stromu
- Datová reprezentace binárního stromu s polem synů, aby šlo předat směr jako parametr podprogramu. Program
zpět na začátek
přednáška 24.února
- Prošité stromy
- Datové soubory a práce s nimi
- Přímý přístup k datovým souborům
- Vnější třídění - charakteristika úlohy. Oprávněnost omezení se na skvenční přístup k souborům. Počet přístupů na disk je vhodnou mírou složitosti pro porovnávání algoritmů vnějšího třídění.
- Definice běhu, myšlenka algoritmu přirozeného slučování
- Datový typ stream, který umožňuje testovat, co "příště přečtu".
  Programová jednotka obsahující podprogramy pro práci se streamy (otevření, kopie prvku, kopie běhu, slévaní běhů atd. )
- Implementace algoritmu přirozeného slučování pomocí streamů
- Rozmyslete - algoritmus, který slévá "jednice do dvojic", ..... , 2^(n-1)-tice do 2ⁿ-tic, není motivací pro algoritmus přirozeného slévání, ale neúnosně pomalým algoritmem, jehož implentace je složitější než u algoritmu přirozeného slučování.
- Zmenšení počtu běhů v souboru "předtříděním" ve vnitřní paměti; použití dvou heapů.
zpět na začátek
přednáška 2.března
- Různá vylepšení algoritmů vnějšího třídění.
- Polyfázové třídění, optimální distribuce běhů.
- Stručný vývoj metodologie programování; Strukturované, modulární programování.
- Objektové programování
- Motivační příklad implementace fronty neobjektové a objektové
- Zapouzdření (encapsulation).
- Dědičnost (inheritance). Podtřída může přidat libovolné (datové nebo metody) atributy a předefinovat metody nadtřídy. Klíčové slovo inherited.
- Ochrana přístupu k atributům - private a public
- Terminologie třída (class) je typ, objekt (instance) je proměnná daného typu.
- Ochrana přiřazovacího příkazu mezi objekty třídy a nadtřídy.

zpět na začátek

přednáška 9.března
přednáška 9.března 15:40 - místo algebry
- Objektové programování - opakování.
- Rozbor ilustračního příkladu realizujícího prostředky pro práci se dvousměrnými spojovými seznamy s hlavou, pomocí tří abastraktních tříd.
- Polymorfismus, virtuální metody, jejich realizace pomocví tabulky virtuálních metod, role konstruktoru. Destruktor.
- Rozšířená syntaxe procedur new a dispose s voláním konstrukroru resp. destruktoru.
- Doporučení pro objektové programování v Pascalu
  1. Neužívejte staticky alokované objekty.
  2. Při alokaci a dealokaci dynamických objektů užívejte jen rozšířenou syntaxi new resp. dispose s voláním konstruktoru resp. destruktoru.
  3. Každá třída, jejíž objekty chcete vytvářet (není jen abstraktní), by měla mít konstruktor a destruktor (třeba zděděný nebo prázdný).
  4. Prvním příkazem konstruktoru podtřídy by mělo být zavolání konstruktoru její nadtřídy (slušnost a dobrý návyk).
- Ilustrační příklady na virtuální metody.
- Hledání K-tého prvku z N prvků
  - Hledání největšího prvku Na N-1 porovnání (přesně); důkaz, že nejde rychleji
  - Hledání druhého největšího prvku na N-2+hor(log₂(N)) porovnání (přesně - kde hor(x) je "horní celá část z x).
  - Nalezení prvních m prvků z posloupnosti délky m² na m² porovnání (asymptoticky)
  - Využití myšlenky heapsortu
  - Využití myšlenky quicksortu
  - Lineární algoritmus
- Na rozmyšlenou:
  1. Analyzujte ilustrační program.
  2. Pohrejte si s prográmky na vitruální metody.
  3. Důkaz, že druhého největšího nejde nalézt na méně než N-2+hor(log₂(N))porovnání. Není snadný.
  4. Nalezněte konstantu pro lineární algoritmus hledání k-tého prvku z N založený na dělení na pětice.
zpět na začátek
přednáška 16.března
- Příklad "a la zkoušková písemka" - rozbor.
- Hašování
- Topologické třídění - ještě se k němu vrátíme
zpět na začátek
přednáška 30.března - ještě nebyla
- Topologické třídění, Dijkstrův algoritmus pro acyklické grafy
- AVL stromy, definice, Fibonaciovy stromy jako nejhorší případ AVL stromů.
- Jednoduchá a dvojitá rotace pro odstranění defektu ve výšce podstromů
- Datová reprezentace AVL stromu
- Procedura SEARCH pro AVL stromy (zdrojový text - bude). Při vkládání prvku do AVL stromu stačí provést (nejvýše) jednu rotaci.
- Vypouštění může vyžadovat tolik rotací, jak je dlouhá cesta k vypouštěnému prvku.
- Opakování myšlenky dynamického programování
- Algoritmus hledání optimálního vyhledácího stromu založený na dynamickém programování a jeho vylepšení s časovou složitostí O(n²)
- Důkaz, že složitost úlohy vnitřního třídění je alespoň n*log(n) jak v nejhorším, tak v průměrném případě. Pro nejlepší případ takové tvrzení neplatí.
- Na rozmyšlenou:
  1. Naprogramovat topologické třídění
  2. Naprogramovat konstrukci optimálního vyhledávacího stromu
zpět na začátek
přednáška 30.března15:40 - místo algebry
- Objektové programování a programy řízené událostmi.
- Princip práce programu běžícího pod OS Windows
- Prostředí Delphi
- Komponenty, vlastosti (properties), události (events)
- inspektor objektů, zdrojový program, soubor DFM
- Vytváření jednoduchého programu v Delphi
- Užívání helpu
- Práce s časem a datem
zpět na začátek
přednáška 13.dubna
Delphi pokračování
- Komponenty Edit, Label, Button, Memo
- Checkbox, Radiobox, RadioGroup, ListBox a Combox, UpDown
- Typické vlastnosti komponent (poloha a velikost okna, Caption a Name, Visible a Enable, TabOrder a TabStop, Lines, WordWrap, Font, Color, atd. .....)
- "Hlavní" událost komponenty, události klávesnice a myši, typy přetahovaní
- Timer a jeho užití
zpět na začátek
přednáška 20.dubna
- Jak počítače hrají hry "typu šachy"
- Shanonnova věta o existenci neprohrávající strategie pro jednoho z hráčů, algoritmus minimaxu.
- Negamaxová implementace minimaxu
- Architektura šachového programu typu A. Algoritmus hrající střední hru (generátor tahů, horizont, pojem tiché pozice, statická ohodnocovací funkce). Vliv zvětšování horizontu. Specifika zahájení a koncovek.
- Alfa-beta jako metoda (případně) rychlejšího výpočtu přesné minimaxové hodnoty. Princip a implementace. Počet volání statické ohodnocovací funkce jako adekvátní míra efektivity Alfa-beta metody. Metody analýzy plausibilty (podpora efektivity alfa-beta procedury): preferování bracích tahů a šachů generátorem tahů, killery.
- Použití alfa-beta metody jako heuristiky - metoda okénka, kaskádní varianta
- Princip diskrétní simulace, kalendář událostí, událostní a procesní přístup.
zpět na začátek
přednáška 20.dubna 15:40 - místo algebry
- Grafika v systému Delphi. Kreslení a malování.
- Canvas, Pen a Brush
- Práce s barvami, RGB model
- Explicitní práce s Device Contextem
zpět na začátek
přednáška 27.dubna
- Příklad analýzy systému pro modelování diskrétní simulací.
- B stromy. Definice, algoritmy vyhledávání, vkládání a vypouštění.
- Delphi.
  - Objektový model
  - Ochrana atributů třídy: private, public, protected (published bude později)
  - Vlastnosti (propreties) jako "virtuální" datové atributy; specifikace přístupových funkcí read a write, defaultní hodnoty).
  - Tvar unity, přetěžování metod a funkcí
zpět na začátek
přednáška 4.května
zpět na začátek
přednáška 18.května
zpět na začátek

Hromadná konzultace 21.4. ve 14.00 v S3

Zpět PRG031