Zpět PRM044

PRM044 Programování I paralelka X

Co bylo na přednáškách

paralelka X - úterý 10:40 K1

přednáška 4.října odpadla - nezaregistroval jsem změnu rozvrhu
omlouvám se studentům
  1. přednáška 11.října
  2. přednáška 18.října
  3. přednáška 25.října
  4. přednáška 1.listopadu
  5. přednáška 8.listopadu
  6. přednáška 15.listopadu
  7. přednáška 22.listopadu
  8. přednáška 29.listopadu
  9. přednáška 6.prosince
  10. přednáška 13.prosince
  11. přednáška 20.prosince
  12. přednáška 3.ledna
  13. přednáška 10.ledna
  1. přednáška 11.ří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), aritmetick operace v desítkové soustavě, 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
    2. Zpět začátek
  2. přednáška 18.ří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 25.října
    • Opakování tématu asymptotické složitosti. Složitost konkrétního výpočtu jako počet provedení zvolené operace (resp. váženého mixu operací). Složitostí je funkce z N do N, Definice asymptotické složitosti, její přednosti a "antiintuitivnost" a zní vyplývající úskalí jejího bezmyšlenkovitého použití na konkrétní problém.
    • 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.
    • Čísla v reálném světě, v matematice a v počítači. Rychlost růstu exponenciely.
  4. přednáška 1.listopadu
    • Typ integer, konstanta maxint, přetečení hodnoty.
      (ukázka, že díky němu není sčítání integerů asociativní)
    • Tvar programu v Pascalu
    • 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
    • for cyklus, jeho syntaxe a sématnika, jednoduché příklady.
    5. Zpět začátek
  5. přednáška 8.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.
    6. Zpět začátek
  6. přednáška 15.listopadu
    • Vícerozměrná pole
    • Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti (program).
    • Stringy
    • Datové a textové soubory - rozdíl v použití.
    • Textové soubory v Pascalu - abstraktní model a konkrétní reprezentace.
    • Procedura assign
    • Otevření textového souboru ke čtení, k zápisu a přípisu. Zavírání textového 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
    Zpět začátek
  7. přednáška 22.listopadu
    • Výstup do textového souboru
      • Opakování - 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ů
      • Realizace výstupů pomocí bufferu, zavírání souboru
      • Pro soubory není přiřazovací příkaz
    • 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í
    • Výpočet kombinačních čísel s prevencí přetečení
    • 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ů).
    • Na rozmyšlenou: n-tá mocnina na co nejméně násobení
    Zpět začátek
  8. přednáška 29.listopadu
    • Opakování - Podprogramy, jejich komunikace s hlavním programem, předávání parametrů.
    • Celočíselné typy v Borland Pascalu (integer, longint, shortint, byte, word).
    • "Reálné" typy v Borland Pascalu - real, single, double.
    • Efektivní "hardwarový" výpočet N-té mocniny pomocí umocňování na druhou, kterému stačí 2*log2 (n) násobení
    • Vyčíslování aritmetických výrazů - shrnutí zásad
    • 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).
    9. Zpět začátek
  9. přednáška 6.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
    • Rozmyslet:
      • Program, který hledá jen ty pozice N nezávislých dam, které nelze získat pomocí symetrie z již dříve nalezených pozic.
      • Program pro hledaní všech maximálních nezávislých konfigurací obecné (exo)figury zadané na vstupu.
    10. Zpět začátek
  10. přednáška 13.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?
    • Předávání parametrů const
    • Příkaz case
    • 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) )
    • Metoda Monte Carlo.
    11. Zpět začátek
  11. přednáška 20.prosince
    • 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 3.ledna
    • Praktické testy, přihlašování, praktické rady pro praktické testy, sbírka úloh
    • Dokumentace zápočtového programu - materiál
    • 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; složitost v nejlepším a nejhorším případě.
    • Algoritmus Quicksort, jeho rekursivní a nerekursivní verze
    • Odstranování rekurze pomocí zásobníku
    13. Zpět začátek
  13. přednáška 10.ledna
    • Datová struktura halda, operace extract-min, add,
      implementace haldy v poli
    • Algoritmus heapsort a jeho složitost
    • reprezentace a aritmetika "dlouhých čísel"
    • 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