Programování I (PRM044 - Matematici)
Cvičení se koná každé úterý od 12:20 v učebně K6 (Karlín), cvičení je určeno pro studijní kroužek matematici/59.
Na této stánce budou postupně uveřejňovány informace týkající se průběhu cvičení.
Cvičení 3.10.2006
Pro získání zápočtu je vyžadována aktivní účast na cvičení, napsání zápočtové písemky a
vytvoření zápočtového programu. Dále je nutné složit praktický test z programování u
počítače, tato povinnost se však řeší mimo cvičení.
Cvičení 10.10.2006
Bylo zadáno několik lehkých domácích úloh: přímky v rovině, počet rozsazení, doplňování binárního čísla, tankování za letu a otáčející se
stolek se skleničkami.
Na rozmyšlenou zůstaly také úlohy (trochu těžší): minimální sada závaží pro rovnoramennou váhu, když chceme vážit předměty
o hmotnostech 1,2,...,n (rozmyslete variantu s kladením závaží pouze na jednu misku vah a variantu s kladením na obě misky) a velbloud vozící banány
(zajímavé je především obecné řešení úlohy tj. sestrojení funkcí, které vzdálenosti přiřazují maximální počet banánů do
této vzdálenosti dopravitelný a počtu banánů maximální vzdálenost, kam lze tento počet banánů dopravit).
Cvičení 17.10.2006
Domluvili jsme schůzku za účelem seznámení se s vývojovým prostředím Borland Pascal. Schůzka se bude konat
ve středu 25.10.2006 v počítačové laboratoři v Karlíně (místnost K10, vedle vchodu) od 12:20.
Probíraly se domácí úlohy zadané na minulém cvičení. Opakovali jsme asymptotické porovnávání funkcí a
dokazování správnosti algoritmu (zatím neúspěšně).
Cvičení 24.10.2006
Procvičovalo se porovnávání kvality algoritmů podle rychlosti (podle počtu vykonaných operací). Opakovali jsme
časovou složitost v nejhorším případě (počet kroků v nejhorším případě). Zmínili jsme i očekávanou časovou
složitost v průměrném případě. Zopakovali jsme asymptotické porovnávání funkcí (definice g∈O(f)) a
jeho využití při zařazení algoritmu do třídy podle časové složitosti (logaritmický, kvadratický čas ...).
Procvičili jsme důkaz konečnosti a parciální správnosti algoritmu na příkladu hledání NSD dvou přirozených čísel.
Na rozmyšlenou zůstala otázka, "jak dlouho může běžet program na počítači s konečnou pamětí" a konečnost algoritmu
za předpokladu jistého tvrzení (stejnoměrné a nestejnoměrné klesání ohodnocení konfigurace).
Pascalovská schůzka 25.10.2006
Společně jsme zkoušeli napsat program na sčítání velmi dlouhých přirozených čísel (stovky cifer). Při psaní a
ladění programu jsme předvedli základní možnosti vývojového prostředí Borland Pascal 7.0 (krokování
programu, sledování obsahu proměnných atd...). Samostatně pak každý psal a ladil program podle vlastního
výběru. Možnosti byly buď zkusit reprodukovat program na sčítání dlouhých čísel nebo napsat program, který
nalezne prostřední (vzhledem k uspořádání) ze zadaných tří čísel.
Cvičení 31.10.2006
Procvičoval se Pascal. Dělaly se základní číselné datové typy a základní prostředky pro řízení běhu
programu (if-then-else, for-do, while-do, repeat-until) na jednoduchých úlohách - druhá mocnina bez
násobení, druhá mocnina jen s přičítáním jedničky, nalezení největšího čísla z několika zadaných čísel
(strom if-then-else), výpočet n-tého Fibonacciho čísla, sčítání zlomků a/b+c/d=x/y, kde x/y nelze krátit.
Dále se procvičovaly úlohy na výpočet odmocniny (druhé, třetí) jen s použitím sčítání, odčítání, násobení a dělení
a převod zadaného čísla do zvolené číselné soustavy (dvojková, trojková, šestnáctková).
Cvičení 7.11.2006
Zmínili jsme několik témat na zápočtový program. Standardní termín pro odevzdání zápočtového programu
je začátek zkouškového období. Nejpozdější termín pro odevzdání zápočtového programu je
konec zkouškového období. Opakovaly se úlohy na převod čísel mezi různými číselnými soustavami a
počítání odmocniny jen s použitím +,-,*,/. Procvičovaly se pole - reprezentace matice, hledání sedlového prvku
(předvýpočet). Na rozmyšlenou zůstalo generování permutací (všech, pořadové číslo->permutace, premutace->pořadové číslo).
Ve zbývajícím čase jsme se věnovali ukázkám zápočtových (i nezápočtových) programů. Příští cvičení se bude konat v počítačové
laboratoři v Karlíně - cvičení bude spojeno s Pascalovskou schůzkou (čas 12:20-15:40).
Prodloužené cvičení v laboratoři 21.11.2006
Cvičení probíhalo od 12:20 do 15:40. Probírala se úloha násobení matic a zjišťování
souvislosti grafu založené na násobení matic. Každý úlohu implementoval a ladil na počítači. Přitom
se opakovaly Pascalovské konstrukce: pole, záznam, předávání parametrů hodnotou a odkazem. Zmiňovali
jsme také ladící prostředky breakpoint a watch.
Cvičení 28.11.2006
Cvičení neproběhlo moc zdárně. Udělali jsme příliš málo práce. Zkoumali jsme problém generování
všech možných permutací a jedné permutace dle pořadového čísla v lexikografickém uspořádání. Potom jsme
si neformálně (intuitivně) zavedli haldu v poli a rozmýšleli jsme vkládání prvku, odebírání nejmenšího
prvku a třídění pomocí haldy. Za domácí úkol je přemýšlet o postupu, jak nalézt posloupnost tahů koněm, aby
navštívil každé políčko šachovnice právě jednou a problém N královen na šachovnici NxN.
Cvičení 5.12.2006
Podrobně jsme sepsali program na práci s haldou (procedury pro vložení prvku, odebrání nejmenšího prvku).
U zkonstruovaného programu jsme zkoumali jeho časovou složitost (vložení O(log2N), odběr nejmenšího O(log2N)).
Poté jsme na základě operací s haldou navrhli třídící algoritmus (heap-sort) a provedli jsme jeho časovou analýzu (O(N log2N)).
Rozmýšleli jsme, jak abecedně setřídit telefonní seznam uložený v souboru. Dále jsme rozmýšleli několik úloh na
prohledávání stavového prostoru (přelévání vody, šachovnice) - zatím jen logicky. Těžší úloha na závěr: navrhněte
algoritmus, který najde algoritmus na řešení úlohy o vážení 12-ti kuliček pomocí rovnoramenné váhy (11 stejných, 1 jiná,
chceme určit jinou).
Na posledním předvánočním cvičení (tj. 19.12.2006) se bude psát písemka.
Cvičení 12.12.2006
Procvičovala se práce s řetězci a se soubory. Přehazování dvojice slov v rámci řetětce. Přehazování
dvojice slov v rámci souboru. Prohledávání stavového prostoru. Úloha na přelévání vody (nádoby 5 a 3,
chceme odměřit 4). Kreslení domečku jedním tahem.
Ve zbývajícím čase jsme se věnovali ve stručnosti věnovali některým příkladům. Diskutovali jsme vhodnost
binárních souborů pro úlohu přehození dvou řetězců v souboru (operace seek). Rychlost práce s diskem, vyrovnávací
paměti, zmínka o paměťové hierarchii podle rychlosti a velikosti (registry, cache, RAM, disková cache, disk, DVDčko).
Hra LIFE, popis pravidel a pracovního pole, výpočet nové situace podle pravidel. Pohybující se předměty ve hře LIFE
(kluzáky). Simulace počítače ve hře LIFE (stroj sestavený z kluzáků a jiných rostoucích shluků).
Příští cvičení (tj. 9.1.2007) bude prodloužené (čas 12:20-15:40) a bude se konat v počítačové laboratoři v Karlíně.
Nasimulujeme si praktický zápočtový test.
Prodloužené cvičení v laboratoři 9.1.2007
Proběhl trénink praktického zápočtového testu. Zároveň jsme opakovali prohledávání do hloubky a do šířky
- diskuse případů, kdy je vhodné jedno či druhé.