NPRM044 Programování I zimní semestr 2009/10

přednáška paralelka X - přednášející Rudolf Kryl - středa 8:10 posluchárna F1
přednáška paralelka Y -přednášející Martin Pergel - čtvrtek 9:00 posluchárna F1
Můžete navštěvovat kteroukoli paralelku, výuka v obou bude ekvivalentní. Není však rozumné střídat různé paralelky, protože se výuka v nich může "rozejít" a také mohu použít odlišné příklady.
seminář - skupina 57 - úterý 17:20 posluchárna K11

O předmětu

Hlavním cílem předmětu je naučit studenty algoritmickému myšlení a základním programátorským dovednostem. Přednáška je vedena na bázi programovacího jazyka Pascal. Programovací jazyk však není cílem, ale prostředkem. V prvním semestru probereme v podstatě celý jazyk mimo prostředků pro dynamickou alokaci paměti a objektového programování.
V praktickém testu musí studenti prokázat schopnost vytvořit a odladit v daném čase program řešící středně obtížnou úlohu.

Systém CodEx

Studenti budou mít možnost testovat automaticky správnost svých programů odkudkoli z internetu pomocí systému CodEx. Systém bude užíván na cvičeních, není primárně určen ke kontrole studentů, ale k tomu, aby studenti získali zpětnou vazbu. Přesto však vedoucí skupiny může předepsat vyřešení jistého počtu úloh v tomto systému jako podmínku pro získání zápočtu. Typicky bude používán k odevzdávání domácích úkolů, jejichž řešením má být zdrojový text programu. Systém CodEx lze použít i pro praktické testy na cvičeních.
Proto je třeba, aby se všichni studenti zaregistrovali do systému jakmile to půjde.
Uděláte to na stránce. Login i heslo udáváte tak, jako v SISu.

Rozdělení studentů na cvičení

Student by měl navštěvovat to cvičení, které je rozvrhem určeno jeno skupině. Pro úplnost uvádím přehlednou tabulku. (V případě kolize s rozvrhem, věřte spíš rozvrhu, mohl jsem se uklepnout. Uvádím tabulku jen proto, že si někteří studenti stěžovali, že nemohou "svůj" rozvrh najít.)

Pochopitelně lze v odůvodněných případech chodit na cvičení s jinou skupinou (případně i jiné paralelky). Musíme ale zachovat několik pravidel:

1. každý student má právo chodit na cvičení se skupinou, do které byl zařazen
2. žádná skupina nesmí být příliš velká - maximum je dejme tomu 27, skupinu přes 30 již nelze připustit
3. žádná skupina by neměla být příliš malá - pokles pod 15 je již přílišným přepychem
4. o vašem přijetí do jiné skupiny rozhoduje vedoucí té skupiny, kam chcete přejít (řídí se při tom pravidly 1 a 2), vedoucímu skupiny, ze které odcházíte, byste to měli dát vědět

Nejpozději na konci třetího týdne výuky by mělo být zcela jasné, kdo do jaké skupiny chodí, další přestupy již nebudou umožněny. Speciálně byste se měli nějak ozvat vedoucímu Vaší skupiny i v případech, že nyní nemůžete do školy např. kvůli nemoci chodit, aby s Vámi počítal.

Pokud by se ukázalo, že došlo k přílišným nerovnoměrnostem, můžete být již udělený souhlas se změnou skupiny zrušen.

Informace pro studenty kombinovaného studia

Studenti kombinovaného studia nemají povinnost navštěvovat výuku. Mohou se však sami rozhodnout, že budou navštěvovat některý ze seminářů a získají tedy zápočet od příslušného cvičícího. Pokud se tak nerozhodnou, domluví si náhradní podmínky udělení zápočtu s některým z přednášejících. Vřele Vám však doporučujeme alespoň občasnou návštěvu některého ze cvičení i kdybyste ho nemohli navštěvovat pravidelně. Získáte tak zpětnou vazbu.

Vážíme si Vašeho odhodlání doplnit si i při jiných povinnostech kombinovaným studiem znalosti i dovednosti v matematice. Budeme se snažit Vám ve Vašem úsilí pomoci. Prvním takovým krokem je

Hromadná konzultace, která se koná v sobotu 24.října od 9:30 v posluchárně S3 ve třetím patře budovy na Malostranském náměstí 25.

Předpokládaný program (bude přizpůsoben zájmům a úrovni publika):

• 9:30 - 12:00 Algoritmy.
  Pojem algoritmu, jednoduché příklady algoritmů, správnost algoritmů a metody důkazu jejich správnosti, složitost algoritmů, pojem asymptotické složitosti
• 12:30-15:00 Základy jazyka Pascal, překladače, ladící prostředky, systém CodEx

Další dvě hromadné konzultace se konají 5.prosince 2009 a 16.ledna 2010 v posluchárně S3 opět vždy ve dvou blocích 9:30 - 12:00 a 12:30-15:00. Náplň bude přizpůsobena potřebám a zájmům přítomných studentů.

Koordinaci práce se studenty kombinovaného studia má na starosti přednášející paralelky Y Mgr Martin Pergl, PhD. Další informace najděte na jeho stránce pro kombinované studenty.

Úlohy v Codexu berte především jako trenažér, který Vám samým umožní kontrolu jak na tom jste, nikoli jako nástroj naší kontroly. Přesto však může být stanoven nějaký počet bodů, které budete muset dosáhnout (domluvíme se na hromadné konzultaci). Uvědomte si, že samotná správnost řešení úlohy v CodExu sama o sobě nic nezaručuje, mohli jste "vynaleznout" chybu, kterou autor úlohy nepředpokládal, nebo úlohu vyřešit velmi nešikovně. Systém mi umožňuje vidět řešení, která jste odevzdali, můžeme se jim tedy věnovat na případných konzultacích.

Podmínky pro získání zápočtu

Zápočet zapisuje vedoucí semináře po té, co student splnil všechny podmínky ze semináře a vedoucí semináře dostane od přednášejícího zprávu, že student úspěšně složil praktický test. Pokud je vedoucím semináře student (vyššího ročníku), zapisuje zápočet do indexu na základě informace od něj přednášející.

Pro studenty kombinovaného studia, kteří nenavštevovali žádný ze seminářů, plní roli vedoucího semináře přednášející.

Podmínky ze semináře :

• Aktivní účast na seminářích a průběžné znalosti během semestru.
• Vytvoření a odladění zápočtového programu. Zápočtový program byste zpravidla měli odevzdat do konce zkušeního období, posledním termínem k odevzdání zápočtového programu je konec března (musí jít o v podstatě hotový program, vedoucí semináře může studentovi dát další lhůtu (zpravidla ne více než dva týdny) k odstranění závad či dodělání dokumentace.
  
  K zápočtovému programu je potřeba vytvořit smysluplnou dokumentaci.

Praktický test

Obecně

Přihlašování k jednotlivým termínům praktických testů

Studenti se ke skládání praktických testů přihlašují ve studijním informačním systému jako k zápočtu z předmětu NPRM044.
Zapisování bude možné od 6.ledna 2010. Termíny budou v pondělí a ve čtvrtek, vždy v laboratoři SW2, která se nalézá v přízemí budovy fakulty na Malé straně, hned vlevo za vrátnicí. Nemusíte mít účet v laboratořích na MS, při testech nebudete mít přístup na internet ani k poště.
V laboratoři je 25 počítačů, termíny vypisujeme pro 23 studentů. Pokud bude volno, budou moci praktický test skládat i studenti, kteří na daný termín nebyli přihlášeni. Přihlášeným se místa v laboratoři rezervují nejdéle 10 minut po plánovaném začátku testu.
Termínů budete mít během zkouškového období dostatek, budeme je však otevírat postupně, jak se budou plnit okolní otevřené termíny. Dosud neotevřené termíny jsou označeny jako "zatím fiktivní". V případě nutnosti můžeme některé týdny přidat i termíny další.
Přihlašujte se až když budete skutečně rozhodnuti, že na daný termín skutečně chcete jít, nezneužívejte možnost odhlašování - blokovali byste kapacitu svým kolegům. Pokud budete nemocni a nestačíte se již z termínu odhlásit, omluvte se mailem (pokud možno nejpozději v den konání termínu). Mail s omluvou pošlete na adresy obou přednášejících
Respektujte přednostní práva na některé termíny - například termíny v posledním týdnu zkouškového období budou vyhrazeny pro druhé resp. třetí pokusy.

Pokud byste měli potíže se zaplněním termínů, můžete otevření fiktivních urgovat mailem (pošlete ho jako urgentní s předmětem "termíny PRM044") nebo osobně.

Během zkušebního období se o složení testu pokusilo 154 studentů, z toho 99 ho úspěšně složilo. Celkem tedy zbývá 55 studentů, kteří o složení testu měli zájem a dosud se jim to nepovedlo. Budou tedy pravděpodobně stačit 3-4 termíny s kapacitou 23. Ke správnému odhadu jejich počtu nám slouží průzkumný termín 28.2., pokud chcete tento semestr ještě praktický test skládat, přihlašte se na tento průzkumný (reálně neexistující) termín.

Termíny po zkouškovém období budou vypsány po 1.březnu 2010.

Žádné z pravidel není samo sobě účelem. Pokud by v konkrétním případě mělo důsledky příčící se zdravému rozumu, lze pochopitelně udělat výjimku (Dobrá pravidla mají ještě lepší výjimky). Nestyďte se v takovém případě o ní požádat - nanejvýš neuspějete.

Požadadavky a pokyny k vypracování testu

Při testu má student prokázat, že ovládl základy algoritmizace a praktické dovednosti nutné k vytvoření a odladění programu na počítači.

Během 3 hodin musí student samostatně sestavit a odladit na počítači program řešící středně obtížnou úlohu. Pracuje se v prostředí Borland Pascal 7.0. Úlohy jsou formulovány tak, aby nevyžadovaly použítí "pokročilejších" částí jazyka Pascal, které budeme probírat až v druhém semestru (dynamicky alokované proměnné, datové soubory, objektové programování), můžete je ale použít pokud je znáte.

Pokud zkoušející zjistí, že předávaný program nefunguje správně, může studentovi dát možnost program opravit. Zpravidla však student nedostane takovou možnost více než jednou.

Při práci na testu nejsou povoleny žádné pomůcky (knihy, zápisky z přednášek, flash disky a jiná paměťová media, mobilní telefony, ...). Případné potřebné informace o detailech programovacího jazyka student může zjistit z helpu Borland Pascalu. Student si pochopitelně může dělat poznámky na papír - je to dokonce doporučeníhodné .

• Znalost programovacího jazyka Pascal, resp. Borland Pascal v rozsahu:
  jednoduché a strukturované datové typy (čísla, znaky, typ boolean, pole, záznamy, množiny, znakové řetězce), jednoduché a strukturované příkazy (:=, if, while, repeat, for, case, with), práce s textovými soubory, procedury a funkce, separátní překlad a programové jednotky - unity, lokalita identifikátorů, předávání parametrů, rekurze.
• Aktivní znalost integrovaného prostředí Borland Pascal verze 7.0.
  (editor, překlad, výpočet, trasování, breakpointy, sledování hodnot proměnných (watches) atd.).
• Ovládnutí konkrétních jednoduchých algoritmů a programovacích technik, např. :
  1. Eukleidův algoritmus
  2. Eratosthenovo síto
  3. Hornerovo schéma
  4. práce v pozičních číselných soustavách
  5. aritmetika s vyšší přesností ("dlouhá čísla")
  6. algoritmy vyhledávání v poli (binární, zarážka)
  7. použití rekurze
  8. backtracking (prohledávání do hloubky)
  9. algoritmus vlny (prohledávání do šířky)
  10. konstrukce minimální ekvivalence zadané (některými) dvojicemi ekvivalentních prvků (faktorová množina)
  11. jednoduché algoritmy pro práci s permutacemi
      zjištění pořadového čísla permutace, zjištění permutace z jejího pořadového čísla, přímé nalezení následující permutace
      (vše v lexikografickém uspořádání)
  12. vyčíslování aritmetických výrazů
  13. zarovnávání vstupního textu "do bloku"

Poznámky k testům

1. Je naprosto nutné, abyste prakticky zvládli vstup a výstup do textových souborů. Některé úlohy to výslovně vyžadují, většinu bez toho nelze v krátkém čase odladit. Při tom nejde vůbec o nic složitého. Pokud se Vám to nepodaří zvládnout samostatně, nestyďte se vyhledat pomoc někoho, kdo programovat umí (např. cvičící nebo přednášející).
2. Pokud neovládáte dobře ladící prostředky, které Borland Pascal poskytuje, velmi tím snižujete pravděpodobnost úspěchu.
3. Přečtěte si zadání. Je to většinou jen několik vět, přesto se občas vyskytne student, který řeší jinou úlohu. Není zcela jasné, zda má být skutečnost, že "neumí číst", přitěžující či polehčující okolností.
   Nebude-li Vám v zadání něco jasného, zeptejte se.
4. Dodržte způsob vstupu a výstupu, na kterém se při zadávání úlohy dohodneme
5. Nejprve promyslete algoritmus a teprve pak začněte "bušit do klávesnice".
6. Při návrhu programu předpokládejte, že v něm může být chyba.
   Navrhujte ho proto tak, abyste ji mohli jednoduše odhalit.
7. Dodržujte při psaní testů "pravidla fair play", tím nám umožníte, abychom jejich dodržování nemuseli vynucovat "násilím".

Literatura

1. P. Töpfer: Algoritmy a programovací techniky
   Prometheus Praha 1995
   Pěkná knížka, ve které najdete většinu algoritmů, které na přednášce probereme. Algoritmy jsou zpravidla uvedeny i s důkazem správnosti a odhadem složitosti. Většina znich je dovedena až do stádia programu v Pascalu. Knížku oceníte především při přípravě ke zkoušce v letním semestru.
2. P. Satrapa: Pascal pro zelenáče
   Neokortex Praha 2000
   Svižně napsaná knížka o programovacím jazyku Pascal
3. N. Wirth: Algorithms + Data Structures = Programs
   Prentice Hall Englewood Cliffsů; New Jersey 1975
   slovenský překlad N. Wirth: Algoritmy a štruktúry údajov
   Alfa, Bratislava 1989
   Klasická učebnice programování dodnes neztratila svúj půvab. Dnes poslouží především jako učebnice algoritmů.

Překladače Pascalu

1. Borland Pascal verze 7 - "starý, ale osvědčený" překladač
2. Free Pascal - volně šiřitelný, pracuje jak pod OS Windows, tak pod OS Unix
3. Delphi - de facto jde o překladač jiného jazyka navazujícího na Pascal

Při praktických testech a na cvičeních bude používán překladač Borland Pascal verze 7 v prostředí operačního systému DOS.
Důvodem použití tohoto překladače na praktické testy je především ověřená funkce helpů a ladění. Nevýhody plynoucí z toho, že jde přece jen o starší program, se v úlohách, které se vyskytnou v praktických testech, prakticky nemohou projevit.
Tento překladač může pracovat i v prostředí Windows - např. pro ladění zápočtových programů.

Pro zápočtové programu můžete použít i překladač Free Pascal. Má několik výhod:

• Je volně k dispozici na síti
• Může pracovat jak pod OS Windows, tak pod OS Unix
• Je modernější, proto v něm neplatí některá omezení Borland Pascalu.
  Tato omezení se však na úlohách praktických testů ani na typických zápočtových programech zimního semestru neprojeví.
• Může pracovat v režimu, ve kterém je téměř úplně kompatibilní s Borland Pascalem.