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

1. Úvodní informace
Dotazy: ke cvičení? případně ještě k podmínkám zápočtu? k přednášce? 

2. Hvězdičky pokračování (Labyrintem algoritmů)
Pozorovani: měli jsme 3 meta-typy chování funkci složitosti: a) přesně spočítáme , b) aproximujem c) omezíme mezí (horší či lepší než to nebude) 

2.1 Který algoritmus je lepší?

2.2 Kuchařka pro výpočet složitosti


3. Asymptotické složitosti
3.2 Definice 

3.3 Příklady: 
Dokažte nebo vyvraťte následující tvrzení:
3.3.1 pro všechny funkce f, g: N->R+ platí: f = n^2 -6n + 4, g= (n^2), pak f(n) = O(g(n))
3.3.2 pro všechny funkce f, g: N->R+ platí: f = n^2, g= n^3, pak f(n) = O(g(n))
3.3.3 pro všechny funkce f, g: N->R+ platí: f = n^3, g= n^2, pak f(n) = O(g(n))
3.3.4 pro všechny funkce f, g: N->R+ platí: f = O(g) => g = OMEGA(f)
3.3.5 pro všechny funkce f, g, h: N->R+ platí: f = O(g) & h = O(g) => f+h = O(g)
3.3.6 pro všechny funkce f, g, h: N->R+ platí: f = O(g) & h = O(g) => f.h = O(g)


Převody ze soustav do soustav

[110011]2 do 10
[110011]3 do 10

[3456]10 do 2
[3456]10 do 3



4. Style Guide: o čem to je? co vše se mimo jiné řeší? není to dogma, jsou to doporučení; 
mají svě klady i zápory; často programovacím jazykem a kulturně závislé

PEP 8 – Style Guide for Python Code: https://peps.python.org/pep-0008/
Google Python Style Guide: https://google.github.io/styleguide/pyguide.html

namming convention (var, fce, const, class, ..)
blank lines delim, delim, line function length



Příště
- základní postupy při ladění programů
- model view architekture


Programování
 
3.0 Mejme celociselnou matici ve (zjednodusenem) Matlab formatu ulozenou v souboru (na jednom radku), vytvorte funkci, ktera soucasne:
- matici ze standardniho vstupu nacte, 
- naparsuje a ulozi do nested listu (2D/nested listu) a
- vytiskne
(s.split(), s.strip(), s.strip(" abc"), s.strip(" []"), "".join(["a","b"]), "xxxx".join(["a","b"]), s.replace("[",""))
https://ksvi.mff.cuni.cz/~dingle/2022-3/prog_1/notes_4.html

Priklad zjednodusene matice: "[1,2,3,4;5,5,5,5]"
		
3.2 Předchozí a předpokladejme že matice v souboru můze byt prolozena ruznym mnozstvym mezer
Priklad matice: "   [   1,   2   , 3,4  ;   5, 5   ,5 , 5   ]  "


3.3 Předchozí a predpokladejte ze matice v souboru nemusi byt ulozena na jednom radku
Priklad matice: "  [   1,  
 2   , 3
,4  ;   5, 5   ,5
 , 5   ]  "

3.5 Predchozi a tisknuty vystup "hezky"*  naformatujte (fString)
*hezky = zarovnane doprava, predpokladejte ze cisla nebudou vetsi nezli 6 cislic

Napr. 
   0   1  22
 111  11 111
  11  11   1 


Poznamky:
- zacit s funkci ktera cte ze stdin (vice radku) a vraci jeden slozeny string
- cviceni je na dekompozici kodu; opakovani top-down a bottom-up pristupu 
- dekompozice top-down napr. 
	read_parse_print_matrix:
	-- read(...)
	-- parse(...)
	-- print(...)

a dale napr 
	parse(...):
	-- zbavit se hranatych zavorek
	-- rozdelit na jednolive radky
	-- radky rozdelit podle jednotlivych prvku v radku (rozdelit na sloupce)
		-- orezat a pretypovat
            
- pouziti konstant pro delimitry ve vstupnim stringu
- a nebo cely kod parsovani napsat do 
# [item for item in matrix_string_with_brackets.strip("][ ").split(ROW_DELIM)]
[[int(item.strip()) for item in row.split(COL_DELIM)] for row in matrix_string_with_brackets.strip("][ ").split(ROW_DELIM)]



6. Loupání matice

6.1 Loupaní matice - v implementaci použijte for/while cykly

Matici z předchozího příkladu "oloupejte"* a výsledné hodnoty vypište na konzoli. 
Loupání začněte v pravém horním rohu a pokračujte ve směru hodinových ručiček.
(*loupání = loupáte/ořezáváte matici vrstvu po vrstvě, z vnějšího okraje k vnitřními; jako byste rozbalovali šnečí ulitu)
(u funkce loupani muzete pocitat, ze matice je aspon o 2 radcich a 2 sloupcich)

Matice:
1  2  3  4
5  6  7  8 
9 10 11 12 

Jak vypadá její oloupaný tisk?

Výstup "oloupané" matice:
4 8 12 11 10 9 5 1 2 3 7 6


6.2 Loupaní matice - 
Předchozí a místo tisku oloupané matice napište funkci vracející list hodnot "oloupané" matice

6.4 Loupaní matice - v implementaci použijte rekurzi