Zpět PRM044

PRM044 Programování I paralelka Y ZS 2008/9

Co bylo na přednáškách

paralelka Y - čtvrtek 8:10 F1

Hromadná konzultace se koná v pondělí 19.ledna od 9:00
v posluchárně S5 ve II. poschodí budovy na Malé straně

  1. přednáška 2.října
  2. přednáška 9.října
  3. přednáška 16.října
  4. přednáška 23.října
  5. přednáška 30.října
  6. přednáška 6.listopadu
  7. přednáška 13.listopadu
  8. přednáška 20.listopadu
  9. přednáška 27.listopadu
  10. přednáška 4.prosince
  11. přednáška 11.prosince
  12. přednáška 18.prosince
  13. přednáška 8.ledna
  14. přednáška 15.ledna
  1. přednáška 2.ří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
    • O nepovinném předmětu NPRM047 "Praktika z programování pro začátečníky", jeho cílech a způsobech výuky
      Tento předmět půjde zapsat až cca za dva týdny a začne za tři týdny
    • Příklady konkrétních algoritmů:
    • 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í.
    2. Zpět začátek
  2. přednáška 9.října
    • 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".
    • 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
    • Důkaz praciální správnosti Ariadnina algoritmu.
    • Pojem invariantu algoritmu
    • Beletristické zpracování Ariadnina algoritmu a důkazu jeho správnosti.
    • 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.
      animace
      Naivní algoritmus složitosti n3*m3
      Ani chytrá implementace naivního algoritmu nepomůže
    • Úvod k pojmu asymptotické složitosti
    • Dvě ekvivalentní definice pojmu "velké O"
    • Na rozmyšlení:
      Nalézt rychlejší algoritmus pro hledání max. jedničkového obdélníka
    3. Zpět začátek
  3. přednáška 16.října
    • Fáze řešení problému a problémy na jejich rozhraních:
      skutečnost - (matematický) model - algoritmizace a volba datových struktur - vytváření programu - testování
    • 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.
    • Hledání maximálního jedničkového obdélníku v 0/1 obdélníku rozměrů m x n
      • 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
      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.
    4. Zpět začátek
  4. přednáška 23.října

    Pokud jste tak již neučinili, pořiďte si účet v laboratoři Karlín a zaregistrujte se do systému Codex !!!

    • Opakování: proměnná, přiřazovací příkaz
    • 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.
    • Vývojové diagramy řečené bloková schémata - "blokáče"
      programové konstrukce Pascalu jsou strukturované, lze tedy při návrhu programu postupovat "shora dolů"
    • Tvar programu v Pascalu, komentáře
    • Čísla ve světě, v matematice a "v počítači" - čísla zobrazená přesně a čísla zobrazená se zaokrouhlením
    • 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
    • Konstanty jako nástroj pro snadnou modifikaci programů.
      Ukázkové programy.
    • Zjednodušená sémantika příkazů read, readln, write, writeln
      vstup číselných typů,
      formátování výstupů číselných typů
    5. Zpět začátek
  5. přednáška 30.října
    • Typ real, standardní funkce, zaokrouhlovací chyby.
    • Typová ochrana přiřazovacího příkazu. Funkce trunc a round.
    • 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.
    • 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
    • Funkce s parametry předávanými hodnotou, jednoduché příklady
    • Funkce počítající mocninu s optimálním počtem násobení
    6. Zpět začátek
  6. přednáška 6.listopadu
    • Opakování.
      • Funkce počítající mocninu s optimálním počtem násobení
      • Hornerovo schéma -lineární výpočet hodnoty polynomu
    • 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.
    • V Pascalu musí být význam každého identikátoru definován dříve než je tento identifikátor použit
      (vyjímka je u ukazatelů - bude až v letním semestru), aby překladač mohl být jednoprůchodový
    • Pole, indexový typ, typ složky, přístup ke složce pole pomocí indexového výrazu.
    • for cyklus, jeho syntaxe a sémantika.
    • faktoriál
    • Výpočet kombinačních čísel s prevencí přetečení
    • Rozmyslet:
      • Funkce počítající n- tou mocninu s optimálním počtem násobení (2*log2(n))
      • Najděte co nejlepší algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti
    7. Zpět začátek
  7. přednáška 13.listopadu
    • ilustrativní příklad na vyhodnocování "výrazu"
    • Rekursivní funkce - mocnina, faktoriál
    • Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti (program).
    • Datové a textové soubory - rozdíl v použití.
      v zimním semestru budeme používat jen textové soubory
    • 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 read, 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.
    8. Zpět začátek
  8. přednáška 20.listopadu
    • O předmětu NPRM047 Praktika ....
    • Znakové řetězce - stringy
    • Čtení znakových řetězců
    • Výstup do textového souboru
    • Přesměrovaní standardního vstupu a výstupu
    • Vícerozměrné pole
    • Podprogramy a jejich význam pro programování. Návrh programu metodou "shora dolů".
    • Procedury, formální a skutečné parametry.
    • Předávání parametrů hodnotou a referencí. Jednoduchý příklad.
      ještě se k tomu vrátíme
    9. Zpět začátek
  9. přednáška 27.listopadu
    • Opakování: Předávání parametrů hodnotou a referencí, jednoduchý příklad
    • 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í
    • 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í.
    • Kritéria pro užitečné rozdělení systému na části:
      • Vazby jednotlivých částí (jejich inteface) musí být jednoduché
      • Funkce celého systému musí jít jednoduše popsat jako spolupráce jeho částí aniž bychom museli znát (detailní) vnitřní strukturu jeho částí
    • Dobrá zásada:
      Vždy hned po návrhu hlavičky podprogramu napište komentář, který v "řeči parametrů" popíše, co podprogram má udělat (nikoli jak, ale co), teprve pak pište její kód
    • 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í prvního výskytu prvku v tabulce, urychlení výpočtu pomocí zarážky.
    • Zdrojové kódy vyhledávací algoritmů v unitě a pomocná unita - bude příště, vytiskněte si
    10. Zpět začátek
  10. přednáška 4.prosince
    • Standardní podprogramy pro práci se stringy
    • Najděte chyby v podprogramu, který má transponovat matici - řešení
    • 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 - klikátko.
      • 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č B ovlivňujicí činnost překladače Pascalu
    • Samostatně překládané programové jednotky - unity. Interfaceová a implementační část, klausule uses.
      Význam používání unit.
    • Přetečení indexu, přepínač R
    • Rekursivní algoritmy a podprogramy
    • Animace hanoiských věží
    • Rekursivní funkce - mocnina, faktoriál
    • Fibonnaciova posloupnost - chybné řešení s exponenciální složitostí - animace
    • Rozmyslete si - vrátíme se k tomu příště
      Nerekursivní a rekursivní verze programu hledajícího všechny rozklady zadaného čísla na sčítance
  11. přednáška 11.prosince
    • Třetí způsob předávání parametrů v Pascalu - const
    • 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
    • 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.
    • Opakování: Nerekursivní a rekursivní verze programu hledajícího všechny rozklady zadaného čísla na sčítance
    • 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 - klikátko
    • Rozmyslet: Modifikace programu tak, aby nepoužíval podprogramů lokálních v jiném podprogramu. Jak se musí změnit hlavičky podprogramů a jejich vzájemná komunikace?
    • Pseudonáhodná čísla - princip použití, hnízdo generátoru.
    • Pseudonáhodná čísla v Borland Pascalu ( RandSeed, Randomize, Random, Random(n) )
    • Metoda Monte Carlo.
  12. přednáška 18.prosince
    • První informace o praktických testech
    • zadání aritmetického výrazu stromem a třemi notacemi: inorder, postorder, preorder
      klikátka:
    • vyčíslování hodnoty aritmetického výrazu zadaného postorder notací - klikátko
    • vyčíslování hodnoty aritmetického výrazu zadaného preorder notací
    • vyčíslování hodnoty aritmetického výrazu z inorder notace
      • metoda shora dolů - nalezení "nejvnějšnějšího" operátoru a rekursivní volání - klikátko
      • metoda zdola nahoru - postupné vyčíslování toho, co jde "hned vyčíslit"
      • metoda rekursivního sestupu - byla minule
        Formální definice aritmetického výrazu a z něj odvozené rekursivní procedury pro vyčíslení hodnoty aritmetického výrazu - klikátko
      • převod na postfix klikátko
      podrobněji se o vyčíslování aritmetických výrazů můžete dočíst ve 12. kapitole knihy Algoritmy a programovací techniky
    • Prohledávání grafu do hloubky a šířky.
      Animace: do hloubky, do šířky, tyto animace obsahují závažnou chybu. Najděte ji!
    • Společná implementace se seznamy OPEN a CLOSE, ve které se tyto algoritmy liší jen implementací seznamu OPEN (zásobník/fronta).
    • Porovnání použití prohledávání do šířky a do hloubky pro hledání nejkratší cesty
    • Algoritmus vlny - animace a zpětný chod při hledání nejkratší cesty
    13. Zpět začátek
  13. přednáška 8.ledna
    • praktické testy, požadavky, zapisování
    • "typované" konstanty (pozor nejsou to konstanty !) jako příjemný způsob inicializace hodnot proměnných (i strukturovaných) typů
    • příkaz case
    • Dlouhá čísla - reprezentace a aritmetické operace s nimi
    • 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;
      faktorová množnina - animace
    • Dijkstrův algoritmus pro hledání nejkratší cesty v grafu s nezáporně ohodnocenými hranami
      invarianty, složitost - klikátko
    14. Zpět začátek
  14. přednáška 15.ledna
    • Různé reprezentace grafu,
      Matice sousednosti, matice incidence, seznam hran, seznam následníků.
    • Mocnina grafu sousednosti - použití pro hledání komponent souvislosti
    • Porovnání použití prohledávání do šířky a do hloubky pro hledání nejkratší cesty
    • Algoritmus vlny - animace a zpětný chod při hledání nejkratší cesty
    • Komentář k programování úlohy o hledání nejkratší cesty dané figury po šachovnici se zakázanými políčky, šachovnici se zakázanými poli je vhodné si "nakreslit" v editoru a jednoduše přečíst,
      srovnej se čtením seznamu zakázaných políček
    • Rozmyslet vhodnou datovou reprezentaci pro úlohu o dominanci šachovnice se zakázanými políčky:
      hledám nejmenší počet figur daného typu (např. dam), které jedním tahem ohrožují každé políčko šachovnice
    • Úloha vnitřního třídění - jednoduché algoritmy složitosti O(n2) efektivnější si necháme na letní semestr:
      • přímé zatřiďování
      • třídění výběrem
      • třídění výměnami - bubblesort, shakesort
      Programy
    • unita CRT
Zpět výuka ZS 2008/9