Zpět PRM044

PRM044 Programování I paralelka Y ZS 2007/8

Co bylo na přednáškách

paralelka Y - úterý 9:00 M1

Hromadná konzultace k předmětu PRM044
se koná v pondělí 14.ledna 14:00-16:00 v posluchárně S3 na MS
  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
  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
    • Pojem algoritmu, jeho "filosofické vymezení"
    • Příklady konkrétních algoritmů:
    • Úlohy na rozmyšlení:
      1. Nalézt algoritmus pro nalezení stabilního párování
      2. Navrhnout konečné automaty G(enerál), Z(adák) a V(oják) tak, libolně dlouhá posloupnost vojáků začínající generálem a končící zadákem dokázala vydat salvu za nějakou dobu po generálově rozkazu.
        Nejde o přesný popis automatů, ale o myšlenku jejich komunikace
    2. Zpět začátek
  2. přednáška 9.října
    • 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".
    • Ú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
    • 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.
      Naivní algoritmus složitosti n3*m3
      Ani chytrá implementace naivního algoritmu nepomůže
    • Na rozmyšlení:
      1. Navrhnout konečné automaty G(enerál), Z(adák) a V(oják) tak, libolně dlouhá posloupnost vojáků začínající generálem a končící zadákem dokázala vydat salvu za nějakou dobu po generálově rozkazu.
        Nejde o přesný popis automatů, ale o myšlenku jejich komunikace
      2. 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
    • 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
    • Urgence: přihlašte se všichni 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,
      bez znaménka: byte, word
    • 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.
    5. Zpět začátek
  5. přednáška 30.října
    • Typ real, standardní funkce.
    • 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
    • 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í.
    • ilustrativní příklad na vyhodnocování "výrazu"
    • 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ématnika.
    7. Zpět začátek
  7. přednáška 13.listopadu
    • Opakování
      • for cyklus, jeho syntaxe a sémantika, jednoduché příklady.
      • typ pole
    • Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti (program).
    • faktoriál
    • Výpočet kombinačních čísel s prevencí přetečení
    • 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
    8. Zpět začátek
  8. přednáška 20.listopadu
    • stringy
    • vstup z textových souborů
      • opakování
      • Anomální chování programu s testem
        while not eof(F) do
        begin read(F,I); ..... end;
      • Testy seekeof, seekeoln.
      • čtení stringů
    • Specifika čtení z klávesnice
    • Výstup do textového souboru
    • Přesměrovaní standardního vstupu a výstupu
    • Úvod k podprogramům
    9. Zpět začátek
  9. přednáška 27.listopadu
    • 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í
    • 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.
    • 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í.
    • 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.
      • Unity utab a seektab realizující probírané algoritmy vyhledávání v tabulce
        stáhněte si a vytiskněte, budeme se jim věnovat i příště
      • Hledání prvního výskutu prvku v tabulce
        • verze využívající neúplného vyhodnocování booleovských výrazů
        • verze s proměnnou "navíc"
        • použití zařážky pro zefektivnění vyhledávání
    • Úplné a neúplné vyhodnocování booleovských výrazů.
      Přepinač B ovlivňujicí činnost překladače Pascalu
    10. Zpět začátek
  10. přednáška 4.prosince
    • Vícerozměrná pole
    • Najděte chyby v podprogramu, který má transponovat matici
      řešení
    • Samostatně překládané programové jednotky - unity. Interfaceová a implementační část, klausule uses.
      Význam používání unit.
      Příklady unit utab a seektab
    • Hledání prvku v uspořádané tabulce, metoda půlení intervalu - klikátko.
    • Rekursivní funkce - mocnina, faktoriál
    • Rekursivní a nerekursivní podprogramy
      Fibonnaciova posloupnost - chybné řešení s exponenciální složitostí,animace
    • Hanojské věže - animace
    • Rekursivní výpočet N-té mocniny na O(log(N)) násobení
    • 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
    • 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. Zpět začátek
  11. přednáška 11.prosince
    • Standardní podprogramy pro práci se stringy
    • Nerekursivní a rekursivní verze programu hledajícího všechny rozklady zadaného čísla na sčítance
    • 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.
    • 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 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 - viz dále
      • převod na postfix (bude příště)
    • Formální definice aritmetického výrazu a z něj odvozené rekursivní procedury pro vyčíslení hodnoty aritmetického výrazu rekursivním sestupem - klikátko
    • 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 zadaného postorder notací - klikátko
    12. Zpět začátek
  12. přednáška 18.prosince
    • praktické testy, požadavky, zapisování
    • "typované" konstanty (pozor nejsou konstanty !) jako příjemný způsob inicializace hodnot proměnných (i strukturovaných) typů
    • příkaz case
    • opakování aritmetických výrazů
    • vyčíslování hodnoty aritmetického výrazu zadaného postorder notací - klikátko
    • převod infixové notace na postfixovou - klikátko
    • převod infixu na postfix jde spojit s vyčíslováním
    • postavení stromu z prefixové notace (bude příště)
    • 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
    • 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, 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).
    • komponenty souvislosti, použitím prohledávání grafu,
      použitím faktorové množiny - animace
    • Algoritmus vlny - animace a zpětný chod při hledání nejkratší cesty
    • š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
    • komponenty souvislosti, použitím prohledávání grafu,
      použitím faktorové množiny - animace
    13. Zpět začátek
  13. přednáška 8.ledna
    pravděpodobný obsah přednášky - mimo jiné
    • Dominance na šachovnici - je vhodné si v každém políčku uchovávat "počet útoků"
    • 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 a hledání komponent souvislosti
    • Ú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
    • Zápočty, praktické testy a přihlašování k nim, přečtěte si pokyny a požadavky
    14. Zpět začátek