Zpět PRM045

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

Hromadná konzultace v pondělí 28.května 9:00-10:30 v posluchárně S7
  1. přednáška 21.února
  2. přednáška 28.února
  3. přednáška 6.března
  4. přednáška 13.března
  5. přednáška 20.března
  6. přednáška 27.března
  7. přednáška 3.dubna
  8. přednáška10.dubna
  9. přednáška 17.dubna
  10. přednáška 24.dubna
  11. přednáška 15.května
  12. přednáška 22.května
  1. přednáška 21.ú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í
      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í
    2. Zpět začátek
  2. přednáška 28.února
    • Opakování principu algoritmů vnějšího třídě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
      • 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ů
    • 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é
    • 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
    3. Zpět začátek
  3. přednáška 6.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.
    • 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
    • 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
    • Podprogram pro otáčení seznamu s hlavou
      rozmyslete si kolik proměnných potřebujete
    • 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.
    4. Zpět začátek
  4. přednáška 13.března 12:20
    • Ří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
    • Implementace fronty a zásobníku pomocí pole a spojových seznamů
    • 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
    • Stromy - terminologie
    • Různá data se stromovou strukturou, různé datové reprezentace stromu
    5. Zpět začátek
  5. přednáška 20.března
    • 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
    • postavení stromu z aritmetické notace
    • 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 27.března
    • 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
    • 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
    • Hašování jakožto alternativa k (vyváženým) stromům - úvod ještě se k tomu vrátíme
    7. Zpět začátek
  7. přednáška 3.dubna
    8. Zpět začátek
  8. přednáška 10.dubna
    9. Zpět začátek
  9. přednáška 17.dubna
    Na přednášce pravděpodobně bude
    • Myšlenka důkazu tvrzení, že neexistuje žádný algoritmus vnitřního třídění, kterému by v průměrném případě stačilo méně než n*log(n) porovnání
    • jednoduchý lineární algoritmus pro nalezení prvních n prvků z n2 prvků
    • 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í.
    • Vývoj programování
      • 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)
    • 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.
    10. Zpět začátek
  10. přednáška 28.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
    • 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
    • ukázkové příklady na polytmorfismus s hierarchií tříd zvíře, pes a kočka
      k příkladům se vrátíme
    • Polymorfismus, virtuální metody, VMT tabulka, role konstruktoru
    • funkce typeof a její použití
    11. Zpět začátek
  11. přednáška 15.května
    • Odstraňování rekurze pomocí zásobníku
    • 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
    • Negamaxová modifikace algoritmu minimaxu
    • Když popisujeme hru vždy z pohledu hráče na tahu, vede to k jednodušším formulacím tvrzení i algoritmů .
    • 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
    • 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
    12. Zpět začátek
  12. přednáška 22.května
    Pravděpodobný obsah přednášky
    • Ještě k programování her typu šachů. Program, který má hrát celou partii má tři fáze:
      1. zahájení řeší se knihovnou
      2. střední hra - měli jsme podrobně minulou přednášku, pracujeme se stromem hry ikdyž to ve skutečnosti strom není (více cest do téže pozice)
      3. 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
    • Procedurální a funkcionální parametry, přepinač F, procedura pro hledání kořene rovnice f(x)=0 metodou půlení intervalu
    • topologické uspořádání grafů - algoritmus animace
    • minimální kostra grafu,
      faktorová množina
    • B- stromy
      nalezení prvku, vložení prvku, vypuštění prvku
    • O zkouškách
    • ukázková zadání příkladů k první části zkouškové písemky
    • Inventura zkouškových požadavků
    13. Zpět začátek
Hromadná konzultace v pondělí 28.května 9:00-10:30 v posluchárně S7
Zpět PRM045