Programování 2 - cvičení - NMIN112 1. Úvodní informace 1.1 Představení cvičení 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 Předpokládané znalosti z Programování 1 ze zimního semestru vyučovaného v Pythonu: - instalace Pythonu, IDLE, Python jako kalkulačka - proměnné a výrazy, operace s čísly, relace a logické spojky - struktura programu – příkazy input a print, indentace, komentáře - příkaz if (zanořování, elif, else), cyklus while (včetně else) - základní použití cyklů - ciferný součet, Euklidův algoritmus, test prvočíselnosti - zpracování posloupnosti dat, seznamy a operace s nimi, indexování, řezy - generátorová notace seznamů (list comprehension) - formátovaný výstup - funkce - parametry, return, lokalita proměnných - znakové řetězce, N-tice (tuples) - množiny a slovníky - textové soubory - standardní knihovna (math, copy, array, fractions, random, ...). - výjimky - try-except-finally, raise, assert - základní informace o třídách a objektech v Pythonu (jen princip, bez většího procvičení) - základní postupy při ladění programů 1.4 Python Kurz Adama Dingla pro anglickou paralelku: https://ksvi.mff.cuni.cz/~dingle/2022-3/prog_1/programming_1.html (pouze subjetivní tip na literaturu): https://www.programiz.com/python-programming 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áří. viz web cvičení. 3. 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 Programovani 1.std I/O (https://ksvi.mff.cuni.cz/~dingle/2022-3/prog_1/notes_2.html) 1.1. import sys 1.2 std in 1.3 sum numbers example 1.4 redirecting input 1.5 cat .\numbersToSum.txt | python .\stdio.py Ex. 2.0 Napiste program, ktery cte z stdin (standardni vstup), pred jednotlive radky vlozi cislo radku a radky s cislem radku vytiskne cat .\text.txt | python .\addLinesNumber.py Resp. 2.1 Napiste program, ktery cte z stdin (standardni vstup) a nacteny vstup vytiskne na std out; staci zadavat z klavesnice do prikazove radky; jak ukoncime ukoncime zadavani vstupu? 2.2 Napiste program, ktery cte z stdin (standardni vstup), pred jednotlive radky vlozi cislo radku a radky s cislem radku vytiskne na std out; staci zadavat z klavesnice do prikazove radky 2.3 Napiste program, ktery cte z stdin (standardni vstup), pred jednotlive radky vlozi cislo radku a radky s cislem radku vytiskne na std out; vstup presmerujte ze souboru 2.4 Do programu presmerujte vas/nejaky textovy soubor cat .\text.txt | python .\addLinesNumber.py 3.0 Mejme matici v Matlab formatu ulozenou v souboru (na jednom radku), vytvorte program, ktery: - matici ze standardniho vstupu nacte, - naparsuje a ulozi do nested listu (2D listu) a - vytiskne (s.split(), s.strip()) https://ksvi.mff.cuni.cz/~dingle/2022-3/prog_1/notes_4.html 3.2 Predpokladejte ze matice v souboru nemusi byt ulozena na jednom radku 3.4 Predpokladejte ze matice v souboru nemusi byt ulozena na jednom radku a muze byt prolozena ruznym mnozstvym mezer a tabulatoru 3.5 Predchozi a tisknuty vystup "hezky" naformatujte (fString) napr. 0 1 22 111 11 111 11 11 1 6.0 comments ctrl + /; ls; cat; cd; |; rm