IV104 Seminář řešení programátorských úloh

Cíle

Motivační citáty:
- Mysl není nádoba, kterou je potřeba naplnit, ale oheň, který je potřeba zapálit. (Plutarchos)
- Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. (Brian W. Kernighan)
- Premature optimization is the root of all evil. (Donald Knuth)
- To iterate is human, to recurse divine. (L. Peter Deutsch)
- Most of you are familiar with the virtues of a programmer. There are three, of course: laziness, impatience, and hubris. (Larry Wall)
Hlavní cíle semináře jsou:
- zopakování metod návrhu algoritmů, procvičení jejich použití
- procvičení programování, získání programátorské zběhlosti
- trénink "soft skills": práce v týmu, komunikace,
- rozvoj myšlení, schopnosti řešení problémů, ...
Kromě toho je cílem semináře částečně též příprava a výběr soutěžících na soutěž ACM ICPC, která probíhá na podzim.

9 trojhodinových seminářů.
Většina seminářů bude věnována nějakému specifickému tématu (viz předběžný program níže).
Semináře se skládají z "teoretických" a "programátorských" částí.
V "teoretické" části semináře se stručně probírají základní poznatky vztahující se k danému tématu (základní algoritmy, jejich složitost, ...) a také příklady s papírem a tužkou (případně příklady "na živo").
V "praktické" části semináře se programují různé příklady související s daným tématem. Programování probíhá různou formou (individuálně, skupinově, na krátký čas, s povinnou teoretickou přípravou, ...).
Prerekvizity: znalost alespoň 1 programovacího jazyka na rozumné úrovni (hodí se znalost C či C++, ale není úplně nezbytná), znalost základních algoritmů.
Budou domácí úlohy, které budou většinou spočívat v dodělání/zdokonalení výtvorů ze semináře.
Průběžně během semestru bude probíhat soutěž. Do soutěže se budou započítávat příklady programované v rámci semináře a domácí úlohy.
Zápočet je za snahu během semestru: kdo bude v bodované soutěži výrazněji pozadu, bude muset na konci splnit extra dávku domácích úkolů.

Na seminář se chodí včas!
Pokud není řečeno, že máte pracovat s počítačem, tak s počítačem nepracujete.
Pokud pracujete s počítačem, tak pracujete na zadaných úkolech. Seminář zejména není určen k vyřizování pošty.
Z Internetu je dovoleno používat pouze jako dokumentaci k programovacímu jazyku. Pokud není explicitně řečeno jinak, tak není povoleno vyhledávat řešení, náměty, informace, rady ...
Na seminář se chodí včas!

(Program se může mírně změnit v průběhu semestru.)

Termín	Téma
1. týden (22. 2.)	uvodní miš-maš
2. týden (29. 2.)	metody návrhu algoritmů: přehled
4. týden (14. 3.)	dynamické programování
5. týden (21. 3.)	rekurze I
7. týden (4. 4.)	rekurze II
8. týden (11. 4.)	hrubá síla a heuristiky
10. týden (25. 4.)	geometrické algoritmy
11. týden (2. 5.)	grafy
12. týden (9. 5.)	závěrečný miš-maš

Bude průběžně zveřejňováno.

SVG:

Fraktály:

Bez podkladů.

Zadání (s chybou v ukázkovém řešení úlohy Lampy)

dfs.cc
dfs.py

input1
input2
input3
input4
input5

bludiste1
bludiste2
robot1
robot2

Jméno	Součet	Úvod	Přehled	DP	Rekurze	Robotanik	Fraktály	Hry	Hry DÚ	Geom.	Grafy	DÚ grafy	Závěr
Klučár, Marek	255	30	30	24	30	0	24	26	0	28	25	5	33
Abaffy, Matúš	251	24	26	25	30	17	30	24	0	23	25	0	27
Kučera, Martin	221	19	25	26	30	0	26	26	0	22	25	0	22
Sloup, Petr	216	20	25	26	27	13	30	26	0	28	0	0	21
Čadek, Pavel	216	23	20	24	27	9	22	24	0	21	25	0	21
Kadlec, David	204	16	20	22	21	6	22	23	18	17	16	0	23
Janík, Richard	199	20	20	25	15	11	26	21	0	17	20	0	24
Vraník, Milan	196	26	20	22	16	10	15	23	0	23	20	0	21
Zmrzlý, Adam	170	16	20	24	16	4	15	22	15	22	16	0	0
Keda, Michal	169	16	20	18	21	7	20	22	0	15	20	0	10
Gazárek, Jiří	154	20	20	0	0	9	20	22	20	21	0	0	22
Liška, Martin	151	0	26	25	0	5	0	21	0	28	25	0	21
Kolařík, Matouš	149	20	20	18	15	8	15	22	0	15	16	0	0