Optimální algoritmus výpočtu

branchman1

Re: Optimální algoritmus výpočtu
« Odpověď #135 kdy: 28. 10. 2010, 20:40:29 »
A sme doma. A že takové bod (tvrzení) existuje musíš ukázat, jinak není důkaz korektní. jinými slovy - musíš věnovat extra pozornost existenci pevného bodu.
Právě že obecně nemusíš
Na zaklade coho funguje MI bez pevneho bodu? Pre mna je MI len nekonecne vela implikacii, na ktore sa opakovane aplikuje modus ponens. Pri modus ponens pri odvodzovani nestaci len \phi => \psi; treba mat aj platnost \phi.


Re: Optimální algoritmus výpočtu
« Odpověď #136 kdy: 29. 10. 2010, 02:54:57 »
Nekonečně mnoho tvrzení a nekonečně mnoho implikací se špatně zapisuje na papír. Takže místo
T(1)&T(2)&T(3)&...
se radši napíše
(pro každé n) (T(n))
a jsme úplně někde jinde.

No ale pokud bychom uvažovali konečnou indukci...
T(1)&T(2)&T(3)&...&T(z)
tak bychom skutečně mohli pomocí modus ponens dokazovat indukci:

pro slabou indukci bychom museli dokázat
T(1)
T(1)=>T(2)
T(2)=>T(3)
...
T(z-1)=>T(z)
a pak opakovaně aplikovat modus ponens

ale my máme silnou indukci, takže
T(1)
T(1)=>T(2)
T(1)&T(2)=>T(3)
...
T(1)&T(2)&...&T(z-1)=>T(z)

V minulém odstavci napíšu místo
T(1)
raději
tautologie=>T(1)

T(1) se odvodí pomocí modus ponens také:
z formulí
* tautologie
* tautologie=>T(1)
odvodím
* T(1)

obecně to pak vypadá tak, že
z formulí
* (pro každého předchůdce n) (T(n))
* (pro každého předchůdce n) (T(n)) => T(n)
odvodím
* T(n)

Potřebuji tedy dokázat pouze
* (pro každého předchůdce n) (T(n)) => T(n)

a nemusím tedy "věnovat extra pozornost pevnému bodu".
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

Logik

  • *****
  • 937
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #137 kdy: 29. 10. 2010, 13:31:50 »
Citace
Myslím tu teorii množin, kterou vám přednášeli na mff v prvním ročníku, a o kterou se opírá většina přednášek na mff, včetně MA. To znamená ZFC nebo GB, které jsou ekvivalentní.
Na MFF se v prvním ročníku žádná teorie množin nepřednáší (a na informatice se npřednáší nyní vůbec, za mého studia to byl nepovinný předmět k souborkám, které obsahovali totální základy TEMNA, na které ta přednáška potřeba v podstatě nebyla). A žádná přednáška (mimo ty vyloženě na TEMNO navazující) nestaví na temnu, nýbrž si definuje vlastní axiomy a z nich pak dokazuje.
Ono to ani jinak nejde - ona ani ZFC teorie není standardní, i v ní se lidi hádaj, jestli axiom výběru ano či ne - a hlavně je to zbytečné a (mimo pár speciálních důkazů, např. goodsteinova posloupnost, který zas ale nejdou dokázat v každym TEMNU) k ničemu.

V každém případě nejde prohlásit jednu teorii množin za privilegovanou - každá dokazuje jinou množinu tvrzení a přitom objekty MA jsou modelem všech teorií množin.

Citace
Relaci < musím nejprve definovat, ale jakmile to udělám, je to stejné < jako v analýze.
Ano? Jenže jaksi v analýze existují pouze menší čísla, nic jiného, zatímco v TEMNU je těch podmnožin trochu více (např. {{0}}). Takže při tvrzení o podmnožinách množiny musíš udělat více práce, než při tvrzení o číslech menších než n.

Citace
Rád se nechám poučit. Jaké vlastní axiomy má MA?
Mimo axiomy predikátové logiky s rovností axiomy definující vlastnosti tělesa reálných čísel a operací nad nimi (doufám, že si to pamatuju +- přesně).

Citace
A zajímal by mě příklad tvrzení, které nelze dokázat v analýze, ale v teorii množin ano.
http://cs.wikipedia.org/wiki/Goodsteinova_v%C4%9Bta

Citace
f(n)=min (f(i)+ f(j) ....)=min (P(i)+ P(j) ....)=P(n)
funguje i pro počátek, tedy pro n=1. Je zbytečné dokazovat zvlášť, že P(1)=f(1)
Pokud neukážeš, že existuje bod, tzn. n_0, pro které tvrzení platí nezávisle na platnosti tvrzení pro jiné n, je důkaz nekorektní. Protože takovej důkaz prostě nerozlišíš od důkazu, že a+1=a.
Že to ukážeš  (skoro) stejným tvrzením jako indukční krok je druhá věc, ale ukázat to prostě musíš.
« Poslední změna: 29. 10. 2010, 17:00:58 od Matyáš Novák »

Re: Optimální algoritmus výpočtu
« Odpověď #138 kdy: 29. 10. 2010, 17:16:30 »
Ano? Jenže jaksi v analýze existují pouze menší čísla, nic jiného, zatímco v TEMNU je těch podmnožin trochu více (např. {{0}}). Takže při tvrzení o podmnožinách množiny musíš udělat více práce, než při tvrzení o číslech menších než n.
Já už nevím, jak to jinak říct.
Při důkazech nemusíš stále používat axiomy dané teorie, to by byl vopruz, jak si říkal. Pomáháš si definicemi a větami. Jakmile definuješ pojem "2" a věty, které popisují potřebné vlastnosti přirozených čísel, můžeš klidně zapomenout jak bylo "2" zkonstruováno a jaké jsou její prvky a podmnožiny. V dalších úvahách si vystačíš s informací, že 2 je objekt, který má takové a takové vlastnosti.
Stejně tak se dopracuješ k větě o transfinitní indukci (posílal jsi na ni odkaz), která pojem podmnožina nebo prvek vůbec nezná, a mluví jenom o uspořádání.

Citace
Citace
Rád se nechám poučit. Jaké vlastní axiomy má MA?
Mimo axiomy predikátové logiky s rovností axiomy definující vlastnosti tělesa reálných čísel a operací nad nimi (doufám, že si to pamatuju +- přesně).

Citace
A zajímal by mě příklad tvrzení, které nelze dokázat v analýze, ale v teorii množin ano.
http://cs.wikipedia.org/wiki/Goodsteinova_v%C4%9Bta
Pamatuješ si to špatně, splývají ti matematické pojmy.

Ano, Goodsteinovu větu nelze dokázat v Peanově aritmetice, a lze ji dokázat v teorii množin. Jenomže
matematická analýza <> Peanova aritmetika.
Peanova aritmetika je něco diametrálně odlišného od MA: PA zkoumá pouze konečně velké objekty.

Stejně tak
matematická analýza <> teorie reálných čísel.
Pokud by ses spokojil s teorií založenou na axiomech tělesa, nemohl bys definovat pojmy jako posloupnost, funkce, míra.

Matematická analýza nejen že potřebuje teorii množin, ale dokonce i teorii množin s axiomem výběru.

Citace
Citace
f(n)=min (f(i)+ f(j) ....)=min (P(i)+ P(j) ....)=P(n)
funguje i pro počátek, tedy pro n=1. Je zbytečné dokazovat zvlášť, že P(1)=f(1)
Pokud neukážeš, že existuje bod, tzn. n_0, pro které tvrzení platí nezávisle na platnosti tvrzení pro jiné n, je důkaz nekorektní. Protože takovej důkaz prostě nerozlišíš od důkazu, že a+1=a.
Že to ukážeš  (skoro) stejným tvrzením jako indukční krok je druhá věc, ale ukázat to prostě musíš.
Pro jedničku tvrzení platí nezávisle na předchůdcích.
Ukazuješ to nikoli "skoro stejným tvrzením jako indukčním krokem", ale přímo indukčním krokem.
Pokud se mnou nesouhlasíš, řekni, které místo ve tvém důkazu indukčního kroku s jedničkou nefunguje.
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

Logik

  • *****
  • 937
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #139 kdy: 30. 10. 2010, 15:44:30 »
Citace
Ukazuješ to nikoli "skoro stejným tvrzením jako indukčním krokem", ale přímo indukčním krokem.
1) Výraz nic => B v logice neexistuje. Takže v prvním případě máš výraz typu
A_1 & A_2 ... A_n-1=> B_n
v druhym případě
B_1
Takže výraz pro 1 není stejný jako pro ostatní. To ti může připadat jako slovíčkaření, v každym případě se prostě musíš, aby byl důkaz korektní, explicitně ukázat, že pro 1 to platí bez předpokladů. Tzn. potřebuješ pevný bod.

Citace
Matematická analýza nejen že potřebuje teorii množin, ale dokonce i teorii množin s axiomem výběru.
To není pravda, alespoň matematická analýza tak, jak se učí na MFF. Tam se prostě zadefinují axiomy tělesa as jede se. Jestli pak existuje nějaká teorie (ať už ZFC nebo třeba Vopěnkova), ve který se daj axiomy MA dokázat z jejich axiomů, je možné, ale to nic nemění na tom, že MA má svoje axiomy a vyvozuje z nich.

To, že tomu tak je, vyplývá i z toho, kolik TEMEN existuje. Kdyby byla MA na TEMNU závislá, muselo by být jen jedno TEMNO. Těch teorií ale existuje hafo (byť některé jsou oblíbenější a některé nikoli) a ze všech se dá MA namodelovat.

Vem si pascal a stroják. Pascal může běžet na X různých architekturách počítače, na všech dá ale stejné výsledky. Každá architektura ale může běžet s různým strojovým kódem, dokonce i na některých můžeš "udělat" více než na jiné (abych se nezaplet do turingovské úplnosti tak např. zvuk, grafika, ....).
A třeba i jeden strojový kód je implementován více architekturami počítače.

A teď si dosaď:
PASCAL = MA
TEMNO = Stroják
Model TEMNA = Architektura PC

Je to úplně to samé. To, že PASCAL jde implementovat ve strojáku neznamená, že je pascal na strojáku závislej. Stejně tak není MA závislá na TEMNU.  Pascal je svébytnej systém se svojema pravidlama, kterej jde ve strojáku nadefinovat. Stejně tak lze nadefinovat MA v TEMNU.

Jedinej rozdíl je v tom, že zatímco MA byla ještě před TEMNEM, tak PASCAL byl až po strojáku, to ale jen zesiluje pozici MA jako svébytného systému.

Citace
Ano, Goodsteinovu větu nelze dokázat v Peanově aritmetice, a lze ji dokázat v teorii množin. Jenomže
matematická analýza <> Peanova aritmetika.
Peanova aritmetika je něco diametrálně odlišného od MA: PA zkoumá pouze konečně velké objekty.
Goodsteinova věta se dokazuje pomocí aritmetiky s nekonečny. A tato aritmetika z axiomů MA nijak nevyplývá. V MA se totiž sice používají objekty, které se v TEMNU modelují pomocí axiomu nekonečna, to ale neznamená, že v MA tyto objekty mají vlastnosti dané axiomem nekonečna.
(jinými slovy - v MA množina N není stejné povahy jako přirozené číslo - číslo je číslo a množina je množina - a tedy nejde na N aplikovat aritmetiku přirozených čísel).

Takže ano, matematická analýza <> Peanova aritmetika, ale také matematická analýza <> temno.

To, že MA není TEMNO vyplývá i z toho, že MA požaduje jedinečnost (až na izomorfismus) svého modelu. Ten je ale zajištěn pouze axiomatizací v jazyku druhého řádu, zatímco ZFC je teorie prvního řádu.

Citace
Pokud by ses spokojil s teorií založenou na axiomech tělesa, nemohl bys definovat pojmy jako posloupnost, funkce, míra.
Ehm? Proč ne? Běžně se to tak dělá. Ono když použiješ termín množina, tak to ještě neznamená, že používáš teorii množin. Použití teorie množin znamená použití axiomů TEMNA a definic čísel pomocí množin, a to se prostě v MA nedělá. Např. čísla nejsou definované jako speciální typ množin, ale jako entity na množinách nezávislé.

Citace
Matematická analýza nejen že potřebuje teorii množin, ale dokonce i teorii množin s axiomem výběru.
No jsem na informatice, takže možná nám něco zamlčeli, ale za celý studium nikdo axiom výběru při analýze nepotřeboval. Máš pro to nějaký důkaz?

Navíc, i kdyby byl např. axiom výběru nutný (o čemž dosti pochybuju, protože naopak pomocí AV se konstruují lebesgueovsky neměřitelné množiny, takže naopak axiom výběru MA spíš "kazí"), tak to furt neznamená, že se používá TEMNO.
Pořád to znamená zavedení dalšího axiomu mezi axiomy MA. Neboť pořád Tě to neomezuje na jednu konkrétní teorii množin s jedním konkrétním modelem: furt existuje hafo axiomatickejch systémů a na nich hafo modelů, z kterých lze vybudovat axiomatický systém MA (včetně axiomu výběru).

Citace
.... Jakmile definuješ pojem "2" a věty, které popisují potřebné vlastnosti přirozených čísel, můžeš klidně zapomenout jak bylo "2" zkonstruováno a jaké jsou její prvky a podmnožiny. ....
Stejně tak se dopracuješ k větě o transfinitní indukci (posílal jsi na ni odkaz), která pojem podmnožina nebo prvek vůbec nezná, a mluví jenom o uspořádání.
Ty jsi sem dal větu, kteorus nazval větou o MI kterou prej používáš. No a v tý se o podmnožinách mluví. Takže s nima pracovat musíš.

Ono i to, žes byl schopnej tu větu dát dohromady asi na čtvrtej pokus vypovídá o tom, že zavlékat tam TEMNO není zrovna rozumnej nápad.

Nebo teda používáš jinou větu o MI, která nepoužívá tvrzení o podmnožinách? A jak má člověk, kterej čte Tvuj důkaz vědět, kteoru větu používáš, když jich je teda víc??
« Poslední změna: 30. 10. 2010, 18:18:04 od Matyáš Novák »


Koly

Re: Optimální algoritmus výpočtu
« Odpověď #140 kdy: 11. 11. 2010, 08:34:22 »
Může se při výpočtu použít i lidská logika?
Například pro:
1ks 10000000Kč/ks
5ks 70Kč/ks
10ks 50Kč/ks

Není lepší při koupi 2 kusů koupit balení s 5 a 3 vyhodit?
Protože jsem našel jedno řešení a zajímá mě zda mohu použít i tento postup...

Logik

  • *****
  • 937
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #141 kdy: 11. 11. 2010, 11:42:37 »
Jde, ale je to jiný problém. Ale imho bude taky NP - protože ty čísla nemusí být tak extrémní, takže bude větší rozdíl za cenu jednoho balení, než mezi možnými kombinacemi. A pak se vyhazování nevyplatí. A jsme zase doma :-)

Michal Illich

Re: Optimální algoritmus výpočtu
« Odpověď #142 kdy: 26. 11. 2010, 16:06:01 »
Nečetl jsem tu diskuzi, ale jen to zadání -- ale tohle je typický problém batohu, které se programátorčata učiní už na základce, ne?

Uděláte si pole 0..Počet co chcete (v příkladu bylo 78). Do každé buňky si budete zapisovat nejlepší cenu a poslední přidaný výrobek. Na začátku budete mít v poli 0 hodnotu 0 (jakože nic koupíte za nic) a všude jinde nekonečno.

Pak to pole projdete s každým balíčkem (např. pro balíček 5ks za 90 Kč) a pro každé pole. Podíváte se o 5 polí dál a pokud to dokážete přidat výhodněji (např. předtím bylo na poli 5 nekonečno peněz, teď tam bude 0+90=90 Kč, což je očividně lepší) tak si to zapíšete - jak cenu, tak že jste se tam dostali s balíčkem 5 kusů.

Na konci si jen zpětně jdete od pole 78 pozpátku - vždy přeskočíte o tolik polí, kolik výrobků bylo v daném balíčku.

Celková složitost je Cena * Počet balíčků, což je super.

vandrovnik

Re: Optimální algoritmus výpočtu
« Odpověď #143 kdy: 04. 12. 2010, 15:31:06 »
Ahoj, já myslím, že tohle nebude ale fungovat v jeho případě, kdy může být limitovaný počet balíčků, které má k dispozici.
Složitost není závislá na ceně, ale ne požadovaném množství, ne?

Logik

  • *****
  • 937
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #144 kdy: 04. 12. 2010, 18:19:28 »
jojo, balíčků je neomezené množství, takže se to nedá dělat podle balíčků, ale podle počtu balíčků (začnu na nula balíčků a vždy k nejlepší ceně přidám všechny možné balíčky a tím upravím vyšší počty a skočím na počet o jedna větší).

Paja

Řešení
« Odpověď #145 kdy: 04. 12. 2010, 21:29:25 »
Kód: [Vybrat]
<?

  // definice baleni dle zadani. Klic je pocet ks, hodnota je cena za ks
  $baleni=array(1=>20,5=>18,10=>19,50=>17);
  // zadany pocet ks
  $ks=78;
  // priznak zda muzu vyhodit nejake kusy. Napriklad celkova cena pro 49 je vetsi nez pro 50ks
  // vyplati se koupit 50 a 1 vyhodit 
  $muzuvyhazovat=true;
  // nadale budu pouzivat baleni od nejvetsiho poctu kusu v baleni. Na objednavce to bude vypadat lepe.
  krsort($baleni);
  // kontrola jestli je zadane baleni 1ks. To zaruci moznost poskladat jakykoliv pocet ks
  if (!isset($baleni[1])) die("neni zadana cena baleni pro 1ks");
  // pokud je pocet ks vetsi nez nejmensi spolecny nasobek baleni (nsnb), staci pocitat optimalni ceny pro nsbn a zbytek po deleni
  // poctu nsbn. Napr. pokud chci 738 baleni a nsnb je 70, tak vysledek bude 10*cena(nsnb)+cena(38)
  // Proc? protoze mnozstvi nsbn lze poskladat z kterehokoliv baleni, lze ho poskladat i z baleni s nejnizi cenou za kus
 
  // nebudu tady psat eukliduv algoritmus at to neni dlouhe, spokojim se s kratkym orientacnim vypoctem. Kdyztak si ho sem dopiste.
  $nsnb=1;
  foreach ($baleni as $pocet=>$tmp)
   if (($nsnb % $pocet) !=0) $nsnb*=$pocet;
   
  // pocet kombinaci ktery musim spocitat. Je to bud ks nebo nsbn - co je mensi
  $n=$ks<$nsnb?$ks:$nsnb;

  /* ceny je pole, kde budu ukladat navrhy kombinaci pro jednotlive pocty.
   * klic bude pocet, hodnoty budou mit nasledujici strukturu   
   * cena .. celkova cena
   * index .. prvni index ze ktereho se sklada. Pokud jde o baleni, nebude existovat
   * viz nasledny vypocet. Druhy index je pocet-index. Napr. 42 s indexem 15 znamena ze
   * se sklada z vypoctenych kombinaci baleni 15 a (42-15) tj. 27   
   * pokud muzu vyhazovat, a bude index zaporny, znamena to ze mam koupit klic - index a zbytek vyhodit   
   */
  $ceny=array();
  // baleni 1ks je nutno vzit z definice.
  $ceny[1]["cena"]=$baleni[1];
  // vyplnim hodnoty pro vsechny ostatni pocty az po n
  for ($i=2;$i<=$n;$i++) {
    // kazde baleni lze vyjadrit jako kombinaci dvou jinych baleni o mensich mnozstvich
    // je jasne ze kombinaci je mnozstvi/2. A take je jasne ze jedna z techto kombinaci je nejlepsi
    // jako vychozi nejlepsi kombinaci ulozim soucet baleni 1 a o 1 mensi nez hledane
    $nejindex=1;
    $nejcena=$ceny[1]["cena"]+$ceny[$i-1]["cena"];
    // staci prohledavat do poloviny hodnoty
    for ($j=2;$j<intval($i/2);$j++) {
      if ($nejcena>$ceny[$j]["cena"]+$ceny[$i-$j]["cena"]) {
         $nejcena=$ceny[$j]["cena"]+$ceny[$i-$j]["cena"];
         $nejindex=$j;
      }
    }
    // ted zjistim jestli nahodou neni baleni o hledanem mnozstvi a nema lepsi cenu nez nalezena kombinace
    // pozor musim dat na prepocet celkove ceny a ceny za kus
    if (isset($baleni[$i]) and ($baleni[$i]*$i<$nejcena)) {
      // mam baleni a vychazi lepe
      $ceny[$i]["cena"]=$baleni[$i]*$i;
    } else {
      // ne, je potreba to poskladat
      $ceny[$i]["cena"]=$nejcena;
      $ceny[$i]["index"]=$nejindex;
    }
  } 
 
  // v pripade ze mam povoleno vyhazovat, zjistim jestli je vyssi cena pro nizsi index. Pokud ano, tak nastavuju zaporny index
  if ($muzuvyhazovat) {
    for ($i=$n-1;$i>=1;$i--)
      if ($ceny[$i+1]["cena"]<=$ceny[$i]["cena"]) {
        // vyplati se vyhodit, vyhazuju i v pripade ze je cena stejna
        if (!isset($ceny[$i+1]["index"]) or ($ceny[$i+1]["index"]>0)) {
          // je to cele baleni, napr. 50ks, nebo kladny index v baleni
          $ceny[$i]["index"]=-1;
        } else {
          // uz o 1 vyssi pocet je lepe vyhodit, takze index dam rovnou na to puvodni
          // napr zkoumam 48. 49 melo index -1 a ukazovalo na 50. Spoctena cena je porad vyssi nez pro 50, index dam -2 (=-1-1)
          $ceny[$i]["index"]=$ceny[$i+1]["index"]-1;
        }
        // a dosadim novou cenu
        $ceny[$i]["cena"]=$ceny[$i-$ceny[$i]["index"]]["cena"];
      }
  }
 
  // ted musim udelat vysledky
  // do pole objednat naskladam vsechny indexy baleni, hodnota bude pocet baleni
  // nastavim na 0
  $objednat=array();
  foreach ($baleni as $pocet=>$tmp) $objednat[$pocet]=0;
 
  // na naplneni si udelam rekurentni funkci (zabere to mene radku)
  // misto global to muze byt predavano odkazem, tohle je hezci
  function pridej($mnozstvi) {
    global $objednat,$ceny;
    if (!isset($ceny[$mnozstvi]["index"])) {
      // je to cele baleni
      $objednat[$mnozstvi]++;
    } else {
      pridej($mnozstvi-$ceny[$mnozstvi]["index"]);
      if ($ceny[$mnozstvi]["index"]>0) {
        // u slozeneho bez vyhazovani i druhou cast
        pridej($ceny[$mnozstvi]["index"]);
      }
    }
  }
 
  // pokud je ks>nsnb tak nejprve pridam nsnb nasobene poctem nsnb v ks
  $x=$ks;
  if ($x>$nsnb) {
    pridej($nsnb);
    $nasob=intval($ks/$nsnb);
    foreach ($objednat as $pocet=>$tmp) $objednat[$pocet]*=$nasob;
    $x-=$nasob*$nsnb;
  }
  pridej($x);
 
  // uz jen ukazat vysledky
  $celkem=0;
  echo "Objednavka:<hr>\n";
  foreach ($objednat as $pocet=>$chceme)
    if ($chceme) {
      echo "$chceme x baleni $pocet ks<br>\n";
      $celkem+=$baleni[$pocet]*$pocet*$chceme;
    }
  echo "<hr>CELEKEM $celkem penez<br>\n";
       

?>


Náročnost algoritmu :
vzhledem k principu nejmenšího společného násobku balení, je nejvyšší náročnost omezena počtem ks nebo nsnb - tím co je menší
Smysl má uvažovat jen do této hodnoty - n.

* paměťová
- pro ukládání typů balení a objednávky je úměrná pouze počtu typu balení. Lze zanedbat.
- pro předpočet cen je úměrná n

* výpočetní
- na počtu typů balení závisí jen předvyplňování polí přímo úměrné počtu balíčků. Lze zanedbat.
- výpočet hodnot :
  pro jednotlivý počet je potřeba x/2 výpočtů
  pro n hodnot je to suma(i/2) pro i od 1 do n. Tedy (n^2)/4
- pro uvažování vyhazování je třeba n výpočtů   
- pro vyhodnocení výsledku je v nejhorším případě (balení po 1ks) potřeba provést 2xn volání funkce pridej
Takže výsledná náročnost je n^2. NSNB ji ale pro velké počty kusů razantně omezuje
   
 

Logik

  • *****
  • 937
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #146 kdy: 04. 12. 2010, 22:52:42 »
Hezkej postřeh s nsnb, ale jinak

1) proč by mělo být zadání kde není balení po jednom kusu nelegální? Proč nemůžu mít balení se čtyřmi kusy a chtít jich osm. Obzvlášť, když mohu vyhazovat, tak mohu složit libovolný počet, stačí a by bylo alespoň jedno balení.
2) pokud můžeš vyhazovat, tak přeci musíš prohledat i stavový prostor nad počtem kusů, nestačí to utnout počtem kusů.
3) složitost je opět na požadovaný počet kusů, takže pseudopolynomiální
4) kostra tohodle řešení tu byla už asi třikrát :-)¨)

Paja

Re: Optimální algoritmus výpočtu
« Odpověď #147 kdy: 04. 12. 2010, 23:21:57 »
1/ jednoducha úprava - přidat nejnižší jednotku do balení menších než nejnižších balení. V případě že se nesmí vyhazovat, opravit podmínku tak aby vyhodila chybu v případě, že počet není možno složit z možných typů balení.
2/ To mne nenapadlo - holt chybka. Oprava : vždy počítat do nsnb (příklad pro 49ks by to teď našlo dražší cenu než je za balík 50ks)
3/ Tady bylo tuny diskuze, že to je NP problem.  A není. Někdo tady psal že je to lineární problém - tedy O(n). To bych chtěl vidět. O(n^2) omezené nsnb je slušné řešení. Netuším proč pseudopolynomiální a ne jen polynomiální.
4/ kostra je jasná. Akorát to nikdo hotové neposlal a navíc jsem tam dal to vyhazování. Přišlo mi to jako dobrý nápad - při lahvičce tramínu řešit školní úkol. A hlavně prokázat že to není NP problém.

Logik

  • *****
  • 937
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #148 kdy: 04. 12. 2010, 23:37:40 »
2) to není tak jednoduché - takhle si z toho udělal exponenciální problém. Při vhodném vstupu (samá prvočísla) Ti s každým kusem vstupu (jeden typ balení navíc)  vzroste složitost k krát, kde k je to prvočíslo...
3) A další kolo! Je NP. Jak zakóduješ chtěný počet n balení? Pomocí log(n) bitů.Takže závislost na velikosti vstupu m je exp(m)^2. A NP úplnost pracuje právě se složitostí v závislosti na délce vstupu: viz definice NP-úplnosti (třeba na wiki, je tam vcelku slušně). Pseudopolynomiální je ten algoritmus PRÁVĚ proto, že sice závisí polynomiálně, ale na něčem jiném, než na velikosti vstupu.
Vzhledem k tomu, že jak jsem ukázal ve 2, tak nsnb při vhodném vstupu roste exponenciálně, tak Tě myslím nezachrání ani omezení pomocí nsnb, byť je to hezká myšlenka.

Nic jsi tedy zatím neprokázal :-), ale stejně, na zdraví :-)

Paja

Re: Optimální algoritmus výpočtu
« Odpověď #149 kdy: 05. 12. 2010, 00:31:29 »
Jo není to jednoduché.
Pochopil jsem, že uvažuješ do velikosti vstupních dat i počet typů baleni. Tohle by mne nenapadlo - protože to neni v kontextu zadáni relevantní.
V tom připadě je nutno opravdu zakázat vyhazování - pak se to redukuje na polynomiální problém.

To s tím vyhazováním mne napadlo jako jednoduchá modifikace, tak jsem ji tam přidal. Protože tu o tom někdo psal. Nenapadlo mne, že počítat vždy do nsb změní P problém na NP problém.

Tedy že je původní zadání (bez vyhazování) polynomiální se mi prokázat podařilo.

A jak to je přesně s tím nsnb a vyhazováním. Úplně postačí prověřit min(ks,nsnb) + max(ks_v_baleni). Nemá smysl vyhazovat více ks než kompletní balení-1. Takže je z toho opět polynomiální problém. I s vyhazováním.