přednáška 7.března
- Termíny praktických testů jsou SISu.
- opakování dynamicky alokované proměnné, ukazatele, procedury new a dispose
- Ří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"
- 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é -
na přednášce 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
- Visualizace (binárního) stromu pomocí indentace - jednoduchá rekursivní procedura
- Pojem binárního vyhledávacího stromu
- Algoritmus vyhledávání v binárním vyhledávacím stromě
přednáška 14.března
- Opakování - binární vyhledávací stromy
- 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
rekursivní podprogramy, které je realizují, diskuse způsobů předávání parametrů těmto podprogramům
- Animace operací s binárními vyhledávacími stromy
- Vypouštění intervalu z binárního vyhledávacího stromu (rekursivně z podstromů a pak z kořene)
rozmyslet a zkusit naprogramovat nerekursivní řešení
- 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.
- Vnitřní a vnější třídění
- Vnitřní třídění - specifikace úlohy, adresní a asociativní algoritmy
- Radixové třídění - příklad adresního třídícího algoritmu
- Asociativní algoritmy - založené na porovnávání klíčů
měření časové složitosti - míry C (počet porovnání) a M (počet přiřazení),
paměťová složitost,
třída algoritmů, které "třídí "na místě" (in situ)
- Jednoduché algoritmy složitosti O(n2):
- přímé zatřiďování
- třídění výběrem
- třídění výměnami - bubblesort, shakesort
Programy - vytiskněte si na příští přednášku spolu se souborem
obsahujícím nerekursivní verzi algoritmu Quicksort
- prezence
přednáška 21.března
- apel:
měli byste během nejdéle 2 týdnů mít zažitu práci s ukazateli a dynamicky alokovanými proměnnými,
abyste neměli problémy s další látkou
- povídání o zkoušce v letním semestru
- Opakování jednoduchých algoritmů vnitřního třídění - zdrojáky
- Datová struktura heap (hromada) a základní operace na ní
delete-min, přidání prku
- Reprezentace heapu v poli - úsek pole reprezentuje ne jeden strom, ale les
- Procedura sift, která přidává k existujícímu heapu prvek "před ním v poli"
- Algoritmus heapsortu - složitost i v nejhorším případě n*log(n)
- Důkaz tvrzení, že neexituje žádný algoritmus vnitřního třídění, kterému by v nejhorším případě stačilo méně než n*log(n) porovnání
- Náčrt důkazu, že obdobné tvrzení platí i pro průměrný případ
- Pro nejlepší případ analogické tvrzení neplatí - protipříklad
- Quicksort - myšlenka; rekursivní implementace s pivotem jako zarážkou;
časová složitost v nejlepším a nejhorším případě.
- Algoritmus Quicksort, jeho rekursivní verze
- Rozmyslet si:
V čem může být quicksort lepší než heapsort, když jsme dokázali, "že heapsort je optimální" ?
Vytiskněte si: nerekursivní verzi quicksortu a soubory týkající se vnějšího třídění unita streams a algoritmus přirozeného slučování
přednáška 28.března
- Odstraňování rekurze pomocí zásobníku
- Algoritmus Quicksort, jeho rekursivní a nerekursivní verze
naprogramujte si verzi se spojově realizovaným zásobníkem, která odkládá na zásobník obě žádosti o setřádění intervalu
- paměťová složitost quicksortu
- vylepšení quicksortu
- pivot jako medián malého počtu nahodně vybraných prvků pole
- je-li pivot prvek tříděného pole, může sloužit jako zarážka
- odstranění rekurze
- do zásobníku dřív žádost setřídění delší úseku
- malé úseky se nevyplatí třídit quicksortem - do zásobníku je nedáváme, setříme všechny najednou přímým zatřiďováním
- detekce "velmi špatných případů" a případné následné použití jiného algoritmu
- multiplikativní konstanta u časové složitosti quicksoru může být menší než u heapsortu
- idea mergesortu - rekursivní verze je v unitě
naprogramujte si nerekursivně
- metoda návrhu rozděl a panuj: analýza, rekurze, sytéza
" klasifikace" algoritmů vnitřního třídění z tohoto hlediska
- datové soubory - určení, výhody a nevýhody oproti textovým souborům
reset, rewrite, close, read, write
- přímý přístup k datovým souborům - proč je podstatně pomalejší než sekvenční
podprogamy seek, pos, setpos, truncate,
- Vnější třídění - charakteristika úlohy, základní idea algoritmu přímého slučování, definice běhu
- Datový typ stream, který umožňuje testovat hodnotu položky, kterou jsme z něj ještě nepřečetli,
jeho programová realizace
- programová realizace algoritmu přímého slučování
přednáška 4.dubna
- Vnější třídění - opakování algoritmu přímého slučování
- Rozmyslete - algoritmus, který slévá "jednice do dvojic", ..... , 2(n-1)-tice do 2n-tic,
není motivací pro algoritmus přirozeného slévání, ale neúnosně pomalým algoritmem,
jehož implementace je navíc složitější než u algoritmu přirozeného slučování.
- různá vylepšení základní myšlenky přímého slučování
- při slévání rovnou rozděluji do více souborů
- více pásek
- 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ů
- Idea polyfázového třídění výpočet optimálního rozdělení běhů na více pásek,
odvození optimálního rozdělení počtu běhů na pásky,
implementační poznámky - fiktivní běhy
- Záznam s variantami pevné a variantní položky, rozlišovací položka (může chybět),
varianta 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 jejich souč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í.
- 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ů
přednáška 11.dubna
- 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)
- Ochrana atributů třídy - private a public
- Motivační příklad pro zavedení objektového programování
- Dědičnost.
Terminologie: Třída, objekt, podtřída, nadtřída.
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.
- Rozšířená syntaxe procedur new a dispose s druhým parametrem voláním konstruktoru resp. destruktoru
-
Doporučení pro objektové programování v Pascalu:
- Neužívejte staticky alokované objekty.
- Při alokaci a dealokaci dynamických objektů užívejte jen rozšířenou syntaxi
new resp. dispose s voláním konstruktoru resp. destruktoru.
- 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ý).
- 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
abstraktní typy, přetypování ukazatelů na objekt,implicitní parametr self, operátor @, funkce typeof, destruktor třídy head, ...
rozmyslet- připravit si dotazy
ne všechno jsme vysvětlili "do konce" - příště se k ní vrátíme podrobněji
- ukázkové příklady na polytmorfismus s hierarchií tříd zvíře, pes kočka
bude vyloženo příště
přednáška 18.dubna
- Opakování objektové programování:
zapouzdření, ochrana přístupu k atributům tříd, dědičnost, specikace inherited, ochrana přiřazovacího příkazu, přetypování, operátor @, ...
- Polymorfismus, časná (early) a pozdní (late) vazba (binding) při volání metod, virtuální metody
- Programy demonstrující virtuální metody -
třída zvíře a podtřídy pes a kočka s virtuálními metodami
- VMT tabulky a role konstruktoru
- Funkce typeof
- Příklad objektové hierarchie pro práci s geometrickými útvary
zdroják
- Nový komentář k "dopručením pro objektové programován v Pascalu" - viz minulá přednáška
- prezence
přednáška 25.dubna
- O praktických testech. O zkoušce
- definice dokonale vybalancovaného stromu
- rekursivní podprogram, který vytvoří dokonale vybalancovaný binární vyhledávací strom
z prvních N čísel rostoucí posloupnosti (uložené v textovém souboru)
rozmyslet:odstraňte z této procedury rekurzi (pomocí zásobníku)
- Dokonale vybalancované binární vyhledávací stromu nejsou vhodné pro dynamické tabulky (t.j. tabulky, ze kterých se mohou prvky vyhazovat a do nichž se mohou vkládat.
- AVL stromy - definice a datová reprezentace ( v každém uzlu "navíc" položka bal: -1..1,
která udává rozdíl výšek levého a pravého podstromu
- Fibonnaciovy stromy - nejhorší případ AVL stromů
- Rotace pro odstranění poruch v AVL stromu
- Algoritmy pro vkládání prvku do AVL stromu a vypouštění prvku z něj mají složitost log(n)
při vkládání stačí provést (je-li to potřeba) jednu rotaci
při vypouštění je v nepříznivém případě provést rotaci v každém prvku na cestě od kořene stromu a vypouštěnému prvku
- Rozdíl mezi datovými strukturami pole a record není jen v to, že všechny složky pole musí být stejného typu,
ale také v tom, že výběr adresy složky recordu jde udělat již za překladu (selektor je identifikátor položky),
kdežto u pole je selektorem u pole je indexový výraz, jehož nemusí a zpravidla není zníma během překladu.
Proto jde udělat cyklus přes prvky pole, jde indexový výraz předat jako parametr, a pod.
- Z výše zmíněných dúvodů je výhodnější definovat typ uzlu AVL stromu s polem ukazatelů na dva podstromy ( indexované třeba výčtovým typem (left, right) ), protože pak můžeme procedurám pro rotace zadat směr rotace jako parametr a nemusíme "programovat totéž dvakrát".
- Dynamické programování
- Hledání optimálního uzávorkování součinu N matic
- Problém batohu s celočíselným zadáním - trasování konkétního výpočtu
rozmyslete si tento algoritmus - příště se k němu vrátíme
obecný problém batohu je NP úplný (stručně řečeno to znamená,že
- není znám polynomiální algoritmus pro řešení úlohy
- neumíme dokázat, že polynomiální algoritmus neexistuje
- kdyby byl polynomiální algoritmus nalezen, znamenalo by to existenci polynomiálních algoritmů
pro celou řadu složitých problémů
proto matematici příliš v možnost existence takového algoritmu nevěří)
- Příklady dalších úloh, které lze efektivně řešit pomocí dynamického programování (budou probrány na cvičeních)
- Hledání optimálního vyhledávacího stromu (vstup: pravděpodobnosti dotazů na jednotlivé hodnoty klíčů) -
včetně modikace, která dosahuje složitost O(n2) - viz, kniha N.Wirtha
- Hledání nejkratší triangulace - viz. např. kniha P. Töpfera
přednáška 9.května
a
přednáška 9.května
(mimo jiné) na přednášce bude
- O zkouškách
rozmyslete si:komentáře k předběžným požadavkům ke zkouškám
- Algoritmus řešení problému batohu
- Hledání nejdelšího společného podřetězce - trasování konkrétního výpočtu
- Ještě několik poznámek k objektovému programování
- Hledání k-tého prvku
- Lineární algoritmus pro hledání mediánu
- hledání nejdelšího symetrického úseku
- naivní algoritmus složitosti O(n3)
- vylepšený algoritmus složitosti O(n2)
prověřujenme najednou včechny intervaly s daným středem
- rozmyslete: existuje lineární algoritmus
- Shanonnova věta o existenci neprohrávající strategie
algoritmus minimaxu jako její důkaz
- Negamaxová modifikace algoritmu minimaxu
- Použití algoritmu minimaxu v případě her, kde je úplný strom hry neúnosně velký - počítání do zvoleného horizontu (doplněné vyhledáváním "tichých" pozic) a
použití statické ohodnocovací funkce pro ohodnocení listů tohoto podstromu
minimax v tomto kontextu již není používán jako přesný algoritmus
pro hledání optimální strategie, ale jako součást heuristiky
- Kvalita statické ohodnocovací funkce versus hlubší horizont
- Algoritmus alfa-beta prořezávání jako efektivnější nalezení přesné minimaxové hodnoty
- efektivita alfa- beta prořezávání a různé metody analýzy plausibilty (t.j. snah o to, aby bylo prořezávání efektivní)
- metoda okénka a kaskádní výpočet minimaxové hodnoty
- Aritmetické výrazy - opakování a shrnutí
- reprezntace pomocí stromu a notací (prefixová, infixová a postfixová)
- algoritmy vyhodnocování výrazů v jednotlivých reprezentacích
- algoritmy převodů mezi jednotlivými reprezentacemi
- rozmyslete: vyčíslení hodnoty infixového výrazu přímým spojením
algoritmů převodu na postfixovýzápis s pro vyčíslování hodnoty postfixového zápisu.
přednáška 23.května
- Lineární algoritmus pro nalezení nejdelšího symetrického úseku
jako příklad toho, že složitost algoritmu přirozeně popsaného dvěma cykly v sobě může být lineární
- Standardní podprogramy getmem a freemem jako nízkoúrovňové prostředky pro alokaci a dealokaci paměti
realizace dynamického pole v Pascalu jejich pomocí a přetypováním pointeru
- Hašování
bezkolizní hašování, kolize a různé metody jejich řešení, metoda řetízků, efektivita hašování
- optimální rozložení abecedy s danými četnostmi písmen na klávesy mobilního telefonu
- Komentář ke zkoušce
- Pozvání na výběrovou přednášku PRM046 Programování III pro neinformatiky,
jejíž náplní je neprocedurální programování