Zpět PRM044

PRM044 Programování I paralelka Y

Co bylo na přednáškách

paralelka Y - středa 12:20 K1

  1. přednáška 5.října
    2. přednáška 12.října odpadá - imatrikulace
  2. přednáška 19.října
  3. přednáška 26.října
  4. přednáška 2.listopadu
  5. přednáška 9.listopadu
  6. přednáška 16.listopadu
  7. přednáška 23.listopadu
  8. přednáška 30.listopadu
  9. přednáška 7.prosince
  10. přednáška 14.prosince
  11. přednáška 21.prosince
  12. přednáška 4.ledna
  13. přednáška 11.ledna
  1. přednáška 5.října
    • Úvodní povídání o předmětu a studiu na MFF UK.
    • Podmínky k zápočtu, praktický test, zkouška v letním semestru, literatura k přednášce
    • Pojem algoritmu, "filosofické vymezení", příklady konkrétních algoritmů:
      Eukleidův algoritmus, Erathostenovo síto (úpravy jeho efektivity), konstrukce magického čtverce lichého řádu.
    • Úloha o bludišti a jednoduchý "Ariadnin" algoritmus, který ji řeší.
    • Úlohy na rozmyšlení:
      1. Nalézt algoritmus pro nalezení stabilního párování
      2. Zkusit dokázat správnost "Ariadnina" algoritmu
    • Prezence
    Zpět začátek
  2. přednáška 19.října
    • Úloha o bludišti, poznámky k formulaci algoritmu, důkaz jeho správnosti .
    • Konečnost a parciální správnost algoritmu.
    • Pojem invariantu algoritmu
    • Problém stabilního párování a jeho řešení algoritmem pánské volenky.
      Důkaz toho, že pánská volenka vytvoří stabilní párování, které je mezi všemi stabilními párováními "optimální pro muže".
    • Měření časové složitosti algoritmu, asymptotická složitost - formální definice pomocí O(f).
    • Nejlepší, nejhorší a průměrný případ
    • Paradoxní aspekty pojmu asymptotické složitosti.
    3. Zpět začátek
  3. přednáška 26.října
    • Příklad na hledání maximálního jedničkového obdélníku v 0/1 obdélníku rozměrů m x n.
      • Trivální algoritmus složitosti n3*m3
      • Algoritmus se složitostí n*m2 využívající předvýpočet "počtu jedniček pod danou jedničkou"
      • Algoritmus pracující v čase n*m
    • Motivační příklad pro zavedení konstrukcí obvyklých v programovacích jazycích.
    • Proměnná - jméno místa pro uložení hodnoty, nikoli hodnoty samé. Přiřazovací příkaz. Příkazy pro čtení (read) a výstup (write).
    • Datový typ, deklarace proměnných.
    • Identifikátor, zápis číselné konstanty, klíčové slovo.
    • Složené příkazy. Úplný a neúplný podmíněný příkaz, složený příkaz, cykly while a repeat. Syntaktická nejednoznačnost konstrukce podmíněného příkazu.
    • Tvar programu v Pascalu
    • Čísla v reálném světě, v matematice a v počítači. Rychlost růstu exponenciely.
    • Typ integer. Maxint, přetečení hodnoty.
    4. Zpět začátek
  4. přednáška 2.listopadu
    • Typ real, standardní funkce, zaokrouhlovací chyby.
    • Ukázkový program, demonstrující, že není rozumné používat pro kontrolu běhu výpočtu programu výsledek testu reálný čísel na rovnost.
    • Typová ochrana přiřazovacího příkazu. Funkce trunc a round.
    • Konstanty jako nástroj pro snadnou modifikaci programů. Ukázkové programy.
    • Typ boolean.
    • Program, který testuje, zda číslo na vstupu je prvočíslo.
    • Funkce s parametry předávanými hodnotou, jednoduché příklady, nsd
    • Funkce demonstující některé zásady pro vyhodnocování výrazů
    • for cyklus, jeho syntaxe a sématnika, jednoduché příklady.
    5. Zpět začátek
  5. přednáška 9.listopadu
    • Překladače pascalu
    • 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í).
    • 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.
    • Vícerozměrné pole.
    • Na rozmyšlenou:
      • n-tá mocnina na co nejméně násobení
      • efektivní výpočet kombinačního čísla "N nad K"
    6. Zpět začátek
  6. přednáška 16.listopadu
    • Stringy
    • Celočíselné typy v Borland Pascalu (integer, longint, shortint, byte, word).
    • "Reálné" typy v Borlnand Pascalu - real, single, double.
    • Výpočet kombinačních čísel s prevencí přetečení.
    • Efektivní "hardwarový" výpočet N-té mocniny pomocí umocňování na druhou, kterému stačí 2*log2 (n) násobení
    • 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ů).
      Programová realizace bude.
    • Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti (program).
    • Datové a textové soubory - rozdíl v použití.
    • Textové soubory v Pascalu,
    • Procedura assign
    • Otevření textového souboru ke čtení, k zápisu a přípisu. Zavírání textového souboru.
    7. Zpět začátek
  7. přednáška 23.listopadu
    • Textové soubory v Pascalu - abstraktní model a konkrétní reprezentace.
    • Realizace výstupů pomocí bufferu, zavírání souboru
    • Všechny procedury mají nepovinný první parametr udávající, ze/do kterého souboru se má číst/psát
      pokud není uveden jde o vstup/výstup z/do souboru input/output
    • Vstup z textového souboru.
      • Testy eof, eoln,
      • Procedura readln,
      • Čtení znaků
      • Čtení čísel
      • čtení stringů (a jeho specifika )
      • Anomální chování programu s testem
        while not eof(F) do
        begin read(F,I); ..... end;
      • Testy seekeof, seekeoln.
    • Výstup do textového souboru
      • Formátování
      • Procedura writeln,
      • výstup znaků,
      • výstup integerů (bez formátu se výsledky mohou "slepit")
      • výstup čísel typu real, zokrouhlování, výstup v semilogaritmickém a "desetinném" tvaru
        ukázkový program a jeho výstup
      • Výstup řetězců
    • Podprogramy a jejich význam pro programování. Návrh programu metodou "shora dolů".
    • Procedury.
    • Předávání parametrů hodnotou a referencí.
    • 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.
    K předávání parametrů se na příští přednášce musíme vrátit, odpřednesené je spíše jen úvodem do problematiky
    Zpět začátek
  8. přednáška 30.listopadu
    • Program, který tiskne Pascalův trojúhelník - ukázka formátovaného výstupu.
    • Opakování - Podprogramy, jejich komunikace s hlavním programem, předávání parametrů.
    • Pro soubory není přiřazovací příkaz, tedy je nelze ani předávat hodnotou
    • 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í
    • Předávání parametrů const
    • 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
        Programové jednotky - unity - budou probrány až na příští přednášce
    • Úplné a neúplné vyhodnocování booleovských výrazů.
    • Přepinače ovlivňujicí činnost překladače Pascalu (speciálně B a R).
    • Příkaz case
    Zpět začátek
  9. přednáška 7.prosince
    • Samostatně překládané programové jednotky - unity. Interfaceová a implementační část, klausule uses.
      Význam používání unit.
    • Znakové řetězce (stringy) a standardní podprogramy pro práci s nimi.
    • Rekursivní podprogramy
    • Faktoriál rekursivní a iterativní rešení
    • Fibonnaciova posloupnost - chybné rešení s exponenciální rešení
      Rozmyslet: Iterativní výpočet a rekursivní procedura s lineární složitostí
    • Hanojské věže
    • Nerekursivní a rekursivní verze programu hledajícího všechny rozklady zadaného čísla na sčítance
    • Výstup otočeného řetězce pomocí rekursivní procedury s lokální promennou.
    • Hledání všech pozic N nezávislých dam na šachovnici N x N - volba datových struktur umožňujícách inkrementální aktualizaci - Program
    10. Zpět začátek
  10. přednáška 14.prosince
    • Přímá a nepřímá rekurse, direktiva forward.
    • Formální definice aritmetického výrazu a z něj odvozené rekursivní procedury pro vyčíslení hodnoty aritmetického výrazu
    • Rozmyslet: Modifikace programu tak, aby nepoužíval podprogramů lokálních v jiném. Jak se musí změnit hlavičky podprogramů a jejich vzájemná komunikace?
    • 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.
    • Pseudonáhodná čísla - princip použití, hnízdo generátoru.
    • Pseudonáhodná čísla v Borland Pascalu ( RandSeed, Randomize, Random, Random(n) )
    Zpět začátek
  11. přednáška 21.prosince
    • Opakování o pseudonáhodných číslech
    • Metoda Monte Carlo.
    • Zásobník, fronta a jejich implementace
    • Různé reprezentace grafu,
      Matice sousednosti, matice incidence, seznam hran, seznam následníků.
    • Prohledávání grafu do hloubky a šířky. Společná implementace se seznamy OPEN a CLOSE, ve které se tyto algoritmy liší jen implementací seznamu OPEN (zásobník/fronta).
    • Hledání nejkratší cesty procházením grafu
    • Dijkstrův algoritmus, invariant a důkaz správnosti
    • Použití mocnění matice sousednosti pro zjišťování hranové vzdálenosti
    • Komponenty souvislosti prohledáváním grafu a faktorová množnina
    • Opakování o unitách,
    • Systémové unity SYSTEM a CRT. Stručná charakteristika jejich role.
    12. Zpět začátek
  12. přednáška 4.ledna
    • Praktické testy, přihlašování, praktické rady pro praktické testy, sbírka úloh
    • Dokumentace zápočtového programu - materiál
    • reprezentace a aritmetika "dlouhých čísel"
    • Typované konstanty (příklad popření přívlastkem) a jejich použití
    • Příkazy ovlivňující běh programu: goto, break, continue, exit,
    • Vnitřní a vnější třídění
    • Vnitřní třídění - specifikace úlohy, adresní a asociativní algoritmy
    • Radixové třídění - příklad adresního třídícího algorioritmu
    • 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)
    • Jednoduché algoritmy složitosti O(n2):
      • přímé zatřiďování
      • třídění výběrem
      • třídění výměnami - bubblesort, shakesort
      Programy
    • Quicksort - myšlenka; rekursivní implementace s pivotem jako zarážkou
    • Algoritmus Quicksort, jeho rekursivní a nerekursivní verze
    • Odstranování rekurze pomocí zásobníku
    13. Zpět začátek
  13. přednáška 11.ledna
    • Datová struktura halda, operace extract-min, add,
      implementace haldy v poli
    • Algoritmus heapsort a jeho složitost
    • Funkcionální a procedurální parametry.
      Funkcionální a procedurální typy, dlouhé adresy a přepinač F.
    • příklad procedury počítající kořen funkce, kterou dostane jako parametr.
    • Reprezentace aritmetického výrazu pomocí stromu, aritmetické notace prefix, postfix a infix
    • Algoritmy vyčíslení výrazu v postfixu a prefixu
    • Vyčíslování výrazu zapsaného v infixu:
      • postup zdola - od nejvnitřnějších podvýrazů
      • postup shora - nalezení nejvnějšněšího operátoru a rekursivní postup dál
      • metoda rekursivního sestupu
      • Převod infixu na postfix a následné vyhodnocení postfixu
      • Spojení algoritmu převodu na postfix a vyčíslení postfixu do jednoho algoritmu
    14. Zpět začátek