Zpět PRM044

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

Co bylo na přednáškách

paralelka Y - čtvrtek 14:00 K1

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 5.října
  2. přednáška 12.října
  3. přednáška 19.října
  4. přednáška 26.října
  5. přednáška 2.listopadu
  6. přednáška 9.listopadu
  7. přednáška 16.listopadu
  8. přednáška 23.listopadu
  9. přednáška 30.listopadu
  10. přednáška 7.prosince
  11. přednáška 14.prosince
  12. přednáška 21.prosince
  13. přednáška 4.ledna
  14. 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
    • 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
    Zpět začátek
  2. přednáška 12.října
    • WWW stranky předmětu, literatura, překladače
    • Úloha o bludišti, poznámky k formulaci algoritmu, důkaz jeho správnosti .
    • 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. přednáška 19.ří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.
    • Čísla ve světě
    4. Zpět začátek
  4. přednáška 26.října
    • Opakování:
      Proměnná, přiřazovací příkaz, Ú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 ve světě, v matematice, "počítačová" čísla.
    • 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í)
    • Celočíselné typy v Borland Pascalu:
      integer, shortint, longint,
      bez znaménka: byte, word
    • Typ real, standardní funkce,
    • 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.
    5. Zpět začátek
  5. přednáška 2.listopadu
    • Opakování
      proměnná, typ, konstanta, literál,
      číselné typy integer a real
    • Absolutní a relativní přesnost (udává se počtem platných cifer)
      reálné typy v Borland Pascalu real, double a single
    • 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.
    • 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 9.listopadu
    • Opakování
    • 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.
    • 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
    • Procedury.
    • Předávání parametrů hodnotou a referencí. Jednoduchý příklad.
    7. Zpět začátek
  7. přednáška 16.listopadu
    • Opakování předávání parametrů hodnotou a referencí
    • Bloková struktura programu a viditelnost objektů, 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.
    • Kdy použít předávání parametrů hodnotou resp. referencí
    • 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í.
    • 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če B a R ovlivňujicí činnost překladače Pascalu
    8. Zpět začátek
  8. přednáška 23.listopadu
    • Opakování: Samostatně překládané programové jednotky - unity.
    • Textové řetězce - 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
      • 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
    9. Zpět začátek
  9. přednáška 30.listopadu
    • Opakování práce se soubory
    • výstup čísel typu real, výstup v semilogaritmickém tvaru nebo se zadaným počtem desetinných míst
    • 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.
    • Přímá a nepřímá rekurze, direktiva forward
    Zpět začátek
  10. přednáška 7.prosince
    • povídání o ladění
    • 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.
    • Formální definice aritmetického výrazu a z něj odvozené rekursivní procedury pro vyčíslení hodnoty aritmetického výrazu (metoda rekursivního sestupu)
    • 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
    • typy souboru při práci s Pascalem *.pas, *.tpu, *.tpl, *.exe
      překlad Compile, Make a Bild
    Zpět začátek
  11. přednáška 14.prosince
    • "typované" konstanty (pozor nejsou konstanty !) jako příjemný způsob inicializace hodnot proměnných (i strukturovaných) typů
    • Pseudonáhodná čísla - princip použití, hnízdo generátoru.
    • Pseudonáhodná čísla v Borland Pascalu ( RandSeed, Randomize, Random, Random(n) )
    • Metoda Monte Carlo.
    • 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ů.
  12. přednáška 21.prosince
    • Systémové unity SYSTEM Graph a CRT.
    • unita CRT
    • Zásobník, fronta a jejich implementace
    • 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).
    • Hledání nejkratší cesty (měřeno počtem hran) procházením grafu
    • Algoritmus vlny - animace
    • Komentář k programování úlohy o hledání nejkratší cesty dané figury po šachovnici se zakázanými políčky
    13. Zpět začátek
  13. přednáška 4.ledna
    • 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
    • Použití mocnění matice sousednosti pro zjišťování hranové vzdálenosti
    • Dijktstrův algoritmus - animace , invariant a důkaz správnosti
    • Ú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
        Programy
    14. Zpět začátek
  14. přednáška 11.ledna
    Pravděpodobný obsah zbývajících přednášek - mimo jiné
    • Komponenty souvislosti prohledáváním grafu - animace a faktorová množnina - animace
    • Funkcionální a procedurální parametry.
      Funkcionální a procedurální typy, dlouhé adresy a přepinač F.
    • 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
    • Algoritmus quicksort - zákládní idea (vrátíme se k němu podrobně v letním semestru)
    15. Zpět začátek