Alg 27.10.2025 0. Dotazy k přednášce 2. Převody soustav Převeďte čísla ze zadaných výchozích soustav do cílových soustav ([číslo]_soustava): 2.1. [143]_10 do []_2 2.3. [143]_10 do []_3 a zpět 2.5. [0111010110110]_2 do []_10 2.7. [0111010110110]_2 do []_5 2.9. [0111010110110]_2 do []_3 2.11. [1B7E]_16 do []_10 2.13. [1B7E]_16 do []_2 4. Binární vyhledávání v setříděném poli - (idea) algoritmu vyhledat v setříděném poli na tabuli, prvek který: a) je obsažen, b) není obsažen, c) je obsažen a je krajní, d) není obsažen a je menší než nejmenší obsažený a symetricky - složitost (hvezdicka 3) - co vracíme? (při (ne)nalezení prvku) - trekování horní a dolní meze - podmínky zastavení - co nám "přináší" setřídení oproti nesetřízenému poli a co bere? (metafora a dílnou) * 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í). * co je DS * proč řadit * sorting algos: vizualgo - trackovani algoritmu - insert select 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 - jak rychle se dostane na svou pozici nejmensi a nejvetsi prvek v bublesortu? - buduje ubble sort take seraz a neseraz cast? - k cemu je promenna swapped? * 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 do min-heapu (ve forme stromu) posloupnost hodnot: 30, 4, 71, 14, 22, 5, 2, 9, 8, 3, 11 - zmente reprezentaci vytvorene haldy z BT na pole - vytvorte haldu ve forme pole z nasledujici posloupnosti: 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 - mejme pole hodnot: 30, 4, 71, 14, 22, 5, 2, 9, 8, 3, 11 provedte razeni heapsortem v poli 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? Prg 27.10.2025 * implementujte funkci pro binarni vyhledavani binary_search(list, key); a rozmyslete si vhodna testovaci data * 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 * f-string formating https://ksvi.mff.cuni.cz/~dingle/2024-5/prog_1/notes_3.html Příklady *3. Matrix Sum Write a function that takes two matrices (in form nested list), 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. predavani odkazu hodnotou a referenci nebylo na prednasece takze bude priste *2. Napiste funkce: a) plusOneToInt(n) prí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 5. std IO: reverse line Napište program, který čte řádky ze std IO a vypisuje je pozpátku (reverzně). 5.2 prepend line number to lines and print Napište program, který čte řádky ze std IO, ocisluje jednotlive radky a vytiskne je Ex. pro vstup: Kde domov můj, kde domov můj? Voda hučí po lučinách, bory šumí po skalinách, v sadě skví se jara květ, zemský ráj to na pohled! A to je ta krásná země, země česká, domov můj, země česká, domov můj! vypíše: 1. Kde domov můj, 2. kde domov můj? 3. Voda hučí po lučinách, 4. bory šumí po skalinách, 5. v sadě skví se jara květ, 6. zemský ráj to na pohled! 7. A to je ta krásná země, 8. země česká, domov můj, 9. země česká, domov můj! 5.3 zkuste si poslat programu data ze souboru na standardni vstup a vypsat do konzole cat inputDataFile.txt | python skript.py 5.4 zkuste si poslat programu data ze souboru na standardni vstup a vypsat do souboru cat inputDataFile.txt | python skript.py >> outputFile.txt vs. cat inputDataFile.txt | python skript.py > outputFile.txt 6. std IO: sum number 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