Zpět PRM001
PRM001 Programování - středa 12:20 M1
Co bylo resp. bude na přednášce - letní semestr
- přednáška 19.února
- přednáška 26.února
- přednáška 5.března
- přednáška 12.března
- přednáška 19.března
- přednáška 26.března
- přednáška 2.dubna
- přednáška 9.dubna
- přednáška 16.dubna
- přednáška 23.dubna
- přednáška 30.dubna
7.května bude místo přednášky z programování analýza
14.května rektorský den
- přednáška 21.května od 10:40 programování místo analýzy
(analýza od 9:00 místo algebry)
- přednáška 21.května od 12:10
- přednáška 19.února
- Komentář k zápočtovým testům.
- Zkouška a zápočet v letním semestru.
- Klasifikace třídících algoritmů
- vnitřní - třídění polí
- vnější - třídění souborů
- Radixové třídění jako příklad adresového algoritmu vnitřního třídění
- Paměťové nároky vnitřního třídění - třída algoritmů pracujících in situ
- Jednoduché třídící algoritmy s kvadratickou složitostí
- zatřiďování přímé a binární
- výběr
- výměna - bubblesort a jeho implementace, při níž si pamatuji místo poslední změny, shakesort
- Vlastnosti třídících algoritmů: stabilita
(je nutná, chceme-li algoritmus použít pro třídění podle více kritérií),
přirozenost (je vhodný pro skoro setříděná pole)
- Datová struktura heap(halda), operace extract-min a insert (v čase log(n))
- Reprezentace haldy v poli
- procedura Sift(L,R:index), která přidává k haldě A[L+1]..A[R] prvek A[L]
- třídící algoritmus heapsort se složitostí n*log(n)
- Příklady z přednášky
zpět na začátek
- přednáška 26.února
- Idea algoritmu quicksortu.
- Použití pivotu z tříděného pole jako zarážky.
- Časová a paměťová složitost qiucksortu.
- Optimalizace quicksortu - odstranění rekurse, volba pivota, netřídění příliš krátkých úseků, detekce nepříznivých případů.
- Nerekursivní realizace quicksortu - program.
- Nerekursivní implementace quicksortu naprogramovaná strukturovaně s realizací některých optimalizací.
- Klasifikace algoritmů vnitřního třídění jako realizace ideje "rozděl a panuj":
analýza - rekurse - syntéza (vyváženost/nevyváženost , důraz na konkrétní fázi).
zpět na začátek
- přednáška 5.března
- Úloha vnějšího třídění.
Počet přístupu do souboru jako operace určující složitost.
- Základní schéma algoritmů vnějšího třídění.
Pojem běhu jako nejdelší monotonní části části souboru.
Rozdělování a slévání běhů.
- Datový typ stream jako příklad implementace souboru, ve kterém známe první prvek.
Implementace algoritmu přímého slévání pomocí typu stream.
Program
- Různá vylepšení základního schématu - rozdělování přímo při slévání, použití více pásek.
- Polyfázové třídění jako příklad efektivního využití více pásek.
Výpočet optimálního rozdělení počtu běhů pro daný počet pásek.
- Předtřídění souboru před vlastním algoritmem vnějšího třídění, aby se zmenšil počet běhů.
Prosévaní souboru přes heap v paměti - program.
- Důkaz tvrzení, že neexistuje žádný (asociativní) algoritmus vnitřního třídění,
který by měl asymptotickou složitost v nejhorším případě lepší než n*log(n).
zpět na začátek
- přednáška 12.března
- Opakování důkazu tvrzení, že neexistuje žádný (asociativní) algoritmus vnitřního třídění,
který by měl asymptotickou složitost v nejhorším případě lepší než n*log(n).
- Důkaz obdobného tvrzení pro průměrný případ.
Pro minimální případ obdobné tvrzení neplatí.
- Statická a dynamická alokace paměti.
Statická a dynamická (ta v Pascalu nejsou) pole.
- Implementace seznamu jako pole - výhody a nevýhody
- Typ ukazatel, doménový typ, příkaz new, konstanta nil.
- Jednosměrný spojový lineární seznam ukončený nilem
a jednoduché opreace s ním
- Vytvoření seznamu (od posledního nebo od prvního prvku)
- Vložení prvku do seznamu za jeho zadaný prvek
- Vložení prvku do seznamu před jeho zadaný prvek
- Vypuštění následujícího prvku
- Průchod seznamem
- Hledánní prvku s danou vlastností
- Možnost "přetržení seznamu" - ztráta přístupu
k dynamicky alokovaným proměnným (t.zv. "smetí" v paměti).
- Jiné "modely" seznamů.
Např. cyklický seznam, seznam s hlavou, dvojsměrný seznam.
- Na rozmyšlení:
Vytvořte procedury provádějící jednoduché akce s jednotlivými typy seznamů.
zpět na začátek
- přednáška 19.března
- Přímý přístup k datovým souborům.
- Lze (střídavě) číst i psát bez ohledu na to, zda byl soubor otevřen pomocí
reset nebo rewrite (ten pochopitelně minulý obsah souboru smaže).
- Standardní podprogramy seek, filepos, filesize, truncate.
- Příkazy read a write.
- Zavírání souboru - close.
- Přímý přístup je podstatně pomalejší než sekvenční,
pokud bychom měli číst procházet (skoro) celý soubor.
K čemu přímý přístup je.
- Příkaz dispose.
- Algoritmus vyhledávání v uspořádaném seznamu -Program.
- Samoorganizující se seznamy
( např. nalezený prvek se stěhuje na první místo, nový prvek je vkládán na začátek).
- Na rozmyšlení: obracení lineárního seznamu.
- Řídké polynomy - implementace jako kruhový uspořádaný spojový seznam členů
s hlavou odpovídající exponentu -1 - výhody této implementace.
- Pool volné paměti a realizace příkazů new a dipose "ve vlastní režiji"
(nepoužívám dispose na jednotlivé členy polynomů, ale vracím celé nepotřebné polynomy
do poolu volné paměti - jde to v konstatním čase).
- Podprogram pro sčítání řídkých polynomů.
-
- Práce pascalského run-timu s pamětí.
Zásobník a halda (heaptop a seznam volných úseků v haldě - realizace procedur new a dispose).
- Možnosti uvolňování paměti:
- Automaticky - garbage collector. V Pascalu není, je např. v Javě.
- Svépomocí - viz výše u příkladu s řídkými polynomy (výhody a nevýhody).
- V Pascalu standarní new a dipose.
- Historický relikt mark a release - nepoužívejte.
- Prostředky nízké úrovně getmem a freemem - bude později.
zpět na začátek
- přednáška 26.března
- Stromy - základní terminologie.
- Příklady datové reprezentace stromů.
- Strom v poli.
- Reprezentace stromu jako spojové struktury, kanonická repezentace
"obecného lesa" pomoci binárního stromu.
- Průchody binárního stromu do hloubky: preorder, inorder, postorder,
jejich rekursivní implementace a souvislost a aritmetickými notacemi.
- Zobrazení stromu pomocí indentace a jeho rekursivní implementace.
- Binární vyhledávací stromy.
- Algoritmy vyhledávání, vkládání a vypouštění prvku z daným klíčem pro binární vyhledávací stromy.
zpět na začátek
- přednáška 2.dubna
- Vkládání prvku do kořene binárního vyhledávacího stromu.
- Implementace ve "standarních" deklaracích.
- Implemenace v deklaracích s polem synů, ve které jde vytvořit
podprogram s parametrem určujícím směr vkládání.
Program.
- Větvený rekord, syntaxe, použití, přítomnost resp. nepřítomnost rozlišovaví položky.
- Procedurální a funkcionální typy, proměnné, parametry.
Omezení pro práci s procedurálními a fukcionálními typy (jen vzdálené adresování,
pouze podprogramy, které nejsou standardní a nejsou lokální uvnitř jiného podprogramu).
Volání a adresa.
zpět na začátek
- přednáška 9.dubna
- Dokonale vybalancované stromy. Algoritmus postavení takového stromu
z N prvních prvků rostoucí posloupnosti na vstupu a jeho rekursivní implementace.
- Odstraňování rekurse.
- Stručný přehled vývoje programovacích jazyků
- Strojový kód, assembler, symbolické adresy
- Nestrukturované programovací jazyky
- Strukturované programování: strukturované řídící příkazy, datové struktury, role podprogramů
- Modulární programování: separátní komplilace modulů, přístupová práva,
abstraktní datové typy - přístup k datům jem přes metody
- Objektové programování a jeho význam
- Objektové programování.
zpět na začátek
- přednáška 16.dubna
- Objektové programování -
Opakování a analýza příkladu
- Podtřída a nadtřída
Podtřída může přidat nové datové atributy a metody a předefinovat metody nadtřídy
- Ochrana atributů - klíčová slova private a public
- Funkce typeof
- Předefinování ukazatele na nadtřídu na ukazatel na podtřídu
- Implicitní parametr self
- Konstruktor a destruktor
Role v objektovém programování a v jeho implementaci v Pascalu
- Potřeba napsat neprázdný konstruktor pokud si objekt "sám" alokuje dynamickou paměť - jako třida head v příkladu
- Abstraktní třídy (a chyba 211)
- Odkaz inherited na (bezprostřední) nadtřídu
- 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
- Časná (při překladu) a pozdní (při běhu) vazba metod.
- Tabulka virtuálních metod a role konstruktoru.
- Motivační příklady pro polymorfismus
zpět na začátek
- přednáška 23.dubna
- Objektové programování - dokončení
- Optimální algoritmy pro hledání prvního a druhého
- Prvních n z posloupnosti délky n*n v čase n*n
- Lineární (v n) algoritmus pro hledání k-tého prvku z n prvků
- Hašování, kolize a metody jejich odstraňování,
metoda řetízků, vkládání, vyhledávání a vypouštění z hašovací tabulky.
efektivita hašování.
zpět na začátek
- přednáška 30.dubna
- Metoda rozděl a panuj
- Dynamické programování
- optimální uzávorkování součinu n matic
- minimální triangulace
- optimální vyhledávací strom
- AVL stromy
Definice, Fibonacciovy stromy jako nejhorší případ AVL stromů, rotace,
algoritmy vkládání (stačí jedna rotace) a vypouštění (je jich případně potřeba víc),
způsob naprogramování s výstupním parametrem udávajícím zda se změnila výška stromu
- "Open array parameters" - možnost jak v Pascalu vytvořit podprogram
pracující s poli libovolného rozměru
- Možnost práce s "dymanickým polem" v Borland Pascalu pomocí getmem a přetypování
zpět na začátek
- přednáška 21.května od 10:40
- Reprezentace aritmetických výrazů pomocí stromu
a aritmetických notací (inorder, preorder a postoreder).
- Algorimy pro vyčíslení hodnoty výrazu.
- Převody mezi jednotlivýmireprezentacemi výrazu
- Algoritmus topologického třídění grafu
- Zobrazení čísel "typu integer" - doplňkový kód.
- Zobrazení čísel "typu real". Důsledky pro programování, příklady výpočtů výrazů, u nichž můe
při mechanickém přepisu do programovacího jazyka dojít ke zbytečným chybám.
zpět na začátek
- přednáška 21.května od 12.10
- Reprezentace grafu, Floydův algoritmus nalezení nejkratších cest v ohodnoceném grafu.
- Diskuse nad požadfavky ke zkoušce.
- Zadání problému obdobného k problémům zadávaným v druhé části písemné práce u zkoušky.
- Algoritmus minimaxu - Shanonova věta o existenci neprohrávající strategie pro
anagonistickou hru dvou hráčů s úplnou informací a nulovým součtem. Použití algoritmu minimaxu
k programování her - statická ohodnocovací funkce.
zpět na začátek
Zpět PRM001