ZS 2007/8 Co bylo PRM044 Programování I paralelka X

přednáška 4.ří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í"
Příklady konkrétních algoritmů:¨
- Eukleidův algoritmus
  - animace1 s rozdílem
  - animace2 se zbytkem po dělení
- Erathostenovo síto (a úpravy jeho efektivity)
- aritmetické operace v desítkové soustavě
- konstrukce magického čtverce lichého řádu
Ú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
Úlohy na rozmyšlení:
1. Nalézt algoritmus pro nalezení stabilního párování
2. Rozmyslet si důkaz toho, že pokud Theseus skončí u Ariadny, pak Minotauros v bludišti být nemůže

Zpět začátek

přednáška 11.října

Pojem invariantu algoritmu
Důkaz parciální správnosti Ariadnina 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".
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 n³*m³ ,
  ani chytrá implementace nivního algoritmu příliš nepomůže
- Algoritmus se složitostí n*m² využívající předvýpočet "počtu jedniček pod danou jedničkou"
- rozmyslet: Algoritmus pracující v čase n*m

Zpět začátek

přednáška 18.ří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 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.
Tvar programu v Pascalu

Zpět začátek

přednáška 25.října

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,
bez znaménka: byte, word
Typ real
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.

Zpět začátek

přednáška 1.listopadu

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.
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*log₂(n))
ilustrativní příklad na vyhodnocování "výrazu"
Typ char, funkce ord a chr.
Zápis čísla v poziční soustavě, výpočet jeho hodnoty Hornerovým schématem - rozmyslete si,
stáhněte si program, který budeme probírat příště

Zpět začátek

přednáška 8.listopadu

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.
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.

Zpět začátek

přednáška 15.listopadu

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
Výstup do textového souboru
- Formátování
- Procedura write, writeln,
- výstup znaků,
- výstup integerů (bez formátu se výsledky mohou "slepit")
  Pascalův trojúhelník
- výstup čísel typu real, zokrouhlování, výstup v semilogaritmickém a "desetinném" tvaru
- Ukázkový program demonstrující formátovaný výstup číselných hodnot a jeho výstup

Zpět začátek

přednáška 22.listopadu

Opakování vstupů a výstupů
Textové řetězce - stringy
Anomální chování programu s testem
while not eof(F) do
begin read(F,I); ..... end;
Testy seekeof, seekeoln.
Specifika čtení z klávesnice
Vstup a výstup textových řetězců
Přesměrovaní standardního vstupu a výstupu
faktoriál
Výpočet kombinačních čísel s prevencí přetečení
Podprogramy - procedury a funkce
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í
Předávání parametrů hodnotou a referencí
pouze první seznámení - vrátíme se k tomu

Zpět začátek

přednáška 29.listopadu

Bloková struktura programu a viditelnost objektů. Lokální versus globální deklarace a jim odpovídající objekty.
Opakování předávání parametrů hodnotou a referencí
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í.
Vícerozměrná pole
Najděte chyby v podprogramu, který má transponovat matici
řešení
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.
Typ záznam a příkaz with
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

Zpět začátek

přednáška 6.prosince

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
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
Výstup otočeného řetězce pomocí rekursivní procedury s lokální proměnnou.
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

Zpět začátek

přednáška 13.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.
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 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 (bude příště)
- převod na postfix (bude příště)- klikátko

Zpět začátek

přednáška 20.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 preorder notací - klikátko
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. Jak se musí změnit hlavičky podprogramů a jejich vzájemná komunikace?
vyčíslování hodnoty aritmetického výrazu zadaného preorder notací - klikátko
převod infixové notace na postfixovou - klikátko
Typ množina, jeho realizace v Borland Pascalu.
Velká množina jako pole množin.

Zpět začátek

přednáška 3.ledna

převod infixu na postfix jde spojit s vyčíslováním postfixu
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í (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).
Algoritmus vlny - animace a zpětný chod při hledání nejkratší cesty
Porovnání použití prohledávání do šířky a do hloubky pro 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
komponenty souvislosti, použitím prohledávání grafu,
použitím faktorové množiny - animace
Hledání nejkratší cesty (měřeno počtem hran) procházením grafu, násobením matice sousednosti, použití prohledání komponent souvislosti

Zpět začátek

přednáška 10.ledna

Dominance na šachovnici - je vhodné si v každém políčku uchovávat "počet útoků"
Zásobník, fronta a jejich implementace
Úloha vnitřního třídění - jednoduché algoritmy složitosti O(n²):
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
Poznámky k praktickým testům

Zpět začátek

-->

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

Co bylo na přednáškách

paralelka X - čtvrtek 14:00 M1