06. Hodina (05. hodina se nekonala, byl státní svátek 28. 10. 2024) Alg * co je DS? * metafora řádu v dílně u DS * proč řadit? * sorting algos: vizualgo - trackovani algoritmu - select insert buble sort: jak vypada: a] nejlepsi a b] nejhorsi vstup vzhledem k poctu operaci/casove slozitosti a jake casove slozitosti to jsou - analyzou pseudokodu na vizualgo - k cemu je promenna swapped? - jak rychle se dostane na svou pozici nejmensi a nejvetsi prvek v bublesortu? - buduje bubble sort take seraz a neseraz cast? * proč vlastně řádíme (pouze) inty? * stromy (jako graf) - binární, n-arní strom, hloubka vrcholu a stromu, delka cesty (v cem se meri?), terminologie: koren a list * bin stromy jako datova struktura, rekurzivne * (binarni) halda: definice, "heap = BT + usporadani + tvar"; forma BT a pole; operace: insert, extract min/max v a) stromě b) poli a jejich prevody; * heapsort (vytvoreni haldy v case nlog(n)) faze 1 - pole - halda jako BT - pole faze 2 - pole halda v poli - pole ... vse to same pole faze 3 - tvorba haldy v case O(n) - vlozte (insert) do min-heapu (ve forme stromu) posloupnost hodnot (pridavani postupne po jednom prvku): 30, 4, 71, 14, 22, 5, 2, 9, 8, 3, 11 - zmente reprezentaci vytvorene haldy z BT na pole - postupnym vkladanim vytvorte haldu ve forme pole z nasledujici posloupnosti (pridavani postupne po jednom prvku): 30, 4, 71, 14, 22, 5, 2, 9, 8, 3, 11 - v halde provedte 4x operaci extractMin a] v forme BT b] ve forme pole PRISTE - mejme pole hodnot: 30, 4, 71, 14, 22, 5, 2, 9, 8, 3, 11 provedte razeni heapsortem v poli Řazení v lineárním čase * CoutingSort - příklad counting sortem seřaďte posloupnost: 5,3,7,1,5,2,3,1,2,4,5,3,1,3 * RadixSort - příklad seřaďte posloupnost: 15,3,17,11,25,32,23,21,42,54,75,13,31,33 Co se stane, když v algoritmu radixového třídění budeme zpracovávat souřadnice zleva doprava (místo zprava doleva), tj. ve funkci radixSort() na str. 21 (přednáškových slidů) vynecháme reversed v záhlaví for-cyklu. Bude takto upravený algoritmus stále fungovat korektně? Pokud ano, vysvětlete proč, pokud ne, sestrojte protipříklad. * Dolni odhad složitosti řazení prvků porovnáním - rekonstrukce důkazu 3. kolik maximálně prvků má binární strom v k-vrstvě (hloubce?) 5. kolik maximálně prvků ma binární strom o k-vrstvách (hloubce?) 7. dokazte nebo vyvratte: mejme plne zaplneny binarni strom o k vrstvach; obsahuje k vrstva vice hodnot nezli cely strom bez k-te vrstvy? * různé modifikace binárního vyhledávání: - v setříděném poli určit počet výskytů dané hodnoty x - v setříděném poli nalézt všechny prvky s danou hodnotou x (první a poslední index) - v setříděném poli nalézt prvek s hodnotu x (pokud tam je) nebo nejbližší vyšší (pokud tam žádné x není). Prg * nested list * structural and reference equality: https://ksvi.mff.cuni.cz/~dingle/2024-5/prog_1/notes_3.html Python provides two different operators for testing equality. The first is the == operator: for structural equality. In other words, given two lists, it compares them element by element to see if they are equal. The second equality operator is the is operator: for reference equality. In other words, it returns true only if its arguments actually refer to the same object. * list deep copy: >>> l = [3, 5, 7, 9] >>> n = l.copy() # technique 1: call the copy() method >>> n = list(l) # technique 2: call the list() function >>> n = l[:] # technique 3: use slice syntax * modularita kódu, reusability, readability, parametrizovatelna cast kodu, funkce, navratova hodnota, parametry, defaultni, pojmenovane parametry, neznamy pocet param * "jedna funkce jedna cinnost", parametrizovatelnost, "dobre" pojmenovani funkce * pass variable refenci a hodnotou, mutable immutable * std in and * string splitting PRISTE * f-string formating https://ksvi.mff.cuni.cz/~dingle/2024-5/prog_1/notes_3.html Příklady *1. Napičte funkci obsahObdelniku(a, b) vypočítávající a vracející obsah obdélníka o stranach a, b. *1.5 Napiste funkci reverseList(list), ktera dostane list a vrati otoceny list *1.7 Napiste funkci plusNumber(list, number), ktera ke vsem prvkum-intum listu pricte cislo number a list vrati. Pokud neni cislo number zadane/definovane pricte hodnotu 1; bere vychozí/defaultní hodnotu 1. (defaultni a pojenovane parametry) *2. Napiste funkce: a) plusOneToInt(n) pricix távající jedničku k intu a vysledek vrati b) plusOneToList(list) pricitavajici jednicku ke všem prvkům v listu a vysledek vrati PRISTE *1.145 Napiste funkci sum() scitajici neznamy pocet cisel eg. sum(4,6,7), sum(2,4,6,9,4,1) *3. Matrix Sum Write a function that takes two matrices (list listu), and returns the sum of the matrices. Assume that the matrices have the same dimensions. *4. Symmetric Matrix A matrix M is symmetric if Mij = Mji for all i and j. For example, here is a symmetric matrix: 1 2 3 2 5 4 3 4 6 Write a function that takes a square matrix M represented as a list of lists, and returns True if the matrix is symmetric. 5. Napište funkci, která načte ze stdin matici a uloží ji jako list listů (2D pole) 7. Napište funkci, která načte ze stdin matici, uloží ji jako list listů (2D pole) a rozhodne, zdali je symetrická 9. Napiste funkci ktera dostane matici jako list listu a vytiskne ji jako "hezkou" matici: mezi cisly je jedna mezera a cisla jsou zarovnana ve sloupci viz priklad matici [ [1, 2, 3], [2, 1, 5], [3, 4, 1] ] vypsat 1 2 3 2 1 5 3 4 1 resp zarovnani cisel 111 2 333 22 1 5 3 4 11