Zkouška 26.5.2008

Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
vrtulex
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 20. 2. 2008 22:41
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od vrtulex »

Myslím, že ta halda v lin. čase spočívá v tom, že se staví odspoda (takže u heapsortu odzadu)
HonzaK
Matfyz(ák|ačka) level II
Příspěvky: 71
Registrován: 28. 9. 2007 17:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od HonzaK »

Him píše:HonzaK: jak se dela to vytvareni haldy v lin. case? jen se pridavaji prvky a nic se nedela? Dik
Dela se to, jak to Holan nazval, "ucetnickym trikem":
Vyjde se z toho, ze pri reprezentaci haldy temer uplnym bin. stromem se velka cast vrochlu nachazi bud v posledni hladine (tj. jsou to listy), nebo predposledni hladine - celkem to vzhledem k exponencialnimu rustu poctu vrcholu vzhledem k hladinam dela n/2 vsech vrcholu, ktere se uz vemou, ze jsou na svem miste, tj. cas na jejich umisteni je 0 (pri reprezentaci polem to odpovida druhe polovine pole). Dale se vezmou vrcholy, ktere tvori zbytek predposledni hladiny a cast predpredposledni - tech je n/4 a na vlozeni kazdeho z nich potrebujeme max 1 prohozeni (s nejakym vrcholem, ktery uz v hlade je). Pak se vezme dalsich n/8 vrcholu (na umisteni kazdeho z nich potrebujeme max 2 prohozeni), pak n/16 atd.

Tedy celkem je potrebny cas: 0*n/2 + 1*n/4 + 2*n/8 + ... coz je O(n)

Takze tak nejak... :wink:
Uživatelský avatar
Cabroušek
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 24. 1. 2008 23:16
Typ studia: Informatika Mgr.
Bydliště: Kladno
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od Cabroušek »

Kdybyste někdo náhodou chtěli brát moc vážně to řešení, co jsem tam napsal, tak to neděleljte, není dobře :oops: ... Ale kdyby se to kapánek předělalo, tak to bude fungovat dobře. A mohlo by to mít ještě mnohem menší složitost, jelikož je mnoho tahů, kdy se vlastně nic neděje.
in5inity
Matfyz(ák|ačka) level I
Příspěvky: 39
Registrován: 12. 1. 2008 10:40
Typ studia: Informatika Bc.

Re: Zkouška 26.5.2008

Příspěvek od in5inity »

Lidi, dá se na téhle zkoušce vyletět?
vrtulex
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 20. 2. 2008 22:41
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od vrtulex »

U Topfera to asi možný je... když zvoráš ten algoritmus, tak budeš muset bojovat o 3 (pokud nepůjdeš rovnou)... ale to jsem tak slyšel... já byl u Holana
in5inity
Matfyz(ák|ačka) level I
Příspěvky: 39
Registrován: 12. 1. 2008 10:40
Typ studia: Informatika Bc.

Re: Zkouška 26.5.2008

Příspěvek od in5inity »

Mohli byste někdo, kdo už má tuhle zkoušku za sebou napsat z čeho jste se učili, atp? Hlavně moc nechápu, jak moc podrobně to musí být u té písemné části rozebrané. Jestli stačí napsat např. teď si vygeneruju stavový prostor, a prohledávám do hloubky, nebo tam bazírujou na detailech?

DÍK
Uživatelský avatar
R.U.R.
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 25. 5. 2008 18:46
Typ studia: Informatika Ph.D.
Bydliště: Beroun
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od R.U.R. »

No musí bejt jasný, jak bys to udělal. Aby z toho bylo vidět, že si uvědomuješ, jak konkrétně by se to napsalo, jak přesně by vypadaly datové struktury, aby z toho byla vidět složitost... Určitě nebazírujou na detailech, musí tam bejt to podstatný, to důležitý. Pokud nějakou důležitou věc ohledně řešení budeš vědět akle nenaúpíšeš ji tam, tak to není dobré. Já osobně jsem popsal asi 6 těch velkejch stránek a musel jsem si během toho ořezávat tužku, ale myslím, že jsem to psal zbytečně moc podrobně. Každopádně káš 2 hpdiny času, to toho člověk stihne napsat dost, mě by byla stačila hodka a půl.
Na písemku jsem se neučil. Na ústní jsem se učil z poznámek a ze slajdů co má topfer na stránkách, a co se týče těch stromů a takovejch těch datovejch struktur, tak na to jsem kouk v Algovision.
hoboj
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 29. 1. 2008 16:18
Typ studia: Informatika Bc.

Re: Zkouška 26.5.2008

Příspěvek od hoboj »

rozhodne nebazirujou na detailech ale musi bejt videt ze vis jak bys to udelal.
jiank z tech peti tematovejch okruhu co tam mame napsat (postrehy, algoritmus, ds, atd atd) jsem mel jeden a pul a stejne, jelikoz jsem tam mel vsechno dulezity, tak to bylo za jedna.
Turista

Jak na tohle

Příspěvek od Turista »

Máte někdo tušení, jak aspoň začít s řešením tohohle příkládku? Nějak vůbec nevím, kde začít a dle čeho navyšovat. Díky
Zadání: http://forum.matfyz.info/viewtopic.php?t=1885
Odpovědět

Zpět na „PRG031 Programování II“