[Zk] 14.2.2012
Napsal: 14. 2. 2012 21:15
Klasicka skuska z datovych struktur. Koubek kazdemu dal jedno zadanie a kto mu to chcel ukazat tak sa prihlasil.
V ruskej rulete som obstal - Fibonacciho haldy. Napisal som vlastne vsetko co je v skriptach (ale dost chaoticky) - definiciu, operacie, ich zlozitosti, amortizovane zlozitosti (zlozitosti som okomentoval ked som si myslel ze to nie je zjavne) a lemmu a vety s dokazmi (o pocte synov vrcholu). Finalny dokaz kde sa odhaduje prave pocet synov v som si nepamatal, takze som ho odhadol jednoduchsie ako je v skriptach (takze viac nahrubo).
Koubek si tie moje papiere precital a nebol uplne spokojny s definiciou haldy - nenapisal som ze korene stromov nemozu byt oznacene. Nechal ma si to rozmysliet ale neprisiel som na to. Potom mi ukazal moj vyvazovaci algoritmus a uz to zo mna vytiahol. S ostatnym viac menej suhlasil a dal mi za 2 so slovami ze by mi chcel dat za 1 alebo ze mi ju neda.
V ruskej rulete som obstal - Fibonacciho haldy. Napisal som vlastne vsetko co je v skriptach (ale dost chaoticky) - definiciu, operacie, ich zlozitosti, amortizovane zlozitosti (zlozitosti som okomentoval ked som si myslel ze to nie je zjavne) a lemmu a vety s dokazmi (o pocte synov vrcholu). Finalny dokaz kde sa odhaduje prave pocet synov v som si nepamatal, takze som ho odhadol jednoduchsie ako je v skriptach (takze viac nahrubo).
Koubek si tie moje papiere precital a nebol uplne spokojny s definiciou haldy - nenapisal som ze korene stromov nemozu byt oznacene. Nechal ma si to rozmysliet ale neprisiel som na to. Potom mi ukazal moj vyvazovaci algoritmus a uz to zo mna vytiahol. S ostatnym viac menej suhlasil a dal mi za 2 so slovami ze by mi chcel dat za 1 alebo ze mi ju neda.