Zpět NMIN102

LS 2013/14
NMIN102 Programování II paralelka Y - středa 12:20 M1
co bylo na přednáškách

  1. přednáška 19.února
  2. přednáška 26.února
  3. přednáška 5.března
  4. přednáška 12.března
  5. přednáška 19.března
  6. přednáška 26.března
  7. přednáška 2.dubna
  8. přednáška 9.dubna
  9. přednáška 16.dubna
  10. přednáška 23.dubna
  11. přednáška 30.dubna
  12. přednáška 7.května
  13. přednáška 21.května
  1. přednáška 19.ú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
    • 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í
    • Opakování principu algoritmu 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ějakou 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
    • 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
    2. Zpět začátek
  2. přednáška 26.února
    • Opakování pojmu asymptotické složitosti
    • Opakování: Vnitřní třídění
      • Jednoduché asociativní algoritmy složitosti O(n2):
        1. přímé zatřiďování
        2. binární zatřiďování - polohu najdeme v logaritmické čase, ale posun pole je lineární
        3. třídění výměnami - bubblesort, shakesort implementace bez pamatování si místa poslední výměny je programátorská nešikovnost
        4. heapsort, třídí na místě, má časovou složitost n*log(n)
    • ideu heapsortu s výhodou použít pro předvýpočet při vnějším třídění:
      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ů
    • zdrojové texty procedur realizujících jednotlivé algoritmy vnitřního třídě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), pro nejlepší případ to pochopitelně neplatí
    • Adresní třídící algoritmy
      • Radixové třídění - adresní třídění, algoritmus jeho realizace na třídících strojích
      • adresní třídění pro malý rozsah čísel - bucketsort
    • opakování optimalizací vnějšího třídění
    • použití více pásek metodou polyfázového třídění:
      • optimální distribuce běhů je dána fibonnaciho čísly vyšších řádů
      • myšlenka, jak to naprogramovat, fiktivní běhy
    3. Zpět začátek
  3. přednáška 5.března
    • 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
    • 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
    • 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
    • Procedura search pro uspořádaný seznam s hlavou a ocasem - vyhledávává resp. vkládá prvek s daným klíčem
    • Rozmyslete si: Podprogram pro otáčení seznamu
      kolik proměnných potřebujete?
    4. Zpět začátek
  4. přednáška 12.března
    • opakování: typ ukazatel, bázový typ, statická a dynamická alokace paměti, procedury new a dispose, ...
    • Otáčení lineárního seznamu
    • 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
    • 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 někdy 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 vhodné - na přednášce teprve bude
    5. Zpět začátek
  5. přednáška 19.března
    • 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
    • Reprezentace aritmetických výrazů pomocí binárních stromů
    • průchody binárním stromem do hloubky - souvislost s aritmetickými notacemi
    • 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
      její naprogramování
    • 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í
    6. Zpět začátek
  6. přednáška 26.března
    • opakování
    • 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ě.
    • 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
    • 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
    • Dokonale vybalancované stromy
    • Hašování jakožto alternativa k (vyváženým) stromům
      bezkolizní hašování, kolize a různé metody jejich řešení, metoda řetízků, efektivita hašování
    • Hledání optimálního uzávorkování součinu N matic jakožto "typická" úloha na dynamické programování
    7. Zpět začátek
  7. přednáška 2.dubna
    • opakování algoritmu, který v čase O(n3) hledá optimální uzávorkování součinu N matic
    • Jednoduché úlohy na dynamické programování:
      • opakování kvadratického algoritmu pro nalezení nejdelší rostoucí vybrané posloupnosti (program)
      • mrkev a petržel
    • Návod pro hledání max společného podřetězce dvou řetězců
    • Hledání maximálního podřetězce - trasování
    • Problém batohu s celočíselným zadáním
      Algoritmus řešení problému batohu - trasování konkrétního výpočtu
      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).
      • minimální triangulace - viz kniha P.Topfera
      • Optimální binární vyhledávací strom k zadaným frekvencím dotazů
    • Floyd-Warshallův algoritmus pro nalezení nejkratších cest v grafu
    • 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
    • zkuste najít jednoduchý algoritmus pro nalezení prvních n prvků z n2 prvků
    8. Zpět začátek
  8. přednáška 9.dubna
    9. Na přednášce pravděpodobně bude - vše asi nestihneme
    Zpět začátek
  9. přednáška 16.dubna
    • 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í.
    • 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)
    • Motivační příklad pro zavedení 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:
      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, ...
      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
    10. Zpět začátek
  10. přednáška 23.dubna
    • 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:
      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).
    • 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í,
    • ukázkové příklady na polytmorfismus s hierarchií tříd zvíře, pes a kočka
    • Polymorfismus, virtuální metody, VMT tabulka, role konstruktoru
    • funkce typeof a její použití
    11. Zpět začátek
  11. přednáška 30.dubna
    Na přednášce pravděpodobně bude
    12. Zpět začátek
  12. přednáška 7.května
    • O zkouškách
    • ukázková zadání příkladů k první části zkouškové písemky
    • Inventura zkouškových požadavků
    • Procedurální a funkcionální typy a parametry, přepinač F, procedura pro hledání kořene rovnice f(x)=0 metodou půlení intervalu
    • Přepinače kompilátoru
    • topologické uspořádání grafů - algoritmus animace
    • Opakování
      vyčíslování hodnoty aritmetického výrazu z inorder notace
      • metoda shora dolů - nalezení "nejvnějšnějšího" operátoru a rekursivní volání - klikátko
      • metoda zdola nahoru - postupné vyčíslování toho, co jde "hned vyčíslit"
      • převod na postfix klikátko
    • reprezentace výrazů pomocí gramatiky, algoritmus vyčíslování infixivého výrazu bez znamének, ale s prioritami - pomocí metody rekursivního sestupu - klikátko
      obdobným způsobem pracují většinou překladače
    • technické cvičení - modifikujte řešení, které bylo na přednášce tak, nepoužívalo lokální podprogramy
    • Definice vyhraných a prohraných pozic, jejich hledání v případě jednoduchých konkrétních her
    13. Zpět začátek
  13. přednáška 21.května
    Dodělávky a témata na přání studentů
    • B- stromy
      nalezení prvku, vložení prvku, vypuštění prvku
    • minimální kostra grafu,
      faktorová množina
    • Odstraňování rekurze pomocí zásobníku
    • Opakování objektového programování
    • ukázkové příklady na polytmorfismus s hierarchií tříd zvíře, pes a kočka
    • Polymorfismus, virtuální metody, VMT tabulka, role konstruktoru
    • Porovnání použití záznamu s variantami a popisu téhož pomocí dědičnosti (návrh hierarchie tříd)
    • Porovnání použití záznamu s variantami a a popisu téhož pomocí dědičnosti (návrh hierarchie tříd)
    • Rekursivní implementace vkládání do kořene binárního vyhledávacího stromu
    • Technické výhody alternativní implementace binárního stromu s polem synů - mohu předat směr jako parametr
    • standardní unity Pascalu
    • unita CRT
    14. Zpět začátek
Zpět NMIN102