Zpět PRM045

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

Hromadná konzultace pátek 23.května 16:00 posluchárna S4

  1. přednáška 20.února
  2. přednáška 27.února
  3. přednáška 5.března
  4. přednáška 12.března
    5. 19.března - pro moji nemoc byla algebra
  5. přednáška 26.března
  6. přednáška 2.dubna
  7. přednáška 9.dubna
  8. přednáška 9.dubna v 10:40 místo algebry
  9. přednáška 16.dubna
  10. přednáška 23.dubna
  11. přednáška 30.dubna
  12. přednáška 30.dubna v 10:40 místo algebry
    13. 7.května - bude místo přednášky algebra
    14.května -rektorský den
  13. přednáška 21.května
  1. přednáška 20.února
    • Komentář k praktickým testům a udílení zápočtů
    • Náplň letního semestru, zkouška
    • Vnitřní a vnější třídění rozdíly
    • 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)
    • Opakování jednoduchých algoritmů složitosti O(n2):
      • přímé zatřiďování
      • třídění výběrem
      • třídění výměnami - bubblesort, shakesort
    • 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
    • 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
      • Programy - vytiskněte si na příští přednášku spolu se souborem obsahujícím nerekursivní verzi algoritmu Quicksort
    2. Zpět začátek
  2. přednáška 27.února
    • Opakování důkazu, ž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
    • 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 a nerekursivní verze
      rozmyslet: který ze dvou úseků se má dát na zásobník "níže" a proč ?
    • Optimalizace quicksortu, různá jeho vylepšení,
    • Porovnání quicksortu s heapsortem
    • Statická alokace paměti (dosud jiná nebyla) pro proměnné v Pascalu
      provádí se "na zásobníku" - vzniká při zpracování deklarací bloku, zaniká "automaticky" při ukončení bloku,
    • 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. 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.
    • Možnost vzniku "smetí v paměti" ztratíme-li možnost přístupu k dynamicky alokované proměnné
    3. Zpět začátek
  3. přednáška 5.března
    • Povídání o termínech praktických testů v semestru - pravidla
    • Opakování: 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.
    • 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
    • Animace práce se spojovými seznamy
      1. spojový seznam
      2. přidání prvku na začátek spojového seznamu
      3. odebrání prvku ze začátku spojového seznamu
      4. průchod spojovým seznamem
      5. přidání prvku na konec spojového seznamu
        pozor, nepracuje, je-li seznam prázdný
      6. odebrání prvku z konce spojového seznamu
    • 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
    • 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
      Zkuste si naprogramovat jednoduché akce s nimi
    • Na rozmyšlenou:
      Vytvořte podprogram pro otáčení seznamu s hlavou
      rozmyslete si kolik proměnných potřebujete
    4. Zpět začátek
    -->
  4. přednáška 12.března
    • opakování dynamicky alokované proměnné, ukazatele, procedury new a dispose
    • 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.
    • 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 reprezentavci řídké matice
    • 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
    • Vytiskněte si napříště programy týkající se vnějšího třídění
    5. Zpět začátek
  5. přednáška 26.března
    • 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í
    • 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ů
    6. Zpět začátek
  6. přednáška 2.dubna
    Pravděpodobný obsah přednášky
    • 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ů
    • 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
    • rozmyslet- připravit si dotazy
      ne všechno jsme vysvětlili "do konce" - příště se k ní vrátíme podrobněji
    • stáhněte si a vytiskněte:
      1. Unita obsahující objektovou implementaci dvojsměrných lineárních seznamů s hlavou
      2. ukázkové příklady na polytmorfismus s hierarchií tříd zvíře, pes a kočka
    Zpět začátek
  7. přednáška 9.dubna
  8. přednáška 9.dubna
    • O praktických testech. O zkoušce
    • Objektové programování - opakování.
    • 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:
      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
      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 a kočka
      rozmyslet, vyzkoušet, připravit si dotazy
    • VMT tabulky a role konstruktoru
    • Funkce typeof
    • Porovnání použití záznamu s variantami a
      a popisu téhož pomocí dědičnosti (návrh hierarchie tříd)
    • 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
    • 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
        Algoritmus řešení problému batohu - 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ěří)
    • 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).
    9. Zpět začátek
  9. přednáška 16.dubna
    • O praktických testech. O zkoušce.
    • Dynamické programování - opakování
    • Hledání maximálního podřetězce - trasování
    • Optimální rozložení písmen na klávesnici mobilu
    • Floyd-Warshallův algoritmus pro nalezení nejkratších cest v orientovaném grafu
    • Příklady dalších úloh, které lze efektivně řešit pomocí dynamického programování (budou probrány na cvičeních)
      • Hledání nejkratší triangulace - viz. např. kniha P. Töpfera
    • Stromy, binární stromy - terminologie
    • Různá data se stromovou strukturou, různé datové reprezentace stromu
    • Kanonická reprezentace lesa pomocí binárního stromu
    • Pojem binárního vyhledávacího stromu
    • Algoritmus vyhledávání v binárním vyhledávacím stromě
    • Binární vyhledávací stromy - vkládání prvku do binárního vyhledávacího stromu
    • myšlenka vypuštění prvku s daným klíčem
    • Animace operací s binárními vyhledávacími stromy
    10. Zpět začátek
  10. přednáška 23.dubna
    • Opakování - binární vyhledávací stromy a operace na nich
      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. Zkuste naprogramovat i nerekurzivně.
    • 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
    • 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
    • animace operací s AVL stromy
      1. vkládání do AVL stromu
      2. rotace při vkládání do AVL stromu
      3. vypouštění z AVL stromu
      4. rotace při vypouštění z AVL stromu
    • Hašování
      bezkolizní hašování, kolize a různé metody jejich řešení, metoda řetízků, efektivita hašování
    11. Zpět začátek
  11. přednáška 30.dubna
  12. přednáška 30.dubna 10:40
    • Předběžná verze požadavků ke zkoušce - prohlédněte si, abyste příšte mohli mít dotazy
    • ukázková zadání příkladů k první části zkouškové písemky
    • 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
    • Kaskádní varianta s použitím okénka
    • AVL stromy - opakování, podprogramy pro vkládání/vypouštění z AVl stromu by měly mít výstupní parametr pomocí kterého vrátí volajícímu informaci, zda se výška stromu provedenou akcí zvýšila/snížila
    • animace operací s AVL stromy
      1. vkládání do AVL stromu
      2. rotace při vkládání do AVL stromu
      3. vypouštění z AVL stromu
      4. rotace při vypouštění z AVL stromu
    • Rozdíl mezi datovými strukturami pole a record není jen v tom, ž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ž hodnota nemusí (a zpravidla není) známa v době 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".
    • 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
    • Příklad objektové hierarchie pro práci s geometrickými útvary
      zdroják
    • Funkcionální a procedurální parametry, Funkcionální a procedurální typy, dlouhé adresy a přepinač F.
    • Podprogram pro hledání kořene rovnice F(x)=0 metodou půlení intervalu s funkcionálním parametrem F
    13. Zpět začátek
  13. přednáška 21.května
    • Vizualizace (binárního) stromu pomocí indentace - jednoduchá rekursivní procedura
    • vybrané grafové algoritmy
      • topologické uspořádání grafů - algoritmus animace
      • Dijkstrův algoritmus pro hledání nejkratších cest z daného vrcholu - animace
      • hledání nejlacinější kostry
      • hledání komponent souvislosti- animace
      • faktorová množnina - animace
    • O zkouškách
    • Odsouhlasení požadavků ke zkoušce
    • Pozvání na výběrovou přednášku
      Programování III pro neinformatiky - neprocedurální programování
      od příštího školního roku bude v zimním semestru
Zpět PRM045