Programování 2 - cvičení - NMIN112


1. Úvodní informace

Uvítání :-) 

1.1 Představení cvičení a cvičícího

Každý kroužek má dvě dvouhodinová cvičení týdně – jedno teoretické a druhé praktické. 

Teoretické cvičení 
slouží k procvičování učiva z přednášky, řešení různých algoritmických problémů, diskusi o správnosti a efektivitě algoritmů. 
Studenti (na)učit algoritmus navrhnout, slovně ho popsat, vysvětlit ho, zdůvodnit jeho správnost, odvodit jeho časovou složitost - a to všechno ústně i písemně. 
Náplň teoretického cvičení navazuje na přednášku, ale můžete na něm řešit i jakékoliv jiné algoritmické problémy, které s učivem aktuálně probíraným na přednášce nesouvisejí. Na teoretickém cvičení se vůbec nepracuje na počítačích (ačkoliv jsou i tato cvičení rozvržena do počítačových učeben). 

Praktické cvičení 
přímo navazuje na výuku programování v zimním semestru a je do značné míry nezávislé na průběhu přednášky a teoretického cvičení. Obsahem praktického cvičení je zopakování a doplnění prostředků a nástrojů programovacího jazyka Python a praktické procvičení práce u počítačů při řešení úloh, tzn. psaní  a ladění programů. V  úlohách řešených na praktickém cvičení by se ovšem měli využívat a procvičovat také ty algoritmy a datové struktury, které jsme se učili na přednášce, takže určitá provázanost s přednáškou zde přeci jenom je. 


1.2 Informace z přednášky: https://ksvi.mff.cuni.cz/~topfer/

1.3 Orientační plán náplně přednášek v letním semestru:
- Algoritmy a jejich efektivita
- Základní algoritmy
- Třídění
- Základní datové struktury
- Spojové seznamy
- Rekurze, binární a obecné stromy
- Binární vyhledávací stromy, rekurzivní generování
- Grafy – reprezentace, procházení
- Grafové algoritmy
- Prohledávání stavového prostoru do hloubky a do šířky
- Algoritmus minimaxu, metoda Rozděl a panuj
- Dynamické programování
- K-tý nejmenší prvek, aritmetické výrazy.



2. Podmínky na zápočet 
Předmět NMIN112 je zakončen zápočtem a zkouškou. K účasti na zkoušce není zapotřebí předchozí získání zápočtu a dokonce to ani není obvyklé. Jednou z podmínek pro získání zápočtu je totiž vypracování zápočtového programu, což si mnoho studentů nechává až na prázdniny a zápočet pak dostanou třeba až v září. 
Podmínky zápočtu na Teoretické části cvičení - viz web cvičení: https://kam.mff.cuni.cz/~aston/.


3. Teoretické cvičení - Algoritmus a jeho složitost - hvězdičky. 

3.1 Algoritmus: pro některé problémy máme matematický popis, ty umíme zadat pc, "data jsou popisem a nastavením problému", intuitivní definice algoritmu (kuchařka, posloupnost instrukcí, ...), algoritmus jako transformace dat na data požadovaných vlastností, vlastnosti algoritmu (konečnost, korektnost, elementárnost, náročnost na zdroje, ...), neformální zavedení turingova stroje, jako teoretického matematického výpočetního modelu, "definice" algoritmu jako přepisovací funkce v TS, více různých algoritů pro daný problém, porovnání algoritmů; náročnost algoritmů na (různé) zdroje a zejména čas (elementární operace vs vteřiny) a prostor, v čem se měří a na čem závisí (délka vstupu), složitost algoritmu jako funkce, idea: určení náročnosti algoritmu na zdroje bez jeho puštění na konkrétních datech (a proč obecně nejde pustit alg na všech datech: nemáme je, nemáme dost času, ...)

3.2 Odhady složitostí konkrétních algoritmů - příklady Hvězdičky
(Průvodce labyrintem algoritmů, https://pruvodce.ucw.cz/)
idea: umíme určit přesně, umíme aproximovat přibližně, umíme učit (horní/dolní) mez