AG1 cvičení

čtvrtek 16:15

Info

Radovan Červený
cervera3@fit.cvut.cz
body
neoficiální skripta: Průvodce labyrintem algoritmů
 
0.5b = krátký challenge, první čtyři (max 2.5b)
0.5b = domácí úloha (max 2.5b)
1.0b = správně vyřešený těžký příklad u tabule
cvičící:
email:
gdocs:
materiály:
 
bonus body:
 
 


12. cvičení

21.12.2017

obvodová úložka

spočítání semestrální písemky

pokračování dynamickým programováním; úlohy na nejdelší rostoucí podposloupnost s jedním poklesem a v čase NlogN; úloha s rovnáním knih do knihovny

nalezení minimální kostry v grafu s ohodnocením hran z {1,2,3,4,5}


11. cvičení - semestrální test

14.12.2017


10. cvičení

7.12.2017

stužková úložka

ukázán 1] a 2] domácí úkol z 9. cvičení

radix sort; řazení N čísel z rozsahu [0, N3] v lineárním čase; řazení řetězců v čase O(součet délek řetězce);

nalezení nejdelšího úseku v posloupnosti, ve kterém se neopakuje žádne číslo

úvod do dynamického programování - přístup top-down

dán graf na vrcholech 1,2,...,N a z každého vrcholu vedou nejvýše dvě hrany do vrcholu z vyšším číslem => počet cest z 1 do N, délka nejdelší cesty při ohodnocených hranách z 1 do N

dláždění mřížky 2xN dlaždičkami 2x1 a 1x2

1] (0.5b) máme 4 přihrádky a 3 míčky, míčky házím do přihrádek, jaká je pravděpodobnost, že se alespoň 2 trefí do první přihrádky?

2] (0.5b) navrhněte graf (nebo algoritmus, který takový graf sestrojí), ve kterém mezi některými dvěma vrcholy vede Fk cest, kde Fk je k-té Fibonacciho číslo


9. cvičení

30.11.2017

ponožková úložka

ukázán domácí úkol hledání inverzí z 8.cvičení

Hanojske věže s pravidlem navíc, že nelze přesunout přímo disk z věže A na věž B

úloha s kabely o rozpoznávání jejich propojení

diskuze nad volbami pivota pro QuickSelect; konstrukce posloupností vynucující si kvadratické chování

analýza pravděpodbnosti výběru skoromediánu, když volím 3 prvky náhodně a vyberu medián z těch tří

načnut domácí úkol s maticí

Domácí úlohy:

1] (1.5b) úloha s nekonečným streamem, ale pro obecnou K-tici řádků (k dispozici je O(K) paměti)

2] (1.0b) zadána matice A velikosti NxM, kde řádky i sloupce jsou seřazeny vzestupně, jak v lineárním čase najít prvek Ai,j=k ?

3] (0.5b) máme 4 přihrádky a 3 míčky, míčky házím do přihrádek, jaká je pravděpodobnost, že se alespoň 2 trefí do první přihrádky?


8. cvičení

23.11.2017

trezorová úložka

rozdělování N kuliček do 3 přihrádek s pomocí operace "patří do přihrádky"; ukázka randomizovaného přístup řešící úlohu s 5N/3 operacemi ve střední hodnotě

mám nekonečný (nevím jak dlouhý) stream řádků, ale pamět mám na uložení pouze O(1) řádků, jak vybrat 1 řádek náhodně tak, aby každý z řádků měl stejnou pravděpodobnost výběru = pokud jsem právě přečetl N řádků, tak každý má pst 1/N, že ho mám zrovna vybraný

důkaz tvrzení, že když mám nesoudělná N,M a postupně beru všechny násobky i*N mod M pro i={0,1,...,M-1}, tak potom musím proskákat všechny hodnoty {0,1,...,M-1}

hashování; diskutováno hashování s řetízky; diskutováno hashování s otevřenou adresací + řešené příklady vkládání a odebíraní

hashování řetězců, ukázka vlastností polynomiálního hashe (rolling hash)

jak efektivně setřídit spojový seznam

načnuto efektivní výpočet počtu inverzí v poli

Domácí úlohy:

1] (1.5b) úloha s nekonečným streamem, ale pro obecnou K-tici řádků (k dispozici je O(K) paměti)

2] (1.5b) jak efektivně spočítat počet inverzí v poli


7. cvičení

16.11.2017

koňská úložka

binomiální haldy; merge, extract min, insert, decrease key, delete, increase key => vše O(log n)

pravděpodobnost; základní pojmy = prostor elementárních jevů, náhodná veličina, střední hodnota = ukázáno na úloze hodu 10 šestistěnnými kostkami

generování uniformně náhodných čísel z rozsahu [0, N-1] pomocí funkce randombit(); oba případy když N je mocnina dvojky a když není

analýza algoritmu Knuth shuffle

úloha s N přihrádkami a strefováním se do nich s tím, že pokus opakuji, pokud se trefím již do plné přihrádky; analýza střední hodnoty počtu pokusů; vyjde to NlogN

Domácí úlohy:

1] (1b) ukázat, že harmonická řada do N prvků se dá odhadnout shora logaritmem z N


6. cvičení

09.11.2017

faktoriál škrtací úložka

ukázán domácí úkol z 5.cvičení

amortizovaná analýza; binární sčítačka přímou metodou, simulace fronty pomocí dvou zásobníků; průchod stromem voláním operace následník

BVS; hledání následníka; pre/post/in order průchod

postavení vyváženého BVS ze seřazeného pole; vyvážení BVS v lineárním čase; sloučení dvou BVS v linearním čase

AVL; simulace insertů a deletů


5. cvičení

02.11.2017

králičí úložka

ukázán domácí úkol z 4.cvičení

dolní odhad hledání nejmenšího prvku v neseřazeném poli N prvků => nejméně N-1 porovnání

rychlé hledání k-tého nejmenšího prvku v neseřazeném poli N prvků

hledání sqrt(N) nejmenších prvků v neseřazeném poli N prvků v O(N)

binární haldy; operace insert, extract min, change key

rychlé slévání K setříděných posloupností

HeapSort + vlastnosti řadících algoritmů: datová citlivost, stabilita, in-place

rychlé seřazení posloupnosti, kde je každý prvek od své pozice vzdálen nejvýše K pozic

Nakousli jsme, doděláme přístě:

amortizovaná složitost; penízková metoda; přímá metoda

Domácí úlohy:

1] (1b) slevání K seřazených posloupností délky N v čase O(N*K*log(K)) bez použití haldy


4. cvičení

26.10.2017

sklenicová úložka

ukázány domácí úkoly z 2. cvičení

nechť T je neorientovaný strom, v němž je maximalní stupeň vrcholu k (zapíšeme jako Δ(T)=k); důkaz, že strom T má alespoň Δ(T) listů (vrcholů stupně 1)

důkaz, že postupným napojováním listů na strom lze sestrojit libovolný strom (indukce přes odtržení vrcholu)

důkaz, že pro každý souvislý graf G na alespoň 3 vrcholech existují dva různé vrcholy u,v takové, že odtržením libovolného z nich nebo i obou dostaneme opět souvislý graf

interpretace mocnin matice sousednosti Ak

prohledávání stavového prostoru a BFS

zapomnětlivý běžci a topsort

Domácí úlohy:

1] (1.5b) je zadán strom T, nalezněte algoritmus pro nalezení nejdelší cesty v tomto stromě a dokažte jeho správnost


3. cvičení - povede Václav Blažej

19.10.2017


2. cvičení

12.10.2017

faktoriálová úložka

podgraf, indukovaný podgraf; důkaz, že graf, který obsahuje kružnici liché délky jako podgraf, obsahuje také kružnici liché délky jako indukovaný podgraf

důkaz, že neexistuje nesouvislý graf jehož doplněk je také nesouvislý

počitání cest různých délek v grafech Kn, Kn,m

určení počtu všech indukovaných podgrafů Kn (nejdříve když nepočítáme vzájemně izomorfní grafy jako různé, poté když je počítáme); určení počtu všech různých podgrafů Kn (pouze když počítáme vzájemně izomorfní grafy jako různé)

důkaz, že graf o 2n vrcholech, kde každý vrchol je spojen s právě n dalšími různými vrcholy, je souvislý

důkaz, že orientovaný graf, jehož každý vrchol má vstupní i výstupní stupeň alespoň jedna, musí obsahovat cyklus

souvislost a komponenta souvislosti

Domácí úlohy:

1] plyne z tvrzení o existenci cyklu v orientovaném graf, jehož každý vrchol má vstupní i výstupní stupeň alespoň jedna, že každý vrchol v tomto grafu je součástí nějakého cyklu?

2] jak vypadá graf na n vrcholech, který má právě c souvislých komponent a má maximální možný počet hran, ze všech takových možných? dokažte, že tento graf nemůže vypadat jinak


1. cvičení

05.10.2017

vajíčková úložka

počítání hvězdiček

úvod do teorie grafů: definice a pojmy; příklady na existenci grafů dle daných podmínek (počty vrcholů, hran, stupně vrcholů); princip sudosti, ukázka, že graf ho může splňovat, ale přitom nemusí existovat; grafy se všemi stupni vrcholů různými (nebo s povolením dvou stejných).

definice izomorfismu, motivace pro jeho zavedení: ukázka, že izomorfismus je ekvivalence a tedy se k grafům ze stejné ekvivalenční třídy můžeme chovat jako ke stejným (smazání labelů u vrcholů); co to znamená dokázat, že dva grafy jsou či nejsou izomorfní; příklady na poznání izomorfismu grafů: nutné podmínky pro izomorfismus (stejný počet vrcholů, hran, ...).

důkaz věty: G ~ H <=> G' ~ H' ; příklad použití u ukázky izomorfismu (n-2)-regulárních grafů.

automorfismus a počítání automorfismů různých grafů: Kn, Kn bez hrany,...

Dáme přístě:

pořádný formální důkaz věty: G ~ H <=> G' ~ H'

Domácí úlohy:

1] dokažte následující tvrzení: pro každé N>0 lze sestrojit graf o N vrcholech, který má všechny stupně vrcholů různé až na dva, které mohou být stejné (tedy např. pro N=5 povolujeme stupně: 0 1 1 2 3, ale ne 0 1 1 1 2)

2] najděte graf s N>1 vrcholy a s právě jedním automorfismem