PRM044 Programování I

přednáška 4.října odpadla - nezaregistroval jsem změnu rozvrhu omlouvám se studentům

přednáška paralelka Y - středa 12:20 posluchárna K1

seminář - skupina X/53 - rozvrženo úterý 15:40 posluchárna S1

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

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

Zápočet zapíše studentovi přednášející po té, co student úspěšně složí praktický test a přednášející dostane od vedoucího semináře zprávu, že student splnil všechny podmínky ze semináře.

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.
  
  K zápočtovému programu je potřeba vytvořit smysluplnou dokumentaci.

Praktický test

Obecně

Přihlašování k testům

K praktickým testům se studenti přihlašují pomocí studijního informačního systému.
Na praktický test se můžete přihlašovat až do dne, kdy se termín koná, odhlašovat zpravidla do tří dní před termínem (abyste zbytečně neblokovali kapacitu ostatním). Po uvedeném termínu je možné se odhlásit bez propadnutí termínu jen ze skutečně vážných důvodů (nemoc) mailem zkoušejícímu.

Praktické testy se konají v posluchárně S1 ve 4. patře budovy na Malostranském náměstí 25, která se během zkouškového období přemění v počítačovou laboratoř. Termíny jsou po celé zkouškové období jsou vždy ve středu a v pátek (s výjimkou posledního týdne, kdy je termín místo pátku již v pondělí 13. února). V jednom dni mohu vypsat až tři termíny (od 8:00, 13:00 a 17:15 hodin) po 20 studentech. Budu je však vypisovat postupně, jak o ně bude zájem. Termíny nyní uvedené v rozpisu jako fiktivní s kapacitou 0 budou otevřeny jakmile budou ostatní termíny v daném dni obsazeny. Pokud vypsané termíny v některém z týdnů nebudou stačit, vypíši další. Tyto změny budu dělat sám, pokud bych si však zaplnění včas nevšiml, můžete mne na potřebu otevření resp. vypsání dalšího termínu upozornit mailem.
V laboratoři bude o dva počítače více - jsou rezervovány pro harwarové poruchy. Můžete tedy na termín přijít i když nejste přihlášeni. Bude-li volný počítač, budete moci test složit. Přihlášeným studentům se počítač rezervuje nejdéle 5 minut po plánovaném začátku testu.

Termínů ve zkouškovém období je tedy dostatek. Naopak během přednášek v únoru a březnu o ně může být (vzhledem ke kapacitě laboratoří) nouze - mohu však garantovat jeden pokus pro každého. Ve vlastním zájmu se snažte zapsat si test tak, abyste v případě neúspěchu mohli složit i první opravu ještě během zkouškového období. Termíny v posledním týdnu jsou rezervovány pro opravné pokusy.

Pokud by tato pravidla měla v konkrétním případě důsledky jsoucí v rozporu se zdravým rozumem, ozvěte se mi mailem nebo jiným vhodným způsobem. Pravidla nejsou sama sobě účelem, ale "jen" nutným organizačním opatřením pro efektivní a co nejspravedlivější distribuci termínů.

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 (viz). 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í).

Student musí svůj program předvést, vysvětlit jeho funkci, případně být schopen ho v reálném čase jednoduše modifikovat. Hodnotí se nejen funkčnost vytvořeného programu, ale i to, jak je program navržen a naprogramován. Není při tom vyžadována (časová) optimalizace algoritmu. Stačí, nejsou-li ani algorimus ani jeho implementace "vysloveně hloupé". Vzhledem k omezenému času se nepožaduje, aby byl program komentován (i když komentáře vytvářené současně s programemem vám mohou práci na programu podstatně zjednodušit i zrychlit).
Spolu s programem musí student předat zkoušejícímu i dostatečný počet testovacích dat, na kterých funkčnost programu testoval. Pokud je vstup/výstup programu ze/do souboru, pak předá tyto soubory na disku, pokud program komunikuje z konzole, pak papír, na který opsal vyzkoušené vstupy a jim odpovídající výstupy, Součástí hodnocení výkonu studenta je i způsob, jak navrhl testovací data. Data by měla program vyzkoušet jak v typických tak i v anomálních situacích. Správnost výsledku by měla být alespoň pro některá vstupní data nějak jednoduše a na programu nezávisle ověřitelná. Lze jen doporučit navrhovat zkušební data současně s výběrem algoritmu, tedy dříve než se začnete zabývat detaily vlastního programu.
Při návrhu programu myslete na to, aby jeho spuštění netrvalo zbytečně dlouho. Pokud je např. při každém spuštění programu potřeba zadat 20 čísel z klávesnice, můžete tak při opakovaném spouštění programu ztratit neúnosně mnoho času.

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. Případné potřebné informace o detailech programovacího jazyka student může zjistit z helpu Borland Pascalu.

Pro úspěšné složení testu jsou potřeba m.j. následující znalosti:

• 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í, breakponty, 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. maticové operace a jejich implementace
  8. použití rekurze
  9. backtracking (prohledávání do hloubky)
  10. algoritmus vlny (prohledávání do šířky)
  11. konstrukce minimální ekvivalence zadané (některými) dvojicemi ekvivalentních prvků

Poznámky k dosavadním termínům testů

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 já).
2. Pokud neovládáte dobře ladící prostředky, které Borland Pascal poskytuje, velmi 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 vyskytlo několik studentů, kteří řešili jinou úlohu. Nebude-li Vám něco jasného, zeptejte se. Dodržte způsob vstupu a výstupu, na kterém se při zadávání úlohy dohodneme
4. Nejprve promyslete algoritmus a teprve pak začněte bušit do klávesnice
5. 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.

Termíny testů po zkouškovém období

Do konce zkouškového období se o složení praktického testu pokusilo 155 studentů, z nich 78 uspělo. Ze 67 studentů, kteří se pokusili a neuspěli, jeden vyčerpal všechny tři pokusy, 34 vyčerpalo dva pokusy a 32 vyčerpalo jen jeden pokus.

Každý student má právo na ještě jeden pokus po zkouškovém období. Z výše uvedených čísel však vyplývá, že s velkou pravděpodobností budou moci všichni studenti vyčerpat všechny pokusy, které jim zbyly. Vyhražuji si však právo regulovat zápisy druhého pokusu studenta v období po zkouškovém období. Situaci studentů, kteří se z vážných důvodů na test dosud ani jednou nezapsali budu řešit individuálně, je třeba, aby se se mnou co nejdříve spojili.

Po zkouškovém období jsou vypsány čtyři termíny po 24 studentech (ve skutečnosti je počítačů 25) vždy v pátek od 16 hodin v nové laboratoři v přízemí budovy na MS hned vlevo za vchodem. Na tyto termíny se můžete zapisovat od 17.února, z těchto termínů se nelze odhlásit.

Definitivní výsledky praktických testů:
pokusilo se 159 studentů, uspělo 102 studentů, tj. 64%

Sbírka příkladů

Vzhledem k tomu, že přibývá studentů, kteří se se programováním poprvé seznamují až na MFF, je účelné obrat "středně obtížná úloha" nějak vysvětlit. Proto jsem vytvořil k praktickým testům krátkou sbírku příkladů. Jde o její první verzi, druhá modifikovaná a definitivní bude přístupná nejpozději 8.ledna.

Pokud student má základní programátorské schopnosti, umí ladit programy a myšlenkově ovládl algoritmizaci úloh sbírky, neměl by mít se složením praktického testu potíže. Rozhodně to však neznamená, že student nutně musí dostat u testu přesně některou z úloh sbírky.

Vyřešení úloh sbírky samo o sobě nesmí být cílem. Je "jen" jedním z dobrých prostředků k dosažením skutečného cíle - naučit se programovat.

Literatura

V podstatě nebudete žádnou potřebovat, můžete si vystačit s poznámkami z přednášek a seminářů

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

K dispozici jsou tři přřekladače

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 bude používán překladač Borland Pascal verze 7 v prostředí operačního systému DOS.
Počítače v laboratoři budou odpojeny od sítě.
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 mohou vyskytnout 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.

Především v letním semestru mohou studenti použít k vytvoření zápočtového programu i programovací systém Delphi. Výhodou může být možnost vytvořit plnohodnotnou aplikaci pod MS Windows včetně grafický výstupů. Nevýhodou je složitost systému.
Proto nelze doporučit použití systému Delphi těm, kdo jej již neznají, v zimním semestru. Systém má režim, který umožňuje vytvářet "konzolové aplikace".