Zpět PRG030

PRG030 - Co bylo na přednášce - paralelka Z

1. přednáška   29.září
2. přednáška   6.října
3. přednáška   13.října
4. přednáška   20.října
5. přednáška   27.října
6. přednáška   3.listopadu
7. přednáška   10.listopadu
8. přednáška   24.listopadu
9. přednáška   1.prosince
10. přednáška   8.prosince
11. přednáška   15.prosince
12. přednáška   5.ledna

1. přednáška 29.září
   
   • prezence
   • Náplň a cíle předmětu, podmínky k zápočtu a zkoušce, praktický test v zimním semestru.
   • Jak a proč se stát/nestát matfyzákem, jak a proč se stát/nestát programátorem.
   • Pojem algoritmu a příklady konkrétních algoritmů (aritmetické operace se zápisy čísel v poziční soustavě, Eukleidův algoritmus, Erathosthenovo síto, ....).
   • Správnost algoritmu, konečnost, parciální správnost.
   • Algoritmus průchodu bludištěm s pamatováním si přímé cesty zpět a důkaz jeho konečnosti.
   • Úlohy k rozmyšlení :
     • Důkaz parciální správnosti algoritmu průchodu bludištěm
     • Nalezení stabilního párování
     • Synchronizace konečných automatů (generál a vojáci)
   zpět na začátek

   ---

2. přednáška 6.října
   • Důkaz parciální správnosti algoritmu průchodu bludištěm.
   • Pojem invariantu.
   • Algoritmus pro nalezení stabilního párování, důkaz, že "pánská volenka" vytvoří stabilní párování "optimální pro muže"
   • Časová složitost algoritmu. Asymptotická složitost. Nejhorší, nejlepší a průměrný případ. Proč má "teoretická" asymptotická složitost praktický význam.
   • Proměnná, identifikátor, mnemotechnické identifikátoty, deklarace proměnných, přiřazovací příkaz, klíčová slova.
   • Hledání maximálního jedničkového obdélníku v nula/jedničkovém obdélníku rozměru m x n
     ( triviální algoritmus složitosti O(m³*n³), algorimy s předvýpočtem složitosti O(m*n²) resp. O(m*n) )
   • Strukturované příkazy: podmíněný příkaz úplný ( if B then S1 else S2 ) a neúplný ( if B then S ) , složený příkaz ( begin S1; S2; .... Sn end ), cykly s testem před ( while B do S ) resp. po ( repeat S1; S2; .... Sn until B ) provedení těla cyklu .
   • Ukázka tvaru pascalského programu
   • Velká a malá čísla v reálném světě. Růst exponenciely.
   zpět na začátek

   ---

3. přednáška 13.října
   • Syntaktické diagramy jako prostředek pro popis syntaxe jazyka.
   • Odstranění nejednoznačnosti konstrukce
     if P then if Q then S1 else S2
   • Čísla typu integer. Maxint, synaxe zápisu konstant, operace a standardní fukce. Příklad neasociativity sčítání integerů.
     Celočíselné typy v Borland Pascalu : integer, shortint, longint, byte, word.
   • Typ real : operace, standardní funkce, funkce trunc a round, zaokrouhlovací chyby.
     Demostrační příklad na zaokrouhlovací chyby.
   • Zásady pro vyčíslování výrazů.
   • Konstanty a jejich role pro modifikovatelnost programu
   • Typ boolean.
   • Program, který testuje, zda číslo na vstupu je prvočíslo.
   • Typ char, funkce ord a chr.
   • Zápis čísla v poziční soustavě, výpočet jeho hodnoty Hornerovým schématem
   • Příklad programu, který čte ze vstupu řádky obsahující vždy číslo k udávající základ soustavy a zápis nějakého čísla X v této soustavě a spočítá a vytiskne hodnotu čísla X
   • Výčtové typy
   • "Zoologie" typů v Pascalu (jednoduché - strukturované, standardní - definované programátorem, ordinální).
   zpět na začátek

   ---

4. přednáška 20.října
   • Typ interval. Hostitelský typ, běhové kontroly a možnost je vypínat (a proč to není žádoucí).
   • Funkce ord pro ordinální typy - succ, prev, inc, dec.
   • Jednoprůchodovost překladače Pascalu a z toho vyplývající požadavek, aby každý identifikátor byl v (textu) programu definován před tím než je použit.
   • Pole, indexový typ, typ složky, přístup ke složce pole pomocí indexového výrazu.
   • for cyklus jeho syntaxe a sématnika.
   • Vícerozměrná pole.
   • Znakové řetězce (stringy).
   • Kvadratický algoritmus pro nalezení délky nejdelší rostoucí vybrané posloupnosti (dokáže nalézt i tuto posloupnost) (program).
     Problém na rozmyšlení: nalézt (asymptoticky) rychlejší program pro nalezení délky nejdelší rostoucí vybrané posloupnosti (třeba za cenu toho, že samu posloupnost nenajde).
   • Příklady funkcí (nsd, faktoriál,...).
   • Výpočet kombinačních čísel s prevencí přetečení.
   • Efektivní výpočet N-té mocniny pomocí 2*log₂(N) násobení
   • Instruktivní příklad na vyčíslení složitější mocninné řady (nepočítat každý člen vždy znovu, inkrementální výpočet dalšího členu z minulého, předpočítání nezávislých faktorů)
   • (Podmíněný) příkaz case
   • "Reálné" typu v Borlnand Pascalu - real, single, double.
   • Reprezentace celých čísel v paměti, doplňkový kód (převedení odčítání na sčítání)
   zpět na začátek

   ---

5. přednáška 27.října
   • Typ záznam (record) a příkaz with.
     Typická reprezentace vektoru jako záznamu o dvou složkách: pole a jeho skutečně využitá délka.
   • Hledání prvku v tabulce: první výskyt, použití zarážky pro urychlení testu, prostřední výskyt.
   • Hledání prvku v uspořádané tabulce, metoda půlení intervalu.
   • Unity utab a seektab realizující probírané algoritmy vyhledávání v tabulce
   • Úplné a neúplné vyhodnocování booleovských výrazů.
   • Přepinače ovlivňujicí činnost překladače Pascalu
   • Podprogramy a jejich význam pro programování. Návrh programu metodou "shora dolů".
   • Procedury.
   • Předávání parametrů hodnotou a referencí. Jednoduchý příklad.
   • Lokální versus globální deklarace a jim odpovídající objekty.
   • Alokace lokálních objektů (parametrů a lokálních proměnných) na zásobníku.
   • Příklad "neintuitivního" chování podprogramu, který byl zavolán se stejným skutečným parametrem pro dva různé formální parametry předávané referencí.
   • Kdy použít předávání parametrů hodnotou resp. referencí
   zpět na začátek

   ---

6. přednáška 3.listopadu
   
   • Vstup a výstup, abstrakce souboru, textové a datové soubory.
   • Procedura assign
   • Otevíraní textových souborů pro čtení (reset), zápis (rewrite) a přípis(append), zavírání souboru.
   • Přehled prostředků pro vstup z textového souboru: read, readln, eof, eoln.
     Vstup čísel ze souboru, funkce seekeof, seekeoln.
     Vstup řetězců.
   • Přehled prostředků pro výstup do textového souboru: write, writeln.
     Formátovaný výstup.
   • Reprezentace celých čísel v doplňkovém kódu (opakování a dementi). Princip, specifické vlastnosti dvojkové (resp. šestnátkové) soustavy.
   • Rekursivní podprogramy. Faktoriál rekursivně a iterativně.
   • Doslovný přepis definice Fibonacciovy posloupnosti vede k algoritmu exponenciální složitosti.
   • Rekursivní procedura, která využívá implicitního zásobníku volání podprogramů k otáčení vstupního řetězce.
   • Úloha o osmi dámách - program.
     Rekursivní implementace algoritmu backtrackingu. Návrh datové struktury, která jde inkrementálně aktualizovat.
   • Úloha k rozmyšlení :
     • Program pro nalezení maximálního počtu vzájemně se neohrožujících figur na šachovnici daného rozměru pro různé konkrétní (exo)figury, totéž pro figuru, jejíž tahy se přečtou z dat.
   zpět na začátek

   ---

7. přednáška 10.listopadu
   • Algoritmus pro nalezení délky nejdelší rostoucí vybrané posloupnosti mající složitost N*log(N) - program
   • Rekursivni a nerekursivni verze programu pro rozklad čísla na sčítance
   • Vyčíslování hodnoty aritmetického výrazu.
     Metoda rekursivního sestupu - konstrukce rekursivních podprogramů na základě gramatiky definující syntaxi výrazu.
   • Úloha k rozmyšlení :
     • Modifikace procedur pro vyhodnocování aritmetického výrazu tak, abychom nevyužívali vnořených podprogramů.
   • Přímá a nepřímá rekurse. Direktiva forward.
   • Standardní podprogramy pro práci se stringy
   • Programové jednotky - unity. Část interface a část implementation, klausule uses. Bude ještě podrobněji
   • Systémové unity SYSTEM a CRT. Stručná charakteristika jejich role.
   • Typované konstanty (příklad popření přívlastkem) a jejich použití
   • Typ množina, jeho realizace v Borland Pascalu.
   • Velká množina jako pole množin.
   • Sekvenční algoritmus pro nalezení reflexního, symetrického a transitivního uzávěru binární relace ze vstupujícího seznamu jejich dvojic.
     Program a jeho realističtější verze.
   zpět na začátek

   ---

8. přednáška 24.listopadu
   • Informace o praktických testech, zkouškách a pravidlech pro zapisování na ně.
   • Variantní záznam
   • Přetypování
   • Implementace seznamu jako pole - výhody a nevýhody
   • Ukazatele a dynamicky alokované proměnné, new, dispose, 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ání 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).
   • Program vyhledávání v uspořádaném seznamu s přístupem na fiktivní začátek (hlavu) a fiktivní konec (ocas).
   • Jiné "modely" seznamů.
     Např. cyklický seznam, seznam s přístupem na začátek i na konec, seznam s hlavou a/nebo s ocasem, dvojsměrný seznam atp.
   • Na rozmyšlení:
     • Vytvořte procedury provádějící jednoduché akce s jednotlivými typy seznamů.
     • Samoorganizující se seznamy ( např. nalezený prvek se stěhuje na první místo, nový prvek je vkládán na začátek).
     • 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žii" (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ů.
   zpět na začátek

   ---

9. přednáška 1.prosince
   • Funkční gramotnost jako jeden z implicitních předpokladů (nejen) úspěšného zápisu k praktickému testu i ke zkoušce.
   • Řídké matice.
   • Technické úlohy k rozmyšlení :
     • Vytvoření struktury řídké matice ze vstupních dat.
     • Vyřazovování z dvourozměrného skladu
   • Typické implentace zásobníku a fonty v poli a pomocí spojových struktur.
   • 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.
   • Procházení grafu do hloubky a do šířky.
     Společný algoritmus užívající seznamy OPEN a CLOSE
     (je-li OPEN zásobník, dostaneme průchod do hloubky, je-li to fronta, dostaneme průchod šířky).
   • Klasifikace třídících algoritmů
     • vnitřní - třídění polí
       • adresové
       • asociativní
     • 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
     • Shellův algoritmus
   • 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)
   • Heapsort
     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)
   • Quicksort
     myšlenka; rekursivní implementace s pivotem jako zarážkou; složitost v nejlepším a nejhorším případě;
     vylepšení efektivity: volba pivota, odstranění rekurze, dotřídění krátkých úseků jiným algoritmem, detekce nejhoršího případu
   • Metoda návrhu rozděl a panuj: analýza, rekurze, syntéza
     klasifikace algoritmů vnitřního třídění z tohoto zorného úhlu
   • Algoritmus mergesort
   • Zdrojové texty třídících programů
   • Na rozmyšlení:
     Odhad složitosti quicksortu v průměrném případě.
   zpět na začátek

   ---

10. přednáška 8.prosince
    • Mergesort, jeho rekursivní realizace
    • Odstranění rekurze pomocí zásobníku
    • Nerekursivní quicksort
    • Paměťová složitost quicksortu
    • Různé datové reprezentace grafů, umocňování matice sousednosti
    • Hledání nejkratší cesty v grafu. Dijkstrův algoritmus. Prohledávání do šířky a do hloubky s ořezáváním.
    • Dlouhá čísla
    • Stromy: definice, terminologie; binární stromy.
    • Kanonická reprezentace lesa pomocí binárního stromu.
    • Průchody binární stromem do hloubky a souvislost s aritmetickými notacemi
      (preorder - prefixová (polská), inorder - infixová, postorder - postfixová (inverzní polská).
    • Visualizace stromu pomocí indentace
    • Binární vyhledávací stromy a operace na nich: vyhledávání, vkládání prvku s daným klíčem
    zpět na začátek

    ---

11. přednáška 15.prosince
    • Vypouštění prvku z binárního vyhledávacího stromu
    • Vypouštění intervalu z binárního vyhledávacího stromu.
    • Postavení dokonale vybalancovaného binárního vyhledávacího stromu ze začátku (zadané délky) rostoucí posloupnosti
    • Statická a dynamická alokace paměti.
      Statická a dynamická (ta v Pascalu nejsou) pole.
      Použití getmem, freemem a přetypování pro implementaci "dynamických polí".
    • "open array parameters"
    • Dynamické programování. Příklady úloh ( optimální uzávorkování součinu matic, minimální triangulace, problém batohu - příklad trasování ). Princip metody.
    • Aritmetické výrazy - reprezentace pomocí stromu, polská, inverzní a infixová notace. Algoritmy převodů mezi těmito reprezentacemi.
      Algoritmy vyčíslování výrazů.
    • Pseudonáhodná čísla - princip použití, hnízdo generátoru. Metoda Monte Carlo. Pseudonáhodná čísla v Borland Pascalu ( RandSeed, Randomize, Random, Random(n) )
    zpět na začátek

    ---

12. přednáška 5.ledna
    • Komentář k testům a zkouškám
    • Složitost problému.
      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).
    • Konstantní parametry
    • 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.
    • Antagonistická hra s nulovým součtem a úplnou informací. Strom hry. Shannonova věta.
    • Algoritmus minimaxu, negamaxová formulace a implementace.
    • Statická ohodnocovací funkce a architektura šachových programů.
    • Princip afa-beta prořezávání.
    • Pojem heuristiky
    zpět na začátek

    ---

Zpět PRG030