Zpět PRM044

PRM044 Programování I paralelka X ZS 2006/7

Co bylo na přednáškách

paralelka X - úterý 15:40 M1

Hromadná konzultace k předmětu PRM044 se koná v pondělí 15.ledna 2007 od 13:00 v posluchárně S3.

  1. přednáška 3.října
  2. přednáška 10.října
  3. přednáška 17.října
  4. přednáška 24.října
  5. přednáška 31.října
  6. přednáška 7.listopadu
  7. přednáška 14.listopadu
  8. přednáška 21.listopadu
  9. přednáška 28.listopadu
  10. přednáška 5.prosince
  11. přednáška 12.prosince
  12. přednáška 19.prosince
  13. přednáška 9.ledna
  1. přednáška 3.ří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, jeho "filosofické vymezení"
    • Úloha o bludišti a jednoduchý "Ariadnin" algoritmus, který ji řeší (trasování na konkrétním bludišti).
    • Algoritmus je správný, když je
      • konečný (na každý přípustných datech skončí)
        a
      • parciálně správný (pokud skončí, tak dá správný výsledek)
    • Důkaz konečnosti Ariadnina algoritmu
    • Čísla ve světě
    • Úlohy na rozmyšlení:
      1. Nalézt algoritmus pro nalezení stabilního párování
      2. Zkusit dokázat parciální správnost "Ariadnina" algoritmu
    2. Zpět začátek
  2. přednáška 10.ří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.
    • 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"
      • rozmyslet: Algoritmus pracující v čase n*m
    • prezence
    3. Zpět začátek
  3. přednáška 17.října
    • Algoritmus na hledání maximálního jedničkového obdélníku v 0/1 obdélníku rozměrů m x n pracující v čase n*m.
      Animace algorimů pro nalezení největšího jedničkového obdélníka.
    • 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.
    • Tvar programu v Pascalu
    • Strukturované 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.
    • Typ integer, aritmetické operace a jejich priority, konstanta maxint, přetečení hodnoty.
      (ukázka, že díky němu není sčítání integerů asociativní)
    • Typ real, standardní funkce,
    4. Zpět začátek
  4. přednáška 24.října
    • opakování
      čísla ve světě, v matematice a "v počítači",
      čísla zobrazená přesně a čísla zobrazená se zaokrouhlením
    • 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.
    • 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
    5. Zpět začátek
  5. přednáška 31.října
    • Funkce s parametry předávanými hodnotou, jednoduché příklady
    • ilustrativní příklad na vyhodnocování "výrazu"
    • Výčtové typy
    • for cyklus, jeho syntaxe a sématnika, jednoduché příklady.
    • "Zoologie" typů v Pascalu (jednoduché - strukturované, standardní - definované programátorem, ordinální).
    • Názorná ukázka boje s hardwarem,
      metoda "vystup a nastup" vždy nepomáhá
    • 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.
    • Pole, indexový typ, typ složky, přístup ke složce pole pomocí indexového výrazu.
    • for cyklus, jeho syntaxe a sématnika, jednoduché příklady.
    6. Zpět začátek
  6. přednáška 7.listopadu
    • Opakování
    • Vícerozměrná pole
    • Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti (program).
    • Funkce počítající mocninu s optimálním početem násobení, faktoriál
    • Výpočet kombinačních čísel s prevencí přetečení
    • Rekursivní funkce - mocnina, faktoriál
    • Rekursivní a nerekursivní podprogramy
      Fibonnaciova posloupnost - chybné řešení s exponenciální složitostí,animace
    • 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.
    • 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í.
    7. Zpět začátek
  7. přednáška 14.listopadu
    • Bloková struktura programu a viditelnost objektů
    • Alokace lokálních objektů (parametrů a lokálních proměnných) na zásobníku.
    • Kdy použít předávání parametrů hodnotou resp. referencí
    • Typ záznam (record) a příkaz with,
      jednoduché příklady
    • 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
    • Samostatně překládané programové jednotky - unity. Interfaceová a implementační část, klausule uses.
      Význam používání unit.
    • Úplné a neúplné vyhodnocování booleovských výrazů.
      Přepinač B ovlivňujicí činnost překladače Pascalu
    8. Zpět začátek
  8. přednáška 21.listopadu
    • Opakování: Samostatně překládané programové jednotky - unity.
    • 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
      • 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
    • Textové řetězce (stringy) a jejich výstup - ještě se k nim vrátíme
    9. Zpět začátek
  9. přednáška 28.listopadu
    • Opakování práce se soubory
    • Textové řetězce (stringy)
    • Vstup a výstup stringů
    • Standardní podprogramy pro práci se stringy
    • Hanojské věže - animace
    • 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í proměnnou.
    • 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 5.prosince
    • Opakování - princip programu pro hledání N nezávislých dam na šachovnici N x N
    • 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.
    • 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?
    • vyčíslování hodnoty aritmetického výrazu
      • metoda shora dolů - nalezení "nejvnějšnějšího" operátoru a rekursivní volání
      • metoda zdola nahoru - postupné vyčíslování toho, co jde "hned vyčíslit"
      • k dalším metodám se vrátíme
    • Příkaz case
    • typy souboru při práci s Pascalem *.pas, *.tpu, *.tpl, *.exe
      překlad Compile, Make a Bild
    • Systémové unity SYSTEM a CRT. Stručná charakteristika jejich role.
    • 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 12.prosince
    • unita CRT
    • 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.
    • Různé reprezentace grafu,
      Matice sousednosti, matice incidence, seznam hran, seznam následníků.
    • Prohledávání grafu do hloubky a šířky.
      Animace: do hloubky, do šířky, s výběrem
      tyto animace obsahují (poměrně závažnou chybu)
    • Společná implementace se seznamy OPEN a CLOSE, ve které se tyto algoritmy liší jen implementací seznamu OPEN (zásobník/fronta).
    12. Zpět začátek
  12. přednáška 19.prosince
    • o zapisování k praktickým testům
    • "typované" konstanty (pozor nejsou konstanty !) jako příjemný způsob inicializace hodnot
    • Zásobník, fronta a jejich implementace
    • Hledání nejkratší cesty (uvažujeme počet hran) procházením grafu
    • Použití mocnění matice sousednosti pro zjišťování hranové vzdálenosti
    • Algoritmus vlny - animace
    • Dijktstrův algoritmus - animace , invariant a důkaz správnosti
    • Komponenty souvislosti prohledáváním grafu - animace a faktorová množnina - animace
    13. Zpět začátek
  13. přednáška 9.ledna
    pravděpodobný obsah přednášky - mimo jiné
    • Zápočty, praktické testy a přihlašování k nim, přečtěte si pokyny a požadavky
    • Dlouhá čísla - reprezentace a aritmetické oprace s nimi
    • Komentář k programování úlohy o hledání nejkratší cesty dané figury po šachovnici se zakázanými políčky
    • Funkcionální a procedurální parametry.
      Funkcionální a procedurální typy, dlouhé adresy a přepinač F.
    • Úloha vnitřního třídění - 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
    14. Zpět začátek