Stránka 1 z 1

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

PoslaťNapísal: Sob Feb 21, 2009 10:03 am
od FeroG
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.

PoslaťNapísal: Pon Feb 23, 2009 10:19 pm
od LukasCh
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...

PoslaťNapísal: Pon Feb 23, 2009 10:52 pm
od FeroG
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 ...

PoslaťNapísal: Uto Feb 24, 2009 1:08 am
od Pnr
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 ...

PoslaťNapísal: Uto Feb 24, 2009 12:22 pm
od alef0
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 :-))

PoslaťNapísal: Uto Feb 24, 2009 2:23 pm
od LukasCh
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...

PoslaťNapísal: Uto Feb 24, 2009 8:33 pm
od FeroG
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.

PoslaťNapísal: Uto Feb 24, 2009 10:26 pm
od lochness42
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.

PoslaťNapísal: Str Feb 25, 2009 8:17 am
od LukasCh
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 ;-)

PoslaťNapísal: Str Feb 25, 2009 9:42 am
od alef0
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.

PoslaťNapísal: Štv Feb 26, 2009 5:33 pm
od Pnr
takze vpodstate by to mohlo ist cez best fit bin packing? zda sa ze ten na to potrebuje najmenej medii

PoslaťNapísal: Štv Feb 26, 2009 5:48 pm
od FeroG
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 ...

PoslaťNapísal: Sob Feb 28, 2009 3:05 pm
od opteron1441
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:

PoslaťNapísal: Sob Feb 28, 2009 6:07 pm
od FeroG
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.