13. 10. 2025 Algoritmizace  

03. Hodina 

Algoritmizace

0. Dotazy k přednášce

* Analýza O(n) složitosti "složitějších algoritmů" a příparava na domácí úkol
* Asymptotické notace - definice 
  - Jak porovnáváme dvě čísla (např. inty)? 
  - Jak porovnáváme dvě funkce? (nutné definovat definiční obor); 
  - Asymptotická notace jako "porovnávadlo funkcí"; 
  - Idea: meze, horní meze, asymptotická horní meze;

* Asymptotické notace - příklady 




1. Analýza O(n) složitosti "složitějších algoritmů"


1.2 Kruskalova algoritmu v pseudokódu: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm 
nebo vymenit na Prim Jarnikuv (nemenit)

- příparava na domácí úkol
- zjistíme, že:
-- nevíme, co je G, G.E, G.V, => ohodnocený neorientovaný graf, kostra ...(víc toho není aktuálně není třeba)
-- nevíme složitost operací FIND-SET(u), UNION(...) atd., záleží na volbě Datové Struktury a její implementaci; 
	složitosti jsou nám zadáný nebo si je zadáme 
-- v čem se měří velikost vstupu? |V| vs |E| vs |V| a |E|
-- zkusili jsme si práci se složitějším algo v pseudokódu, a ... zjistili jsme ze ....

- AIMA pseudokody ... např. str. 82 BFS 


* Asymptotické notace - příklady

Proč funkce? Kde se vzaly? Přeci jsme se bavili o algoritmech?
Kdy se dvě funkce rovnají?
A na čem záleží?

1.1  2x funkce s grafem

1.3  Dokažte nebo vyvraťte tvrzení. Pro každou dvojici funkcí f, g: N_0 -> R platí:
1.3.2 f(n) = 2n^2 + n a g(n) = n^2; f(n) = O(g(n)) - dukaz a nakreslit graf fci v geogebre, napr. pro c=5 
1.3.3 ((n^2)/2)-3n= O(n^2)

1.6 Dokažte nebo vyvraťte tvrzení. Pro každou dvojici funkcí f1, f2: N_0 -> R platí:
Nechť f_1 a f_2 jsou funkce pro, které platí f_1(n) in O(g(n)) a f_2(n) in O(g(n)). Potom f_1(n) + f_2(n) in O(g(n)).

1.8. Dokažte nebo vyvraťte tvrzení. Pro každou dvojici funkcí f1, f2: N_0 -> R platí:
Nechť f(n) = f1(n) + f2(n) a f1(n) in O(f2(n)). Pak f(n) in O(f2(n))

1.10  Dokažte nebo vyvraťte tvrzení. 
Pro každou dvojici funkcí f, g: N_0 -> R platí:

1.10.1 pokud f(n) = O(g(n)), pak g(n) = Omega(f(n))
1.10.2 pokud f(n) = O(g(n)), pak 2^f(n) = O(2^g(n))
1.10.3 f(n) = O(f(n)^2)


1.12 Nechť f_1 a f_2 jsou funkce pro které platí f_1(n) in O(g_1(n)) a f_2(n) in O(g_2(n)). Potom f_1(n) . f_2(n) in O(g_1(n) . g_2(n))




13. 10. 2025 Programování  

03. Hodina

Inspirováno: https://ksvi.mff.cuni.cz/~dingle/2025-6/prog_1/notes_2.html


* hlavne opakovani: if, for, while, I/O
* range, len
* nested loops
* string slicing
* std I/O
* random
* list, funkce, navratova hodnota, parametry, pass variable refenci a hodnotou, pojmenovane parametry, neznamy pocet param  

0.1. Napiste program, ktery precte slovo a vypise kazdy znak (pomoci for cyklu). 
	(iterace přes string; for)

0.1.5 Napiste program, ktery precte slovo a vypise kazdy sudy znak (pomoci for cyklu a range). 
	(for, range, len)

0.1.6. Napiste program, ktery precte alespon 4 znaké slovo a první 4 znaky (pomoci for cyklu a range);
	(for, range, len)

0.1.7. Napiste program, ktery precte slovo a první 4 znaky (pomoci for cyklu a range); pokud je slovo méně než 4 znaké načítání slova opakuje
	(for, range, len)

0.1.8. Napiste program, ktery precte alespon 4 znaké slovo a poslední 2 znaky (pomoci for cyklu a range);
	(for, range, len)

0.2. Napiste program, ktery precte slovo a vypise ho pozpatku-reverzne (pomoci for cyklu a range). 
	(for, range)

0.10. Napište program, který vygneruje všechny dvoupísmenné zkratky za podmínky, že první znak musí být ze znaků "brm", druhý číslo  "1,2,3"
	(nested loops)

HODINA SKONCILA ZDE

0.5. Napiste program, ktery precte slovo a vypise kazdy sudy znak (pomoci slicingu). 
	(string slicing)

0.6. Napiste program, ktery precte slovo a vypise ho pozpatku-reverzne (pomoci slicingu). 
	(string slicing)

0.9. Napište program, který ověří, zdali zadaný (neprázdný konečný) string je palindrom. 
Pokud je string palindrom, vypíše "ano", pokud ne vypíše "ne".
	(string slicing, for cyklus, testování)
	(šlo by reverse string a porovnat s původním; zde udělejme přes for cyklus)

0.9.2 Navrhněte množinu testovacích dat pro testování programu testujícího polindrom :D 



0.11. Napište program, který nalezne a vypíše, všechny číselné palindromy vzniklé součinem tří dvouciferných čísel.
	(string slicing a motivace k fci)



3. Square

Read a number N, then print an N x N square of asterisks as in the example below.

Enter N: 5
*****
*   *
*   *
*   *
*****


4. Triangle

Read a number N, then print an N x N triangle of asterisks as in the example below.

Enter N: 6
     *
    **
   ***
  ****
 *****
******



7. Spaces In Between

Read a string and write it out with a space between each adjacent pair of characters.

Enter string: waffle
w a f f l e



5. std IO: copy line  
5.2 prepend line number to lines and print

6. std IO: sum number