Programování II (PRM045 - Matematici)
 |
Cvičení se koná každé úterý od 15:40 v učebně K8 (Karlín, přesunuto z původní K7), 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í 20.2.2007
Pro získání zápočtu je vyžadována aktivní účast na cvičení, napsání 2 až 3 zápočtových písemek
vytvoření zápočtového programu, který bude nutno odprezentovat cvičícímu a dalším účastníkům prezentace. Procvičovali jsme
reprezentaci aritmetického výrazu pomocí stromového schématu, vyhodnocování hodnoty výrazu. Efektivita vyhodnocování
pro více proměnných, kde některé proměnné se mění jiné ne. Dijkstrův algoritmus nad maticí sousednosti. Hledání tranzitivního, reflexivního a
symetrického uzáveru relace zadané výčtem dvojic prvků v relaci.
Cvičení 27.2.2007
Procvičovaly se ukazatele. Znázornění, jak vypadá situace v paměti. Rozdíl mezi statickou proměnnou a dynamicky
alokovanou. Jednosměrný lineární spojový seznam - operace vyhledání prvku, vložení prvku na konec, vložení prvku za
zvolený prvek. Rychlé opakování práce se soubory, různé způsoby otevření souboru. Úloha na nalezení zadaného slova v
textovém souboru. Nabídl jsem konzultaci k praktickému testu, možnost konzultace však platila vždy. Na rozmyšlenou
zůstaly dvousměrné spojové seznamy - operace vyhledání, vložení na konec, vložení na zvolené místo, vymazání prvku.
Cvičení 6.3.2007
Pokračování v práci se seznamy. Dvousměrný spojový seznam - výpis, vložení na zvolené místo, vymazání prvku, setřídění
(zůstalo za domácí úkol). Jednosměrný spojový seznam - otočení, dělali jsme dvě varianty. Krátké pojednání o čase vykonávání
různých příkazů (přiřazení rychlé, alokace paměti pomalá, ...). Odbočka - určení deseti nejčastěji se vyskytujících slov
v textovém souboru. Výrazový strom z minula pomocí ukazatelů.
Cvičení 13.3.2007
Binární stromy - výpis (jednoduchý a strukturovaný), vložení prvku na místo listu, odebrání listu, odebrání vnitřního vrcholu (pospojování zbylých stromů).
Binární vyhledávací stromy - vyhledání prvku. Úloha na nalezení deseti nejčastěji se vyskytujících slov v souboru (počet různých slov v souboru je
omezen na 1000, velikost souboru omezena není). Reprezentace grafu pomocí ukazatelů - hranám chceme přiřadit čísla.
27.3.2007 se bude psát zápočtová písemka. Náplní písemky bude vše, co se do té doby probere (včetně látky z přednášky).
Cvičení 20.3.2007
Binární vyhledávací stromy - vyhledání prvku, vložení prvku, vymazání prvku, vymazání intervalu. Diskuse složitosti
operací. Vliv pořadí vkládaných prvků na výsledný tvar stromu a na složitost operací. Jak tento problém obejít - vyvažování pomocí rotace.
Úloha z ACM-ICPC na mobilní síť - hledání cesty mezi dvěma městy takové, že počet vysílačů, ke kterým se mobilní telefon
během cesty připojí, je co nejmenší (telefon je vždy připojen k nejbližšímu vysílači). Inkrementální (pouze přidáváme) reprezentace grafu.
Cvičení 27.3.2007
Psala se zápočtová písemka. Na následujícím odkazu je její zadání.
Cvičení 3.4.2007
Opakování algoritmů vnitřního třídění. Detailní implementace algoritmu heap-sort. Úloha ze soutěže
ACM-ICPC na konstrukci kvadrantového stromu pro zadaný obrázek. Opakování dolního odhadu
složitosti třídění založeném na porovnávání.
Cvičení 10.4.2007
Pokračování v úloza na kvadrantové stromy. Konverze ASCII obrázku na kvadrantový strom a naopak.
Detailní opakování třídícího algoritmu quick-sort. Analýza časové složitosti v nejhorším případě s
ohledem na kvalitu výbreu pivota. Úloha na hledání nejlevnějšího autobusového spojení: v souboru je
seznam měst (jeho velikost je omezena jen velikostí paměti) a seznam autobusových spojů (jedno město,
druhé město, cena, velikost tohoto seznamu je opět omezena jen velikostí paměti), úkolem je najít
nejlevnější cestu (s přestupy) ze zadaného počátečního města do zadaného cílového.
Cvičení 17.4.2007
Úloha na nalezení nejlevnějšího autobusového spojení. Úloha na nelezení cesty pro tlustého obra v
lese. Tlustý obr vypadá při pohledu shora jako kruh o jistém poloměru. Pohybuje se v lese, přičemž
stromy můžeme nahlížet jako body v rovině. Jsou-li stromy příliš blízko u sebe, obr mezi nimi (kvůli
své tloušťce) neprojde. Úkolem je odpovědět na otázku, zda se obr za těchto podmínek může dostat z
jednoho místa do jiného místa. Úloha na nalezení nejlevnějšího oplocení lesa. Plot se staví ze dřeva
z pokácených stromů. Chceme oplotit celý les a přitom na plot spotřebovat co nejméně stromů.
Cvičení 24.4.2007
Opakování vnějšího třídění. Dokončování úloh na hledání cesty pro tlustého obra v lese (různé varianty
řešení - algoritmus BUG, algoritmus založený na nakreslení grafu průsečíků kruhů). Úloha na oplocování
lesa, diskuse složitosti úlohy, rekurzivní prohledávání všech možných řešení s tím, že si stále pamatujeme
nejlepší dosud nalezené řešení. Na předposledním cvičení tj. 15.5.2007 se bude psát zápočtová písemka.
Cvičení 15.5.2007
Psala se druhá zápočtová písemka. Na následujícím odkazu je její zadání.
Cvičení 22.5.2007
Diskuse nad písemkou. Navrhl jsem jisté řešení založené na modifikaci Dijkstrova algoritmu. Toto řešení se však
ukázalo jako zásadně chybné (protipříklad nalezl pan Orel). Bude-li mít někdo ze studentů zájem řešení
ještě jednou zkonzultovat, můžeme se domluvit mailem. Dále jsme opakovali dynamické programování. Úloha o
násobení matic - je dána posloupnost matic, chceme zjistit jejich soucin. Úkolem je nalézt uzávorkování posloupnosti
matic takové, že počet operací sčítání a násobení je nejmenší možný.
|
Copyright © 2003-2014 |
|