Programování 2 pro Matematiky - cvičení - NMIN112 1. Úvodní informace 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. 1.4 Předpokládané znalosti z Programování 1 ze zimního semestru vyučovaného v Pythonu: - instalace Pythonu, prostředí IDLE, Python jako kalkulačka - proměnné a výrazy, operace s čísly, relace a logické spojky - struktura programu – příkazy input a print, odsazování kódu, komentáře - příkaz if (zanořování, elif, else) - cyklus while (včetně else) - základní použití podmínek a cyklů - zpracování posloupnosti dat, seznamy a operace s nimi, indexování, řezy - generátorová notace seznamů (list comprehension) - funkce - parametry, return, lokalita a viditelnost proměnných - znakové řetězce - formátovaný výstup (znakové řetězce typu f“xxx {y} xxx“) - N-tice (tuples) - množiny a slovníky - textové soubory - standardní knihovna – základní přehled (math, copy, array, fractions, decimal, time, random, ...) - výjimky - try-except-finally, raise, assert - základní informace o třídách a objektech v Pythonu. - základní postupy při ladění programů 1.5 Python - rozšiřující literatura Kurz Adama Dingla pro anglickou paralelku: https://ksvi.mff.cuni.cz/~dingle/2025-6/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áří. Podmínky zápočtu na Teoretické a Praktické čá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 vstupních 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/) pozorování: umíme určit přesně, umíme aproximovat přibližně, umíme učit (horní/dolní) mez 4. Praktické cvičení - Programování opakování - předavání parametrů hodnotou a referencí - string slicing opakování: vstupu přes stdin; parsování vstupu; formátování výstupu; oop; coding style; good code: https://ksvi.mff.cuni.cz/~dingle/2024-5/prog_1/notes_13.html 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 Napište program, který očísluje řádky textu; čte ze stdin (standardní vstup), před jednotlivé řádky vloží číslo řádku a řádky s číslem řádku vytiskne na standardní výstup cat .\text.txt | python .\addLinesNumber.py Resp. po částech 2.1 Napište program, který čte ze stdin (standardní vstup) a načtený vstup vytiskne na std out; vstup stačí zadávat z klávesnice do příkazové řádky; jak ukončíme zadávaní vstupu? 2.2 Napište program, který čte z stdin (standardní vstup), před jednotlivé řádky vloží číslo řádku a řádky s číslem řádku vytiskne na std out; vstup stačí zadávat z klávesnice do příkazové řádky 2.3 Napište program, který čte z stdin (standardní vstup), před jednotlivé řádky vloží číslo řádku a řádky s číslem řádku vytiskne na std out; vstup přesměrujte ze souboru 2.4 Na vstup programu přesměrujte váš/nějaký textový soubor cat .\text.txt | python .\addLinesNumber.py 2.5 Na vstup programu přesměrujte váš/nějaký textový soubor, proveďte očíslování řádků a vystup uložte do nového souboru cat .\text.txt | python .\read_print_lines.py > text_output.txt (cvičíme načítání a zpracování vstupu; i navrh vhodné dekompozice úlohy) 3.0 Mějme matici v Matlab formátu uloženou v souboru (na jednom řádku), vytvořte program, který: - matici ze standardního vstupu načte, - naparsuje a uloží do nested listu (2D listu) a - vytiskne (s.split(), s.strip()) https://ksvi.mff.cuni.cz/~dingle/2025-6/prog_1/notes_4.html - ještě než se pustíme do implementace; na chvíli se zastavme a rozmysleme si dekompozici úlohy; následně vedoucí do dekompozice kódu - všiměme si, že výsledná funkce dělá 3 různé neávislé činnosti; je tedy vhodné pro každý úkol vytvořit samostatnou funkci; která dobře provádí jednu jednotlivou činnost; a následně tyto činnosti spojit v jedné funkci dohromady příklad vstupu: [ 1 2 2 35; 44 44 44 44 ; 4444 333 22 1] 3.2 Předpokládejte ze matice v souboru nemusí byt uložena na jednom řádku 3.5 Předchozí a tisknuty vystup "hezky" naformátujte (fString) např. vstup 0 1 22 111 11 111 11 11 1 6.0 comments ctrl + /; ls; cat; cd; |; rm