Co bylo PRM045 Programování II

Komentář k praktickým testům a udílení zápočtů
Náplň letního semestru, zkouška
Textové soubory - opakování
Datové soubory - file of T
Přímý přístup k datovým souborům V pascalu
Vnější třídění - charakteristika úlohy, základní idea algoritmu přímého slučování
Datový typ stream, který umožňuje testovat hodnotu položky, kterou jsme z něj ještě nepřečetli,
programová realizace

vzhledem k poruše promítání v posluchárně jsem změnil obsah přednášky
zařadil jsem dynamické proměnné
k původnímu tématu se vrátíme příště

Ukaztele a dynamická alokace paměti,
bázový typ ukazatele, dynamická alokace paměti pomocí procedury new, procedura dispose pro uvolňování dynamické paměti, konstanta nil. Jednoduchý příklad.
Možnost vzniku "smetí v paměti" ztratíme-li možnost přístupu k dynamicky alokované proměnné
Jednosměrné spojové seznamy:
postavení seznamu, vkládání prvku za zadany prvek, vkládání prvku za zadaný prvek, vypouštění následujícího prvku, průchod seznamem,
Jiné typy seznamů, např.:
- Seznamy s hlavou a/nebo s ocasem (fiktivní prvky na začátku resp. na konci seznamu
- Cyklické seznamy
- Dvousměrné seznamy
Na rozmyšlenou:
Vytvořte podprogram pro otáčení cyklického seznamu s hlavou
rozmyslete si kolik proměnných potřebujete

stáhněte si programovou realizaci algoritmu přímého slučování

Zpět začátek

přednáška 8.března

Ještě jednou o praktických testech
Obracení jednosměrného seznamu
Procedura search pro uspořádaný seznam s hlavou a ocasem - vyhledávává resp. vkládá prvek s daným klíčem
Samoorganizující se seznamy ( např. nalezený prvek se stěhuje na první místo, nový prvek je vkládán na začátek) - skuste si naprogramovat.
Řídké polynomy - reprezentace pomocí cyklického seznamu s hlavou, její výhody,
ukázka alokace a uvolňování paměti "svépomocí", procedura pro nedestruktivní sčítání dvou řídkých polynomů.
Řídké matice - je třeba kriticky hodnotit přínosy té které implementace
Technické úlohy na rozmyšlenou:
- Napsat proceduru, která na základě dat ze vstupu vytvoří probíranou reprezentavci řídké matice
- Procedury pro "skladiště konzerv"
Práce Pascalu s pamětí - zásobník a heap, typická realizace heapu s ukazatelem na jeho vrchol a se seznamem "volných děr"

Zpět začátek

přednáška 15.března

Opakování typické organizace heapu v Pascalu.
Prostředky pro alokaci a uvolňování paměti
- Garbage collector - v Pascalu není
- new a dispose
- svépomocí - proč může být vhodné
- mark a release - nepoužívat !!!
- prostředky nízké úrovně
  MemAvail, MaxAvail, Getmem, Freemem - používat jen pro speciální účely, kdy je to nutné - teprve bude
Stromy, binární stromy - terminologie
Různá data se stromovou strukturou, různé datové reprezentace stromu
Kanonická reprezentace lesa pomocí binárního stromu
Průchody binárního stromu do hloubky - preorder, inoreder, postorder
a jejich rekursivní implemenace
Průchody binárním stromem do hloubky a souvislost s aritmetickými notacemi
(preorder - prefixová (polská), inorder - infixová, postorder - postfixová (inverzní polská).
Visualizace stromu pomocí indentace
Binární vyhledávací stromy a operace na nich: vyhledávání, vkládání a vypuštění prvku s daným klíčem
Animace operací s binárními vyhledávacími stromy

Zpět začátek

přednáška 22.března

Komenář k výsledkům praktických testů a k požadavkům v letním semestru.
Vypouštění intervalu z binárního vyhledávacího stromu.
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
Dokonale vybalancované stromy
Vytvoření dokonale vybalancovaného binárního vyhledávacího stromu o N prvcích z rostoucí posloupnosti čísel na vstupu.
Příklad jiné reprezentace stromu - "prošité stromy"
Prezence

Zpět začátek

přednáška 29.března

Záznam s variantami pevné a variantní položky, rozlišovací položka (může chybět), varinta může opět obsahovat pevné položky a další varianty
Význam - "nový typ" je "disjuktním" sjednocením jiných typů,
šetření pamětí - paměťový nárok je maximem paměťových nároků variant, nikoli souičtem.
Kdysi velmi důležité pro praktické programování,
dnes - téhož jde dosáhnout lépe v rámci objektového programování.
Odstraňování rekurse pomocí zásobníku - procedura inorder,
zásobník pomocí pole a pomocí lineárního spojového seznamu
Vývoj programování
- strojový kód, absolutní adresy
- První programovací jazyky
  proměnné, řídící příkazy, cykly, podprogramy
- Strukturované programování
  - strukturované řídící příkazy
  - datové struktury
  - role podprogramů
  - návrh programu metodou shora dolů
- Modulární programování
  separátní kompilace, abstraktní datové struktury, pojem metody
- Objektové programování - charakteristika přínosů
První princip objektového programování: zapouzdření - encapsulation
metody jsou atributem datové struktury
jednoduchý příklad
Terminologie:
třída ... datový typ
objekt ... proměnná daného typu (exemplář, instance třídy)

Zpět začátek

přednáška 5.dubna

Zapouzdření (encapsulation) - opakvání
Ochrana atributů třídy - private a public
Motivační příklad pro zavedení objektového programování
- Neobjektová fronta implementovaná v začátku pole
- Stejná fronta implementovaná objektově, podtřída realizující "cyklickou frontu"
Dědičnost.
Terminologie: Třída, objekt, podtřída, nadtřída.
Specikace inherited
Podtřída sdědí všechny atributy nadtřídy a může
- přidat datové atributy
- přidat další metody
- předefinovat metody sděděné z nadtřídy
Ochrana přiřazovacího příkazu - lze přiřadit do proměnné pro třídu objekt podtřídy a nikoli naopak.
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).
Unita obsahující objektovou implementaci dvojsměrných lineárních seznamů s hlavou
rozmyslet - příště se k ní vrátíme

Zpět začátek

přednáška 12.dubna

O zkoušce. Předběžné požadavky
Opakování objektové programování:
zapouzdření, ochrana přístupu k atributům tříd, dědičnost, ochrana přiřazovacího příkazu, ...
Polymorfismus, časná (early) a pozdní (late) vazba (binding) při volání metod, virtuální metody

Programy demonstrující virtuální metody

VMT tabulky a role konstruktoru
Příklad objektové hierarchie pro práci s geometrickými útvary
zdroják

Zpět začátek

přednáška 19.dubna

funkce typeof
Abstraktní třídy, přetypování ukazatelů na objekt.
Přetypování ukazatelů na objekt, implicitní paramtr metod self, operáror @.
Příklad objektové hierarchie pro práci s geometrickými útvary - zdroják
Celkové shrnutí objektového programování
Specifika vnějšího třídění
Streamy - opakování, program
Pojem běhu, idea algoritmu přímého slučování, jeho implementace
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ž implementace je složitější než u algoritmu přirozeného slučování.
Vylepšení algoritmů vnějšího třídění
- při slévání rovnou rozděluji do více souborů
- zvětšování délky běhů (a tedy i zmenšování jejich počtu) předtříděním ve vnitřní paměti - příklad použití dvou heapů
- použití více pásek - bude ještě podrobněji

Zpět začátek

přednáška 26.dubna

Idea polyfázového třídění výpočet optimálního rozdělení běhů na více pásek
Rozděl a panuj - metoda návrhu efektivních algoritmů
analýza, rekurze, syntéza
Klasifikace algoritmů vnitřního třídění z tohoto hlediska
vyvážený resp. nevyvážený rozklad,
důraz na analýzu resp. na sytézu
Složitost úlohy vnitřního třídění
- důkaz, že v nejhorším případě je n*log(n)
- myšlenka důkazu, že složitost je n*log(n) i v průměrném případě
- Pro nejlepší případ toto tvrzení neplatí
Hedání k-tého prvku z n prvků
- a la quicksort
- použitím heapu z n-k+2 prvků
- lineární algoritmus
AVL stromy
- Definice, nejhorší případ - Fibonnaciho stromy
- Interface procedur pro vkládání a vypouštění prvku z AVL stromu
  Procedura má výstupní boolovský parametr, který udává:
  zda se výška stromu přidáním zvětšila,
  resp. zda se výška stromu vypuštěním prvku zmenšila
- Rotace pro odstranění poruch v AVL stromu
- Pokud imlementujeme uzel sromu s polem ukazatelů na syny, lze programy o hodně zkrátit
- Při vkládání stačí provést jedinou rotaci
- Při vypuštění může být nutné provést rotaci v každím uzlu na cestě od kořene k vypuštěnému prvku

Zpět začátek

přednáška 3.května

Hašování, myšlenka, hašovací funkce bez kolizí pro statické tabulky nevelké velikosti, kolize a různé metody jejich odstraňování, metoda řetízků a její modifikace, aby šlo i vypouštět.
Dynamické programování
- Hledání optimálního uzávorkování násobení posloupnosti matic.
- Helání nejdelší společné posloupnosti dvou posloupností
  Trasovací tabulka konkrétního výpočtu
- Problém batohu s celočíselným zadáním
  Tabulka konkrétního výpočtu
- Příklady dalších úloh, které lze efektovně řešit pomocí dynamického programování
  - Hledání optimálního vyhledávacího stromu (vstup: pravděpodobnosti dotazů) - viz, kniha N.Wirtha
  - Hledání nejkratší triangulace - viz. např. kniha P. Töpfera
Idea diskrétní simulace
Antagonistická hra dvou hráčů s úplnou informací a nulovým součtem, Shannonova věta, algoritmus minimaxu, jeho negamaxová implementace

Zpět začátek

přednáška 10.května suplování Dr. Holan

Programovací systém Delphi
Programování řízené událostmi
prostředí - vycházíme od spustitelného programu
komponenty jako pojem a jejich použití
implicitní pojmenovavání
vlastnosti
inspektor objektů
TabOrder a BitBtn.Kind jako příiklady side-effectu vlastností
reakce na události
sdílení obslužných procedur
přetypováváni nebezpečné a bezpečné, "is"
chyby, vyjimky try-except

Zpět začátek

přednáška 24.května

Mimo jiné bude algoritmus alfa-beta prořezávání

Zpět začátek

PRM045 Programování II - co bylo na přednáškách