Opakování: spodní odhad časové složitosti úlohy vnitřního třídění je v nejhorším i průměrném případě n*log(n)
opakování: quicksort
Časová a paměťová složitost quicksortu, různé optimalizace
Opakování: heapsort
datová struktura heap (hromada) a dvě základní operace s ní: delete-min a přidej prvek
hromada jako část pole, reprezentace hromady v poli,
algoritmus heap sortu
Časová a paměťová složitost heapsortu/li>
porovnání algoritmů heapsort a quicksort
algoritmus vnitřního třídění sléváním - mergesort
netřídí na místě
Vnitřní a vnější třídění - rozdíly
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í
podívejte se na ní, příště si budeme povídat o různých způsobech vylepšení základní idey přímé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, diskuse o tom, že nepomůže pracovat s příliš mnoha (režie OS, někaou dobu trvá vybrat nejmenšího - i když použijeme heap)
idea polyfázového třídění - ideální distribuce běhů bude později
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ů bude později
Rozmyslete si:- 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í.
tuto ideu lze použít u vnitřního třídění:
Mergesort třídí v čase n*log(n), ale ne in situ - potřebuje dvě pole
Ukazatele 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é
V definici typu ukazatel může být použit identifikátor jeho bázového typu i když ještě nebyl bázový typ definován.
Jednosměrné spojové seznamy:
postavení seznamu, vkládání prvku za zadany prvek, vkládání prvku před zadaný prvek,
vypouštění následujícího prvku
Další operace s jednosměrnými spojovými seznamy:
průchod seznamem, hledání prvku v seznamu, hledání s použitím zarážky
opakování: typ ukazatel, bázový typ, statická a dynamická alokace paměti, procedury new a dispose, ...
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) - zkuste si naprogramovat.
Řídké polynomy - reprezentace pomocí cyklického seznamu s hlavou,
její výhody oproti prvoplánovým alternativám (např. pole koeficientů, jednoduchý nezacyklený seznam nenulovách členů,
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á úloha na rozmyšlenou:
Napsat proceduru, která na základě dat ze vstupu vytvoří probíranou reprezentaci řídké matice
Vytvoření dokonale vybalancovaného binárního vyhledávacího stromu
o N prvcích z rostoucí posloupnosti čísel na vstupu. Zkuste naprogramovat i nerekurzivně.
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, proto se spíše používají jiné definice balancovaných stromů.
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
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ěří)
Rozmyslet:
algoritmus pro optimalizaci rozložení písmen na klávesy mobilního telefonu
(jsou zadány frekvence písmen, optimalizuje se počet stisků kláves).
minimální triangulace - viz kniha P.Topfera
Optimální binární vyhledávací strom k zadaným frekvencím dotazů
Charakteristika metody dynamického programování
Hledání k-tého prvku,
algoritmus využívající datovou strukturu heap(hromadu), algoritmy založené na idei quicksortu
Lineární algoritmus pro hledání mediánu
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 podstatně lépe v rámci objektového programování.
Dědičnost.
Terminologie: Třída, objekt, podtřída, nadtřída.
Podtřída zdě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.
Ochrana atributů třídy - private a public
konstruktory
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, ... příklad je poměrně komplexní, ilustruje mnoho jevů, některé jsme ještě neprobrali,
vrátíme se k němu, rozmyslete si případné dotazy
Opakování objektového programování:
zapouzdření (encapsulation), dědičnost (inheritance), ochrana přiřazovacího příkazu
Terminologie: Třída, objekt, podtřída, nadtřída.
Ochrana atributů třídy - private a public
konstruktory a destruktory
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).
Polymorfismus, virtuální metody, VMT tabulka, role konstruktoru
funkce typeof a její použití
ještě jednou k příkladu s dousměrnými cyklickými seznamy
abstraktní typy, implicitní parametr self, přetypování, operátor @, použití typeof, proč je destruktor třídy link virtualní,
Definice vyhraných a prohraných pozic, jejich hledání v případě jednoduchých konkrétních her
Antagonistické hry dvou hráčů s úplnou informací a nulovým součtem
Shanonnova věta o existenci neprohrávající strategie,
algoritmus minimaxu jako její důkaz
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
motivace alfa-beta metody procházení stromu hry jako heuristiky pro efektivnější nalezení přesné minimaxové
hodnoty zadaného stromu hry.
Algoritmus alfa-beta prořezávání jako efektivnější nalezení přesné minimaxové hodnoty
Alfa-beta projde v nejhorším případě celý strom, tedy nejenom, že nic neušetří, ale trvá déle, protože udržování parametrů alfa a beta něco stojí.
V optimálním případě projde sqrt(P) listů, kde P je počet listů, který by prošel minimax. Počet navštívených listů se se používá jako míra složitosti proto,
že se v nich volá statická ohodnocovací funkce, jejíž výpočet je náročnější než průchod stromem.
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
Kaskádní varianta s použitím okénka
Program, který má hrát celou partii má tři fáze:
zahájení - řeší se knihovnou
střední hra - probírali jsme podrobně: pracujeme se stromem hry ikdyž to ve skutečnosti strom není (více cest do téže pozice)
koncovky - mohou být řešeny různě, hlavní rozdíl je, že je "málo pozic a mnoho variant", proto se ukládají již ohodnocené pozice do tabulky
Speciální problémy se mohou řešit zcela jinak - např. zpětná analýza našla pozice, v nichž "pravidlo 50 tahů" mění hru