Domáca úloha č. 1 (LS 2009)

Moderátor: FeroG

<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Sob Feb 21, 2009 10:03 am

Domáca úloha č. 1 (LS 2009)

Na stránke cvičení je zverejnená prvá sada úloh. Nakoniec sa mi podarilo vyrobiť úlohy rôzne od minuloročných. Preto odporúčam inšpirovať sa minuloročnými úlohami a ich riešeniami.

Pripomínam, že na tomto fóre môžete navzájom diskutovať možné prístupy k riešeniu (alebo čo len chcete) s výnimkou zverejnenia zdrojových kódov.
<<

LukasCh

Príspevky: 3

Registrovaný: Štv Feb 19, 2009 7:34 pm

Poslať Pon Feb 23, 2009 10:19 pm

No tak ja som sa na tu DU uz mrkol, ta prva s tym "palicom" mi nepripada az taka tazka, teda ak je moja myslienka spravna :) podstatou mojho algoritmu je to, ze snazim napalit najvacsi nenapaleny subor na co najmensie medium aby som zaistil "neplytvanie" miestom. jednoducho si usporiadam(v mojom pripade polia CD a SUBORY) jedno od najmensieho po najvacsie a druhe naopak a potom postupne "napalujem" subory.

mozno to niekomu pomoze alebo ak je to nahodou zla myslienka(nemala by byt :) ) tak ma opravte. Toto riesenie mi vsak pripada menej casovo narocne ako generovanie vsetkych moznosti ako napalit subory na CD a potom skusat ci sa fakt zmestili...
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Pon Feb 23, 2009 10:52 pm

Dakujem za prvy prispevok v tomto fore. Kedze do terminu pre prvu sadu je casu relativne dost, nebudem ihned reagovat (pozitivne, ci negativne) na tento prispevok (navrh algoritmu). Bol by som rad, ak by sa nasiel niekto z kolegov, co by sa k tomu skusil vyjadrit. Ak sa v rozumnom case (do stvrtku) nenajde nikto, tak sa vyjadrim ...
<<

Pnr

Príspevky: 7

Registrovaný: Ned Feb 22, 2009 2:16 am

Poslať Uto Feb 24, 2009 1:08 am

ja som to ich zas chcel usporiadat obe od velkych po male, a potom na prve cd dat najvecsi subor, a hladat ci je este nejaky co sa tam zmesti, ak je tak ho tam dat a hladat ci je este nejaky co sa tam zmesti, ked ne ides na dalsie cd ...
<<

alef0

Site Admin

Príspevky: 621

Registrovaný: Štv Nov 16, 2006 8:57 am

Poslať Uto Feb 24, 2009 12:22 pm

V pripade toho pristupu od najvacsieho po najmensie sa ale nemoze stat, ze sa mi potencialne oplati vziat namiesto jedneho velkeho suboru radsej dva mensie subory a neskor ich dopchat jednym mensim?

(Hadam ma cviciaci nezabije, ale mna to tiez zaujima :-))
Lorem ipsum dolor sit amet.
<<

LukasCh

Príspevky: 3

Registrovaný: Štv Feb 19, 2009 7:34 pm

Poslať Uto Feb 24, 2009 2:23 pm

no neviem, ale vezmime si priklad ze mame CD velkosti 8 a 3, subory velkosti 2,1,5,3. a ked do CD s kapacitou 8 narvem 2 1 3 subory tak uz sa tam 5 nevmesti nikde. ak vsak zacnem do CD velkosti 3 pchat subor velkosti 5, kedze sa nevmesti ide do 8, subor velkosti 3 sa do cede s kapacitou vmesti tak tam ide a subory velkosti 2 a 1 sa do zvysnych 3 mb vonlnych na cd o velkosti 8 kde uz je subor 5 vmestia tiez.

Ja viem, vela cisel, ale ma to zmysel, staci 2 krat precitat a pochopite :)
je jasne ze som tymto prikladom nepokryl vsetky moznosti, ale ved je to len priklad...
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Uto Feb 24, 2009 8:33 pm

Kedze zajtrajsie cvicenie bolo zrusene (vid dalsiu temu) rozhodol som sa prist s odpovedou uz dnes. Zial ziadne z triediacich pristupov nepomozu. Mozno to vyjde vo vela pripadoch, no nie vzdy. Skuste najst konktrapriklady na jednotlive strategie.

Pre "narocnych" (zvysok si musi pockat na druhy rocnik): Teraz, preco rychle riesenia nefunguju (za predpokladu, ze neplati P=NP), resp. preco to nejde riesit v polynomialnom case. Tato uloha je len variacia Bin Packing problemu zabalena do praktickej motivacie. Ak by ste vedeli riesit tento problem v polynomialnom case (rychlo), zuzenim vstupu na 2 media, ktorych velkost je rovna polovici suctu vsetkych suborov, vedeli by ste riesit v polynomialnom case tzv. Partition problem. O nom je vsak dokazane, ze je to tzv. NP-uplny problem. Prelozenim do "normalnej reci": ak by ste vyriesili domacu ulohu polynomialnym algoritmom, cela informaticka komunita "zaburaca" a stanete sa Einsteinom informatiky.

Cize nic ine ako nejaky chytry backtrack vam nepomoze. Chytry backtrack sa od generovania vsetkych moznosti nebude "asymptoticky" lisit. Resp. asi je jedno ci pri dostatocne velkom vstupe pockate za vysledkom 50000 rokov alebo 20000 rokov. Vo vasich rieseniach chytry backtrack potesi, no v pripade tejto ulohy nie je nevyhnutnostou.
<<

lochness42

Príspevky: 40

Registrovaný: Uto Feb 26, 2008 8:46 pm

Poslať Uto Feb 24, 2009 10:26 pm

Odporucam si pozriet i nieco o greedy algoritmoch - http://en.wikipedia.org/wiki/Greedy_algorithm

Odhali vam to aj dovod preco niektore priamociare riesenia nemusia byt platne v kazdom pripade.
<<

LukasCh

Príspevky: 3

Registrovaný: Štv Feb 19, 2009 7:34 pm

Poslať Str Feb 25, 2009 8:17 am

Heh, a ja som tomu rieseniu tak veril :). No nic, hura na backtrack, ale ako tak rozmyslam tak jednym z rieseni by mohlo byt to generovanie vsetkych rieseni, podobne ako sme to robili pri tych zlodejoch, akurat budem generovat n ciferne cisla z cisel 0 az k-1 kde n je pocet suborov a tie cisla 0 az k-1 su CD na ktory dany subor napalime. Ja viem, toto je to super narocne riesenie ale existuje ak vsetko ostatne zlyha ;-)
<<

alef0

Site Admin

Príspevky: 621

Registrovaný: Štv Nov 16, 2006 8:57 am

Poslať Str Feb 25, 2009 9:42 am

Cize ked sa na to pozeram, greedy algoritmus bolo to, na co som poukazoval, ze nemusi fungovat?

Teda, ze sa nemusi oplatit brat hned najvacsi subor, lebo mozno sa oplati zobrat dva mensie vymenou za neskorsie optimum. Iny priklad na to, ze pazravost sa neoplaca, je Dijsktrov algoritmus na hladanie najkratsej cesty v grafe.
Lorem ipsum dolor sit amet.
<<

Pnr

Príspevky: 7

Registrovaný: Ned Feb 22, 2009 2:16 am

Poslať Štv Feb 26, 2009 5:33 pm

takze vpodstate by to mohlo ist cez best fit bin packing? zda sa ze ten na to potrebuje najmenej medii
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Štv Feb 26, 2009 5:48 pm

Pnr píše:takze vpodstate by to mohlo ist cez best fit bin packing? zda sa ze ten na to potrebuje najmenej medii


Len upozornujem, ze rozne "fit" algoritmy su heuristiky. Nieco, co moze zafungovat v mnohych pripadoch pomerne dobre, no nie stale. V zadani DU sa vsak vyzaduje garantovane rozhodnutie. A to vie zarucit jedine backtrack ...
<<

opteron1441

Príspevky: 2

Registrovaný: Uto Feb 17, 2009 4:54 pm

Poslať Sob Feb 28, 2009 3:05 pm

Mate uz niekto funkcnu 2 ulohu, lebo nejak mi to stale hadze chyby a som zvedavy ci uz to niekto spojazdnil :?: , skusal som to spravit cez dve matice ale nieco tam stale selze :evil:
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Sob Feb 28, 2009 6:07 pm

opteron1441 píše:Mate uz niekto funkcnu 2 ulohu, lebo nejak mi to stale hadze chyby a som zvedavy ci uz to niekto spojazdnil :?: ,


Predpokladam, ze chyby hadze tvoje riesenie a tvoje riesenie je rozne od inych. Preto asi to, ci niekto dalsi tu ulohu uz vyriesil, nie je relevantne ... :-)

V principe ulohu o Noematovi je mozne riesit 2 sposobmi. Prve riesenie je zalozene na pozorovani, ze to co hladame je nejaka permutacia cisel, ktore po dosadeni do prazdnych klietok nebude konfliktne. Teda problem ide zredukovat na generovanie vsetkych permutacii zadanej mnoziny cisel.

Dalsie (backtrackovske) riesenie je mozne zalozit na pozorovani, ze v kazdom okamihu su nejake cisla (cakajuce) pred archou a nejake cisla su bezkonfliktne umiestnene v klietkach archy. V takejto situacii dalsi postup moze byt nasledujuci:
- vyberieme prve cislo, co stoji vonku
- najdeme v arche prvu volnu klietku a vybrane cislo na tuto poziciu vlozime. Ak je umiestnenie konfliktne, tak ho vyhodime prec a skusime na toto miesto umiestnit ine cislo cakajuce vonku. Ak je umiestnenie nekonfliktne, tak skusime rekurzivne vyplnit zvysne klietky. Ak sa to podari, mame riesenie. A ak nie, tak cislo vyhodime prec (tak ako keby bolo konfliktne) a skusame dalsie cisla (druhe, tretie, ...) vonku.

Späť na PAZ1b

Kto je on-line

Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 3 hostia

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software.
Slovenský preklad.