ZS 2010/11 Co bylo PRM044 Programování I paralelka X

přednáška 29.září

Úvodní povídání o předmětu a studiu na MFF UK.
Několik dobrých cílů:

Je třeba umět poznat zda něčemu rozumíme nebo ne
- pokud víme, že věci rozumíme - a je to pravda - jsme "za vodou"
- pokud víme, že věci nerozumíme, pak jsme v situaci, která nás bude provázet celým životem, je však známa naprosto spolehlivá metoda, jak ji "řešit" - několikrát zopakujeme kolečko (rozmyslet si, přečíst si, poradit se)
- pokud nevíme, že nevíme, je to vážný psychologický (či osobnostní) problém, se kterým mohou pomoci rodiče, přítel/kyně, psychoanaliti-k/-čka, trenér (kick)boxu a pod. - ne však učitel, ten jen může pomoci stanovit diagnozu
Pokud se Vám nepodaří tohoto cíle dosáhnout asi Vám na matfyzu nebude moc dobře
Je třeba umět vysvětlit, to čemu rozumíme (jinak řečeno - neumíme-li to vysvětlit, může to být i tím, že tomu nerozumíme).
Správným cílem při tom není vysvětlit to "panu profesorovi" (o kterém předpokládáme, že to umí lépe než my),
ale stejně chytrému kolegovi jako jsme my, který ale o dané věci neví nic. To je těžké a ne všem se to v prním ročníku podaří, ale nejpozději do psaní bakalářské práce se to naučit musíte.

Podmínky k zápočtu, praktický test, zkouška v letním semestru
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 začne na ostro v týdnu od 18.října, bylo by však dobré přijít do skupiny, kam chcete chodit již v týdnu od 11.října.
Zapsat půjde až před koncem měsíce.
Pojem algoritmu, jeho "filosofické vymezení"
Příklady konkrétních algoritmů:
- Eukleidův algoritmus
  - animace1 s rozdílem
  - animace2 se zbytkem po dělení
- aritmetické operace v desítkové soustavě
- konstrukce magického čtverce lichého řádu
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í
budeme se k tomuto schematu mnohokrat vracet
Ú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)
tuto ideu využijeme pro dokazování správnosti algoritmů
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.
Ariadnin algoritmus je vlastně speciálním případem obecnějšího algoritmu prohledávání grafu do hloubky (backtracking), se kterým se ještě mnohokrát setkáme.
Rozmyslet: nalezení stabilního párování k libovolným zadaným preferencím
návod - vzpomeňte si na to, jak to vypadalo v tanečních

Zpět začátek

přednáška 6.října

Pojem invariantu
Griesova úloha o tahání koulí z urny
Problém stabilního párování a jeho řešení algoritmem pánské volenky.
důkaz toho, že pánská volenka skončí a vytvoří stabilní párování,
důkaz toho, že párování vzniklé pánskou volenkou je mezi všemi stabilními párováními optimální pro muže,
t.j. žádný muž nemůže mít v žádném stabilním párování lepší (pro něj) ženu, než je ta, kterou dostal při pánské volence
Existují algoritmy, jejichž správnost jde (poměrně snadno) dokázat, ale jejichž výpočty na reálných datech trvají tak dlouho, že jsou prakticky nepoužitelné. Proto je třeba zabývat se složitostí algotritmů. O tom, jak se měří, budeme - mimo jiné - povídat příště.
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.
Vývojové diagramy řečené bloková schémata - "blokáče"
Tvar programu v Pascalu
for cyklus jako opakování zadaný počet krát (výklad není zatím úplný),
je zakázáno měnit uvntř těla cyklu hodnotu řídící proměnné cyklu, případná změna horní meze uvnitř těla cyklu nemá vliv na počet průchodů tělem cyklu
jednoduché příklady dvou cyklů v sobě.
Zaregistrujte se do systému CodEx !
Zaříďte si účet v laboratoři Karlín !

Zpět začátek

přednáška 20.ří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. Tvar programu v Pascalu.
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.
Rozmyslet: nalézt co nejefektivnější algoritmus pro nalezení maximálního jedničkového obdélníku v 0/1 obdélníku rozměrů m x n.
Hloupé přímočaré řešení metodou "vyzkoušej všechny možnosti" má složitost řádově (co to přesně znamená budeme mít příště) m³ * n³,
je třeba hledat řešení s řádově lepší složitostí.

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

Pokud chcete navštěvovat praktika NPRM047, přijďte nejpozději v tomto týdnu na příslušné praktikum nebo se ozvěte jeho vedoucímu.
Informace o obsazenosti jednotlivých praktik najdete na stránce předmětu

Zpět začátek

přednáška 27.října

Typ boolean.
Program, který testuje, zda číslo na vstupu je prvočíslo.
Funkce v Pascalu, příklady jednoduchých funkcí.
Faktoriál
Výpočet kombinačních čísel - není vhodné volat funkci faktoriál, výpočet s prevencí přetečení
Funkce počítající n- tou mocninu s optimálním počtem násobení (2*log₂(n)) rozmyslete!!
Typ char, funkce ord a chr.
"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í).
Zjednodušená sémantika příkazů read, readln, write, writeln
vstup číselných typů,
formátování výstupů číselných typů
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 n³*m³ ,
  ani chytrá implementace naivní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", rozmyslete
- Zkuste najít algoritmus pracující v čase n*m návod: postup je založený na myšlence, že v matici obroubené nulami každý maximální jedničkový obdélník přiléhá zprava k nějaké nule, a předvýpočtech počtů jedniček nad a pod danou jedničkou

Zpět začátek

přednáška 3.listopadu

Na praktikách NPRM047 jsou ještě volná místa viz stránka
Opakování zoologie pascalských typů,
standardní typy typy integer, real, char, boolean
Výčtové typy
Typ interval. Hostitelský typ, běhové kontroly a možnost je vypínat (a proč to není žádoucí).
V učebnicích i na přednášce se setkáte s typem integer, v konkrétních případech je ho z důvodů malé hodnoty maxint často vhodné nahradit (zejména v Borland Pascalu) typem longint
Obdobně je v případech citlivých na přesnost zobrazení vhodné nahradit typ real typem double
zmenší se tím reativní chyba (zvětší počet platných cifer), nejde o zvětšení rozsahu čísel
Výčtové typy
Funkce ord pro ordinální typy - succ, prev, inc, dec
Zápis čísla v poziční soustavě, výpočet jeho hodnoty Hornerovým schématem
Hornerovo schéma je vlastně lineární algoritmus pro zjištění hodnoty polynomu v zadaném bodě
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 programu je chyba v kontrole přípustnosti znaku v zápisu, zkuste ji odhalit!
děkuji studentovi, který mě na ni upozornil
Pole, indexový typ, typ složky, přístup ke složce pole pomocí indexového výrazu, vícerozměrná pole.
Jednoduchý příklad - hledání maxima čísel ležících pod hlavní diagonálou čtvercové matice
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, algoritmus se složitostí O(m*n) založený na myšlence, že v matici obroubené nulami každý maximální jedničkový obdélník přiléhá zprava k nějaké nule, a předvýpočtech počtů jedniček nad a pod danou jedničkou

přednáška 10.listopadu

Znakové řetězce - stringy, funkce length
Podprogramy a jejich význam pro programování. Návrh programu metodou "shora dolů".
Procedury, funkce, formální a skutečné parametry.
Bloková struktura programu a viditelnost objektů.
Lokální a globální deklarace. Lokální definice zastiňuje globální.
Předávání parametrů hodnotou a referencí. Jednoduchý příklad.
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í
Je výrazně lepší používat komunikaci s podprogramy přes parametry než používat globálních proměnných (vyjímky budou později)
Je vhodné se vyhýbat používání podprogramů lokálních v jiných podprogramech, protože to ve většině dnes používaných jazyků (c-like) nejde
Najděte chyby v podprogramu, který má transponovat matici
řešení
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í.
Příště si zopakujeme použití podprogramů a typy předávání parametrů podprogramům, přečtěte si před příští přednáškou příslušné partie z knihy P. Satrapy (nebo jiné, kterou používáte jako učebnici jazyka),
podívejte se na procedury pro vyhledávání v poli, vytiskněte si je, přiště se těmto příkladům budeme věnovat (příklady jsou formálně umístěny do knihovny (unity), význam téhle syntaktické konstrukce si vysvětlíme)
Motivace k pojmu asymptotické složitosti
Ekvivalence dvou definic pojmu "funce f je velké O z funkce g"
Měření časové složitosti algoritmu, asymptotická složitost - formální definice pomocí O(f).
Nejlepší, nejhorší a průměrný případ

Příště se k asymptoticé složitosti musíme vrátit

Zpět začátek

přednáška 24.listopadu

Opakování:
1. Typ záznam (record) a příkaz with,
  jednoduché příklady.
  Používání příkazu with je analogie vět se zamlčeným podmětem, podstatně zjednodušuje zápis, jeho nadužívání však může vést ke zcela nesrozumitelným programům.
2. Předávání parametrůhodnotou a referencí
Typická reprezentace vektoru jako záznamu o dvou složkách: pole a jeho skutečně využitá délka.
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
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
Programové jednotky - unity, klausule uses, části interface a implementation
Význam použití souborů pro ladění programů
Datové a textové soubory - rozdíl v použití, (file of char není textový ale datový soubor!),
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ů,
  pozor chová se neočekávaně!
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 jako příklad programů, kde formát je "složitější" výraz
- 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
- Chyba Borland Pascalu - při ukončení programu nezavře výstupní soubory (a tedy nevyprázdní buffery do souboru)
  proto se doporučuje na konci programu vždy zavřít všechny výstupní soubory procedurou close
přesměrování vstupu a výstupu při spouštění přeloženého programu mimo ladící prostředí Borland Pascalu

Zpět začátek

přednáška 1. prosince

upozornění na soutěž studentů 1.ročníku v programování pátek 10.12. 15-18 hodin
Chyba Borland Pascalu - při ukončení programu nezavře výstupní soubory (a tedy nevyprázdní buffery do souboru)
proto se doporučuje na konci programu vždy zavřít všechny výstupní soubory procedurou close
Standardní podprogramy pro práci se stringy a komentář k jejich používání
Výstup stringů
Výstup hodnot typu boolean - normální člověk nepoužívá
Rekursivní algoritmy a podprogramy
Rekursivní funkce - faktoriál, je lepší naprogramovat iterativně
Fibonnaciova posloupnost - chybné řešení s exponenciální složitostí - animace
naprogramujte si iterativní řešení i rekursivní řešení bez této chyby(přidáte parametr/y)
Rekursivní řešení problému Hanojských věží a jeho 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
Rozmyslete si dobře a důkladně tento algoritmus i jeho technické provedení. Velmi mnoho rekursivních algoritmů můžete "napasovat" na toto schéma.
Nerekursivní a rekursivní verze programu hledajícího všechny rozklady zadaného čísla na sčítance
rekursivní verzi jsme probrali detailně, rozmyslete si nerekursivní
Výstup otočeného řetězce pomocí rekursivní procedury s lokální proměnnou, implicitně využíváme zásobník volání podprogramů

Zpět začátek

přednáška 8.prosince

opětovné upozornění na soutěž studentů 1.ročníku v programování pátek 10.12. 15-18 hodin
opakování podprogramů pro práci se řetězci: + , lenght, pos, delete, insert, konverze mezi číselnou hodnotou a jejím zápisem ve stringu a
Strukturované a modulární programování - měli byste se zamýšlet nad strukturou svých programů a tvořit spíše podprogramy, které budou data dostávat a odevzdávat prostřednictvím parametrů, než hlavní programy, které řeší vše.
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í
Použití globálních proměnných může vést k sideefectům a pokud pro to nejsou vážné důvody, měl by podprogram komunikovat jen "přes svoji hlavičku" - pomocí parametrů
Jednou z vyjímek je použití globálních proměnných při tvorbě rekurzivních podprogramů (alternativa - předávat stále stejný parametr odkazem - je očividně horší)
Přímá a nepřímá rekurse, direktiva forward,
někdy se používá i jen k tomu, abychom hlavičky podstatných podprogramů umístili hned na začátek programu
V úloze o dominanci šachovnice dámami (hledáme nejmenší počet dam, které by ohrožovaly všechna políčka šachovnice)
pro inkrementální aktualizaci stavu si nestačí pamatovat pro každé políčko zda je ohrožováno, ale stačí pamatovat si kolikrát je ohrožováno
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
Prohledávání grafu do hloubky a šířky .
Společná implementace se seznamy OPEN a CLOSE, ve které se tyto algoritmy liší jen implementací seznamu OPEN (zásobník/fronta)
Animace: do hloubky, do šířky, tyto animace obsahují (poměrně závažnou chybu) Najděte ji!
Algoritmus vlny - prohledávání do šířky bez fronty, přímo do vrchlů grafu se zapisují vzdálenosti od startu
"zpětný chod" pro nalezení nejkratší cesty
Vnitřní třídění - specifikace úlohy, adresní a asociativní (založené na porovnávání klíčů) algoritmy
Jednoduché asociativní algoritmy složitosti O(n²):
- přímé zatřiďování
- binární zatřiďování - polohu najdeme v logaritmické čase, ale posun pole je lineární
- třídění výběrem
- třídění výměnami - bubblesort, shakesort
  implemantace bez pamatování si místa poslední výměny je programátorská nešikovnost
zdrojové texty procedur realizujících jednotlivé třídící algoritmy jsou ke stažení na WWWW, příště se k nim vrátíme

Zpět začátek

přednáška 15.prosince

Opakování procházení grafu do šířky a hloubky
typické implementace zásobníku a fronty (fronta pomocí "zacykleného pole")
Porovnání použití prohledávání do šířky a do hloubky pro hledání nejkratší cesty
Algoritmus vlny - prohledávání do šířky bez fronty, přímo do vrchlů grafu se zapisují vzdálenosti od startu
"zpětný chod" pro nalezení nejkratší cesty
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
O praktických testech

Zpět začátek

přednáška 22.prosince

opakování:
- Motivace k pojmu asymptotické složitosti
- Ekvivalence dvou definic pojmu "funce f je velké O z funkce g"
- Měření časové složitosti algoritmu, asymptotická složitost - formální definice pomocí O(f).
- Nejlepší, nejhorší a průměrný případ
formální definice asymptotické složitosti
Složitost některých konkrétních algoritmů
Paradoxní aspekty pojmu asymptotické složitosti
Quicksort - myšlenka; rekursivní implementace s pivotem jako zarážkou; časová složitost v nejlepším a nejhorším případě.
Algoritmus Quicksort, jeho rekursivní verze (bude na internet doplněna)
a nerekursivní verze - přečtěte si
Využití prvku tříděného pole jako pivota - mohu použít jako zarážku
Složitost quicksortu v nejhoším a v nejleším případě
Paměťová složitost - třída algoritmů pracujících "na místě" - "in situ"
Paměťová složitost quicksortu - netřídí na místě
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.
Dlouhá čísla - reprezentace a aritmetické operace s nimi

Zpět začátek

přednáška 5.ledna

Na přednášce pravděpodobně bude - všechno asi nestihneme

komentář k praktickým testům a přihlašování na ně
třetí způsob předávání parametrů v Pascalu - const
"typované" konstanty (pozor nejsou to konstanty !) jako příjemný způsob inicializace hodnot proměnných (i strukturovaných) typů
konformní schémata polí - rozšíření Pascalu, které umožňuje napsat podprogramy, který lze předat jako skutečný parametr pole libovolné délky
omezení toho způsobu - je asi lepší je nepoužívat
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
  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
- algoritmus převodu na postfix jde rovnou spojit a algorimem vyčíslování postfixu
Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti (program).
hledání minimální kostry grafu
příkaz goto - je lepší nepoužívat
"kultivované" formy skoků: break, continue, return, halt
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
standardní unity Pascalu

přednáška 12.ledna

vyčíslování hodnoty z prefixové notace
technické poznámky k programování vyhodnocování výrazů
Kvadratický algoritmus pro nalezení nejdelší rostoucí vybrané posloupnosti (program)
jako příklad "dynamického programování"
hledání minimální kostry grafu
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
standardní unity Pascalu
unita CRT
příkaz goto - je lepší nepoužívat
"kultivované" formy skoků: break, continue, return, halt
Přepinače kompilátoru
Procedurální a funkcionální parametry procedura pro hledání kořene rovnice f(x)=0 metodou půlení intervalu
odpovědi na dotazy -- budou-li

Hromadná konzultace v úterý 18.1. od 14:00 v posluchárně S4

Zpět začátek

PRM044 Programování I paralelka X ZS 2010/11

Co bylo na přednáškách

paralelka X - středa 8:05 F1