Zpět PRM044

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

Co bylo na přednáškách

paralelka X - pondělí 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 6.října
  2. přednáška 13.října
  3. přednáška 20.října
  4. přednáška 27.října
  5. přednáška 3.listopadu
  6. přednáška 10.listopadu
    7. 17.listopadu je státní svátek
  7. přednáška 24.listopadu
  8. přednáška 1.prosince
  9. přednáška 8.prosince
  10. přednáška 15.prosince
  11. přednáška 5.ledna
  12. přednáška 12.ledna
  1. přednáška 6.ří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
    • O předmětu nepovinném 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
    • Pojem algoritmu, jeho "filosofické vymezení"
    • 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í
    Zpět začátek
  2. přednáška 13.ří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".
    • Ú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
    • Pojem invariantu algoritmu
    • Důkaz parciální správnosti Ariadnina 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
      • Trivální algoritmus složitosti n3*m3 ,
        ani chytrá implementace nivního algoritmu příliš nepomůže
      • 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
    • Motivace k pojmu asymptotické složitosti
    • Ekvivalence dvou definic pojmu "funce f je velké O z funkce g"
    3. Zpět začátek
  3. přednáška 20.ří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
      Demonstrační program
    • 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.
    • 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
    4. Zpět začátek
  4. přednáška 27.ří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ů"
    • Čí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
    • Konstanty jako nástroj pro snadnou modifikaci programů.
      Ukázkové programy.
    • 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.
    • Zjednodušená sémantika příkazů read, readln, write, writeln
      vstup číselných typů,
      formátování výstupů číselných typů
    • Typ boolean.
    • Program, který testuje, zda číslo na vstupu je prvočíslo.
    5. Zpět začátek
  5. přednáška 3.listopadu
    • 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.
    • for cyklus, jeho syntaxe a sématnika, jednoduché příklady.
    • Hledání nejdelší vybrané rostoucí posloupnosti,
      naivní algoritmus je exponenciální - najděte rychlejší řešení. (bude na příští přednášce)
    6. Zpět začátek
  6. přednáška 10.listopadu
    • Funkce s parametry předávanými hodnotou, jednoduché příklady
    • Funkce počítající n- tou mocninu s optimálním počtem násobení (2*log2(n))
    • Faktoriál
    • Výpočet kombinačních čísel s prevencí přetečení
    • Rekursivní funkce - mocnina, faktoriál
    • Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti (program).
    • Znakové řetězce - stringy
    • 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.
      • Čtení znakových řetězců
    • Výstup do textového souboru
    7. Zpět začátek
  7. přednáška 24.listopadu
    • O předmětu NPRM047 Praktika ....
    • Opakování: formátování výstupu do textových souborů, Pascalův trojúhelník
    • Výstup stringů
    • Vícerozměrná pole
    • ilustrativní příklad na vyhodnocování "výrazu"
    • 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.
    • 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í.
    • 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.
    • planý poplach
    8. Zpět začátek
  8. přednáška 1. 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.
    • Kriteria 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
    9. Zpět začátek
  9. přednáška 8.prosince
    • třetí způsob předávání parametrů v Pascalu - const
    • Rekursivní algoritmy a podprogramy
    • Animace hanoiských věží
    • Rekursivní funkce - mocnina, faktoriál
    • Fibonnaciova posloupnost - chybné řešení s exponenciální složitostí - animace
    • 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
    • Nerekursivní a rekursivní verze programu hledajícího všechny rozklady zadaného čísla na sčítance
    • K oběma programům se ještě vrátíme, promyslete si je
    • 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.
    • Pseudonáhodná čísla, pojem a jejich použití, hnízdo generátoru náhodných čísel
    • Pseudonáhodná čísla v Borland Pascalu ( RandSeed, Randomize, Random, Random(n) )
    • Metoda Monte Carlo
    10. Zpět začátek
  10. přednáška 15.prosince
    • První informace o praktických testech, průzkum zájmu o jednotlivé termíny
    • Výstup otočeného řetězce pomocí rekursivní procedury s lokální proměnnou.
    • Přímá a nepřímá rekurse, direktiva forward.
    • 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
        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
    • Rozmyslet: Modifikace programu pro vyčíslování hodnoty aritmetického výrazu metodou rekursivního sestupu 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?
    • Prohledávání grafu do hloubky a šířky.
      Animace: do hloubky, do šířky, tyto animace obsahují (poměrně 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
    Zpět začátek
  11. přednáška 5.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
    • Různé reprezentace grafu,
      Matice sousednosti, matice incidence, seznam hran, seznam následníků.
    • Mocnina grafu sousednosti - použití pro hledání komponent souvislosti
    • Dijkstrův algoritmus pro hledání nejkratší cesty v grafu s nezáporně ohodnocenými hranami
      invarianty, složitost - klikátko
    • Dlouhá čísla - reprezentace a aritmetické operace s nimi
    12. Zpět začátek
  12. přednáška 12.ledna
    • Typ množina, jeho realizace v Borland Pascalu.
    • 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
    • Velká množina jako pole množin.
    • 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
    13. Zpět začátek
Zpět výuka ZS 2008/9