Jarní soustředění KSP 2013
Poznámky k přednáškám

Povinně dobrovolné přednášky

Základy programování (Michal, Jirka)

Na kurzu jsme se naučili základy programování jak po teoretické stránce, tak hlavně po stránce praktické a to v jazyce Python. Můžete si stáhnout o trochu novější verzi Portable Pythonu, než jsme používali.

1. přednáška
Úvod do jazyka, proměnné, definice a volání funkcí, while cyklus
2. přednáška
For cykly, pole a práce s nimi, modul Math, Eratosthenovo síto
3. přednáška
Slovníky (hashe), příklad s telefonním seznamem, rekurze, Fibonacci
4. přednáška
Pokračování příkladu s telefonním seznamem
5. přednáška
Celkové opakování, větší povídání o časové složitosti
6. přednáška
Praktický příklad: 25-2-5: Sbírání papírů

Základní algoritmy (Michal)

Předvádělo se třídění na několik způsobů (bublinkové, vkládáním, výběrem, sléváním, QuickSort). U QuickSortu jsem jenom naznačil, že existuje způsob, jak jej naprogramovat se skutečnou logaritmickou složitostí. Z QuickSortu jsme odvodili QuickSelect. Zde můžete najít popis zmíněného zatajeného triku. Dále jsem ukázal mocnění v logaritmickém počtu násobení (které můžete najít v naší kuchařce o teorii čísel). Nakonec jsme probrali interpretaci matematických výrazů jako stromečků, a ukázal jsem jejich postfixový zápis. Stihl se naznačit i algoritmus na převod mezi běžným (infixovým) a (počítačově pohodlnějším) postfixovým tvarem. Jeho popis můžete najít na anglické Wikipedii.

Algoritmy a jejich složitost (Folwar)

V této přednášce jsme si vysvětlili asymptotické porovnávání funkcí. Vysvětlili si složitost algoritmu a složitost problému, časovou složitost, paměťovou složitost, amortizovanou a průměrnou složitost. Ukázali jsme si dolní odhad složitosti třídění (v porovnávacím modelu, viz radix sort nebo bucket sort) a horní odhad složitosti Eratosthenova síta.

Materiály: Většinu informací lze nalézt v příslušné kuchařce KSP. Zmiňoval jsem se, že k složitosti přistupujeme nesmírně vágně, o něco formálnější přístup je v kapitole o složitosti Medvědových vznikajících skript. Pro Eratosthenovo síto jsme si ukázali odhad O(n log n), lepší odhad lze najít v Medvědově článku, kde se nachází i dva další principálně podobné důkazy.

Dokazování (Paulie)

Na příkladech jsme si ukázali různé druhy důkazů nepříliš těžkých vět, tedy důkaz přímý, sporem a matematickou indukcí. Dále jsme rozebírali, jak dokazovat správnost algoritmů, konkrétně na bublinkovém třídění, Euklidově algoritmu a hledání dvojice s daným součtem v setříděné posloupnosti.

Popis různých druhů důkazů včetně příkladů lze najít na stránkách s výukou logiky.

Algoritmizace

Herní algoritmy (Paulie)

Od algoritmu Minimax, který hledá nejlepší tah z dané pozice nějaké deskové hry podobné šachám, jsme se dostali k Alfa-beta ořezávání a probrali jsme i vylepšení tohoto algoritmu, konkrétně Iterativní prohlubování, Transpoziční tabulky a řazení tahů.

V loňském ročníku KSP jsme měli seriál mimo jiné o herních algoritmech. Alfa-beta ořezávání včetně svých vylepšení a další algoritmus najdete popsaný v kapitole dvě mé bakalářské práce.

Programovací jazyky a techniky

Programování v jazyce C# (Paulie)

Po probrání základů syntaxe jsme se dostali na úvod do objektově orientovaného programování v C#. Následující stránky se mohou hodit, ale možná existuje lepší zdroj (v angličtině určitě):

Stránky o .NETu, kde najdete seriál o C# (bohužel nedopsaný):
http://www.vbnet.cz/kategorie--12.aspx
Tutoriál k C# je i na Programujte.com:
http://programujte.com/clanky/24-c/
Podrobnějším zdrojem o C# a platformě .NET vůbec je MSDN:
http://msdn.microsoft.com/en-us/library/kx37x362.aspx

Matematické přednášky

Diskrétní matematika (Folwar)

Po krátkém úvaze o tom, co je diskrétní matematika, jsme se podívali na princip inkluze a exkluze. Rozšířili jsme si symbolický jazyk tak, abychom vůbec dokázali tento princip zapsat. Třemi způsoby jsme si jej dokázali a sami jste pak s jeho pomocí vyřešili slavný Problém šatnářky.

Materiály: Základním zdrojem k tématu jsou Kapitoly z diskrétní matematiky (J. Matoušek, J. Nešetřil), které nevyžadují žádné znalosti, jen nadšení. Doporučoval jsem ke zhlédnutí rozhovor s prof. Nešetřilem.
Přes šatnářku jsme nějak na chvíli sklouzli k tomu, že z české filmové klasiky určitě stojí za to vidět Světáky.

Teorie kombinatorických her (Paulie)

Začali jsme popisem, o jaké hry se zajímáme, jaké strategie se používají a argumentem kradení strategie. Pokračovali jsme nestrannými hrami a podrobně jsme rozebrali Nim. Pokračovali jsme úvodem do sčítání a ohodnocování her. Jako třešničku na dortu jsme si ukázali Conwayovu hru Game of Life.

V loňském ročníku KSP jsme měli seriál také o kombinatorické teorii her. Zdrojem k přednášce byl předmět Kombinatorická teorie her na MFF.

Knihy o této teorii:

Program Golly pro simulaci Game of Life.

Matematika náhody (Folwar)

V průběhu této přednášky jsme se pokoušeli zavést pravděpodobnost. Dále jsme řešili škálu úloh spadající pod geometrickou a podmíněnou pravděpodobnost, ukázali jsme si Bertrandův paradox. Dokázali jsme si Větu o úplné pravděpodobnosti a Bayesovu větu, v závěru jsme nahlédli jak výsledky získané těmito větami ověřit selským rozumem.

Materiály: Základním materiálem pro tuto přednášku byla sbírka zajímavých úloh prof. Anděla "Matematika náhody", velmi inspirujícím čtením jsou Dialogy o matematice (Alféd Rényi), jejichž jednou částí jsou Dopisy o pravděpodobnosti. Zavedení diskrétní pravděpodobnosti lze nalézt také v Kapitolách z diskrétní matematiky (J. Matoušek, J. Nešetřil).

Půlnoční přednášky

Půlnoční mapování mysli (Paulie)

Popsali jsme si, co jsou mapy mysli nebo také myšlenkové mapy, představili jsme si letmo program Freemind a pak jsme přešli k dalším technikám podporujícím kreativitu nebo sloužícím na řešení problémů.

Čerpal jsem především z těchto zdrojů: Knížka Myslet jako Leonardo da Vinci – původní zdroj k přednášce. Kromě myšlenkových map je tam popsána spousta zajímavých technik osobnostního rozvoje, ale je třeba ji brát trochu s rezervou (psal ji Američan). Bohužel je vyprodaná, ale snad půjde sehnat v knihovnách.

Zjistil jsem, že blog Workaholica (jistého středoškolského učitele), na němž jsem si toho dost přečetl, už nefunguje. Je ale zaarchivovaný.

Půlnoční teorie množin (Folwar)

Trochu jsme si povídali o motivaci zavedení teorie množin a o rozdílu mezi metajazykem a jazykem. Ukázali jsme si Russelův paradox (existence množiny všech množin). Hlavní částí přednášky bylo postupné přidávání axiomů Zermelo-Fraenkelovské teorie množina a sledování toho, jak nám postupně roste universum množin, které umíme zkontruovat. Skončili jsme tím, že z Russelova paradoxu se stala prostá věta o neexistenci množiny všech množin.

Materiály: Základním textem jsou skripta Teorie množin (B. Balcar, P. Štěpánek), nevím však, zda je to rozumné středoškolské čtení. Co velmi doporučuji je kniha Matematika (T. Gowers), která velmi přístupně vysvětluje třeba axiomatický přístup. Je psána v popularizačním duchu, ale nic nebagatelizuje, naopak vede k úvahám nad dost netriválními věcmi. O český překlad se postaral profesor Matoušek.

Programování pro Android (Michal)

Ukázali jsme si s minimální dávkou teorie vývoj aplikací pro Android. Chcete-li si to taky vyzkoušet, můžete si stáhnout balíček obsahující všechno potřebné. Můžete si zde také stáhnout zdrojový kód primitivních piškvorkek, na kterých jsme si vývoj předváděli.