Fórum Root.cz

Hlavní témata => Vývoj => Téma založeno: Ondřej Vaniš 16. 08. 2010, 11:30:04

Název: Optimální algoritmus výpočtu
Přispěvatel: Ondřej Vaniš 16. 08. 2010, 11:30:04
Zdravím, potřeboval bych pomoci z vytvořením optimálního algoritmu.

Zadání:
V internetovém obchode je možno zakoupit zboží v různých baleních za různou cenu.
např.:

bal1 (1ks, 20kč/ks)
bal2 (5ks, 18kč/ks)
bal3 (10ks, 19kč/ks)
bal4 (50ks, 17kč/ks)

Zákazník požaduje např 78ks zboží a program by měl optimální počty balení vložit do košíku, aby to pro zázaníka bylo cenově nejvýhodnější.
Takže v tomto případě 1*bal4, 5*bal2, 3*bal1.
Napadá vás jiné řešení než zkoušet všechny možné kombinace a poté vyhodnotit která je nejvýhodnější. Je to časově celkem náročné.
Díky.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: eDISCO 16. 08. 2010, 11:39:45
Ahoj,

chcelo by to specifikaciu nejakeho prostredia/jazyku v ktorom to ma byt vytvorene, no kazdopadne skus prevod z arabskych cislic do rimskych.
google: decimal to roman algorithm
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: JaPe 16. 08. 2010, 11:55:35
Co to zkusit takhle :

Požadovaný počet kusů podělíš postupně celočíselně počtem kusů v jednotlivých baleních, (od nejlevnějšího po nejdražší), do dalšího kroku vstupuje vždy zbytek z předchozího dělení. Algoritmus končí ve chíli, kdy je zbytek 0.

78/50 = 1, zbytek 28
28/5 = 5, zbytek 3
3/10 = 0, zbytek 3
3/1 = 3, zbytek 0

Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Ondřej Vaniš 16. 08. 2010, 11:57:46
Ahoj,

chcelo by to specifikaciu nejakeho prostredia/jazyku v ktorom to ma byt vytvorene, no kazdopadne skus prevod z arabskych cislic do rimskych.
google: decimal to roman algorithm
Melo by to byt pro PHP.
A převod z arabskych cislic do rimskych neni stejna uloha ktera je popsana.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Ondřej Vaniš 16. 08. 2010, 12:05:12
Co to zkusit takhle :

Požadovaný počet kusů podělíš postupně celočíselně počtem kusů v jednotlivých baleních, (od nejlevnějšího po nejdražší), do dalšího kroku vstupuje vždy zbytek z předchozího dělení. Algoritmus končí ve chíli, kdy je zbytek 0.

78/50 = 1, zbytek 28
28/5 = 5, zbytek 3
3/10 = 0, zbytek 3
3/1 = 3, zbytek 0
Takto to mám uděláno teď ale ve specifických případech to nefunguje.
např.
bal1 (1ks, 100kč/ks)
bal2 (7ks, 10kč/ks)
bal3 (20ks 9kč/ks)
a zákazník požaduje 21ks

dle tohoto by vyšlo 1*bal3 + 1*bal1 výsledná cena 280kč
správně by mělo být 3*bal2 výsledná cena 210kč
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Adam 16. 08. 2010, 12:09:30
Co to zkusit takhle :

Požadovaný počet kusů podělíš postupně celočíselně počtem kusů v jednotlivých baleních, (od nejlevnějšího po nejdražší), do dalšího kroku vstupuje vždy zbytek z předchozího dělení. Algoritmus končí ve chíli, kdy je zbytek 0.

78/50 = 1, zbytek 28
28/5 = 5, zbytek 3
3/10 = 0, zbytek 3
3/1 = 3, zbytek 0

To nebude vzdy fungovat, napriklad pokud by byly ceny nasledujici:
bal1 (1ks, 12kč/ks)
bal2 (5ks, 8kč/ks)
bal3 (2ks, 8,50kč/ks)

A zakaznik si bude chtit koupit 6ks, tak pri koupi bal2 a bal1 zaplati 52kc a pri koupi 3x bal3 51kc...
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: JaPe 16. 08. 2010, 12:26:21
Co to zkusit takhle :

Požadovaný počet kusů podělíš postupně celočíselně počtem kusů v jednotlivých baleních, (od nejlevnějšího po nejdražší), do dalšího kroku vstupuje vždy zbytek z předchozího dělení. Algoritmus končí ve chíli, kdy je zbytek 0.

78/50 = 1, zbytek 28
28/5 = 5, zbytek 3
3/10 = 0, zbytek 3
3/1 = 3, zbytek 0
Takto to mám uděláno teď ale ve specifických případech to nefunguje.
např.
bal1 (1ks, 100kč/ks)
bal2 (7ks, 10kč/ks)
bal3 (20ks 9kč/ks)
a zákazník požaduje 21ks

dle tohoto by vyšlo 1*bal3 + 1*bal1 výsledná cena 280kč
správně by mělo být 3*bal2 výsledná cena 210kč

Grr. Tohle je trochu od boku:
Po ukončení algoritmu dle předchozího spočítat průměrnou cenu za kus (280/21 = 13,333) a najít balení s co nejmenším počtem kusů (zároveň menším, než požadovaný), jehož cena za kus je menší, než ten průměr. A tak pořád dokola, dokud existuje balení s menším počtem kusů než požadovaný a zároveň s cenou za kus menší než průměrná cena vypočtená v předchozím kroku.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Ondřej Vaniš 16. 08. 2010, 12:34:31
Citace
Grr. Tohle je trochu od boku:
Po ukončení algoritmu dle předchozího spočítat průměrnou cenu za kus (280/21 = 13,333) a najít balení s co nejmenším počtem kusů (zároveň menším, než požadovaný), jehož cena za kus je menší, než ten průměr. A tak pořád dokola, dokud existuje balení s menším počtem kusů než požadovaný a zároveň s cenou za kus menší než průměrná cena vypočtená v předchozím kroku.
Takové balení samozřejmě nalézt jde ale co s ním pak. Jaké balení vyhodit z předchozího výpočtu a nahradit novým, výhodnějším??
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: JaPe 16. 08. 2010, 12:42:40
Citace
Grr. Tohle je trochu od boku:
Po ukončení algoritmu dle předchozího spočítat průměrnou cenu za kus (280/21 = 13,333) a najít balení s co nejmenším počtem kusů (zároveň menším, než požadovaný), jehož cena za kus je menší, než ten průměr. A tak pořád dokola, dokud existuje balení s menším počtem kusů než požadovaný a zároveň s cenou za kus menší než průměrná cena vypočtená v předchozím kroku.
Takové balení samozřejmě nalézt jde ale co s ním pak. Jaké balení vyhodit z předchozího výpočtu a nahradit novým, výhodnějším??
Grr - já to nedopsal:
1) Najít balení s co nejmenším počtem kusů, jehož cena za kus je menší, než průměrná  dle prvního kroku a zopakovat celý algoritmus s tím, že začneš od tohoto balení.
2) To celé dokola, dokud existuje balení s cenou za kus menší než průměr z předchozího kroku a zároveň s počtem kusů menším, než požadovaný.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Ondřej Vaniš 16. 08. 2010, 12:51:11
Tak to vypadá že je to podobná úloha této.
http://cs.wikipedia.org/wiki/Probl%C3%A9m_batohu

takže žádné triviální řešení asi nebude  :-\
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Ondřej Vaniš 16. 08. 2010, 12:53:33
Citace
Grr - já to nedopsal:
1) Najít balení s co nejmenším počtem kusů, jehož cena za kus je menší, než průměrná  dle prvního kroku a zopakovat celý algoritmus s tím, že začneš od tohoto balení.
2) To celé dokola, dokud existuje balení s cenou za kus menší než průměr z předchozího kroku a zároveň s počtem kusů menším, než požadovaný.
Zkusím o tom ještě zauvažovat. Možná to nebude úplně 100%ní ale lepší než metoda celočíselného dělení a rychlejší než rekurzivní zkoušení kombinací.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: j. 16. 08. 2010, 14:29:22
Toto je typycky NP-uplny problem, zadne reseni s polynomialni slozitosti zname neni. Kdyz ale pohledas na google, mozna najdes nejake velice tricky subexponencialni reseni, vzhledem k pozadavkum (internetovy obchod, pocty radove v desitkach az stovkach kusu) je asi exponencialni reseni porad nejjednodussi. Proste fakt zkousej vsechno se vsim.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Ondřej Vaniš 16. 08. 2010, 15:29:24
Pro zajímavost zde je kód který používám
Kód: [Vybrat]
class Variation {
var $pieces_arr=array();
var $prices_arr=array();
var $sum_count=0;
var $sum_price=0;

function Variation() {

}

function setPieces($type, $count, $price){
$this->pieces_arr[$type] = $count;
$this->prices_arr[$type] = $count*$price;
$this->sum_count = array_sum($this->pieces_arr);
$this->sum_price = array_sum($this->prices_arr);
}
}

class VariationSolver {
var $itemsArr = array();
var $reqCount = 0;
var $BestVar;

function VariationSolver() {
$this->BestVar = null;
}

function setRequestedCount($count){
$this->reqCount = $count;
}

function addVariationItem($type, $piece, $price){
$this->itemsArr[] = array($type, $piece, $price);
}

function compute($level, $VarObj){
$max_level = sizeof($this->itemsArr)-1;
$increment = $this->itemsArr[$level][1];
for ($i = 0; $i==0 || ($i <= $this->reqCount && ($VarObj->sum_count+$increment)<=$this->reqCount) ; $i=$i+$increment) {
$VarObj->setPieces($this->itemsArr[$level][0], $i, $this->itemsArr[$level][2]);

if ($max_level>$level){
$this->compute($level+1, $VarObj);
}
else {
if ($VarObj->sum_count==$this->reqCount){
if ($this->BestVar == null || $VarObj->sum_price < $this->BestVar->sum_price){
$this->BestVar = $VarObj;
}
}
}
}
}

function getBestVar(){ //slow
$this->BestVar = null;
if (sizeof($this->itemsArr)>0){
$this->compute(0, new Variation());
}
return $this->BestVar;
}
}

//==== Vypocet ====
$VS = new VariationSolver();
$VS->setRequestedCount(100);
$VS->addVariationItem("N",1,100);    // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("B",2,95);     // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("A1",5,90);    // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("D",10,98);    // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("IC1",20,81);  // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("IC2",50,80);  // typ baleni, pocet kusu v baleni, cena za kus

print "<pre>";
print_r( $VS->getBestVar() );
print "</pre>";
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: pedro 17. 08. 2010, 19:04:55
Typicky laboratorni syndrom :-D Vazne veris, ze muze v realnem svete existovat/prodavat se baleni 1 ks za 100 Kc, kdyz baleni 7 ks stoji 70 Kc?
Jinak problem muze nastat i v realu v mnohem mensich radech, ale jenom tehdy, kdyz uspora dosazena koupi nejvyhodnejsiho baleni je nizsi, nez rozdil ceny baleni potrebneho pro dosazeni pozadovaneho poctu a dalsich vyhodnych baleni, ktere jsme nevzali.

Výše uvedený příklad od Adama:
bal1 (1ks, 12kč/ks)
bal2 (5ks, 8kč/ks)
bal3 (2ks, 8,50kč/ks)

Pri koupi bal2 je uspora proti bal3 5 * 0,50 = 2,50 a 2,50 je mensi, nez 12 - 8,50 = 3,50. V 99% procentech pripadu vyjde, ze uspora je vyssi a nebudes muset resit dalsi moznosti, takze takovy pristup by mel byt vypocetne mene narocny, nez zkouset vsechno se vsim, tedy za predpokladu, ze pocet moznych baleni je vyssi, nez 3 v nasem pripade ;-)
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Ondřej Vaniš 17. 08. 2010, 21:36:33
Typicky laboratorni syndrom :-D Vazne veris, ze muze v realnem svete existovat/prodavat se baleni 1 ks za 100 Kc, kdyz baleni 7 ks stoji 70 Kc?
Jinak problem muze nastat i v realu v mnohem mensich radech, ale jenom tehdy, kdyz uspora dosazena koupi nejvyhodnejsiho baleni je nizsi, nez rozdil ceny baleni potrebneho pro dosazeni pozadovaneho poctu a dalsich vyhodnych baleni, ktere jsme nevzali.

Výše uvedený příklad od Adama:
bal1 (1ks, 12kč/ks)
bal2 (5ks, 8kč/ks)
bal3 (2ks, 8,50kč/ks)

Pri koupi bal2 je uspora proti bal3 5 * 0,50 = 2,50 a 2,50 je mensi, nez 12 - 8,50 = 3,50. V 99% procentech pripadu vyjde, ze uspora je vyssi a nebudes muset resit dalsi moznosti, takze takovy pristup by mel byt vypocetne mene narocny, nez zkouset vsechno se vsim, tedy za predpokladu, ze pocet moznych baleni je vyssi, nez 3 v nasem pripade ;-)
Samozrejme vim ze tato situace v realu by nastat nemela. jen jsem zvolil takto vysoke cislo kvuli nazornosti.
Stale nechavam puvodni jednodussi algorytmus zalozeny na celociselnem deleni ktery pro 99% situaci bude optimalni. jen jsem zde chtel zjistit zda neexistuje 100% metoda ktera neni vypocetne narocna, coz asi neni.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Waseq 17. 08. 2010, 21:57:23
Pokud je výpočet složitý, a tady asi bude, zbývá ještě možnost si průběžná řešení ukládat. A při každém požadavku se podívat, zda tuto variantu chtěl někdo předtím. Ano -> nemusím počítat, ne -> spočítám, uložím.
Nevhodné při častých změnách cen. A určitě ohlídat žádosti o milion balení, při exponenciální složitosti by to mohlo trvat trošku dýl.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: pedro 18. 08. 2010, 13:41:31
Samozrejme vim ze tato situace v realu by nastat nemela. jen jsem zvolil takto vysoke cislo kvuli nazornosti.
Stale nechavam puvodni jednodussi algorytmus zalozeny na celociselnem deleni ktery pro 99% situaci bude optimalni. jen jsem zde chtel zjistit zda neexistuje 100% metoda ktera neni vypocetne narocna, coz asi neni.

Souhlas, taky bych nechal to, co funguje v 99% pripadu. Zivot neni rizeni jaderne elektrarny. Zadne elegantni reseni me samotneho nenapada.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: kosta 18. 08. 2010, 15:09:34
jestli neni jednodussi dat ceny podle poctu ks, napr.
cena1 = 1-4 ks
cena2 = 5-9ks
cena3 = 10ks a vic
nemusis nic pocitat
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: mt 18. 08. 2010, 15:25:34
Škoda nevyužít práce generací studentů FELu, kteří se problémem batohu zabývali v předmětu 36PAA ;-) Nějaké info třeba zde:

http://tumic.wz.cz/fel/online/36PAA/3/ (http://tumic.wz.cz/fel/online/36PAA/3/)
Název: řešení v C++
Přispěvatel: Honza S. 18. 08. 2010, 23:25:32
Autor příspěvku má pravdu, řešení optimální sestavy balíčků je podobné problému batohu. Jednoduchý algoritmus s několika do sebe vnořenými for-cykly zvládne takovou úlohu vyřešit jen pro malý počet velikostí balíčků a kusů zboží. Uznávám že to může v praxi stačit ale řešení inspirované problémem batohu a dynamickým programováním bude pro větší vstupy výrazně rychlejší:

Kód: [Vybrat]
/*
   (c) Jan Stoklasa 2010 (http://www.lisp.cz)
   Reseni ulohy nejlevnejsi sestavy balicku daneho zbozi s pouzitim upraveneho problemu batohu.
   Na vstupu je počet kusů které chce zákazník koupit, počet balíčků a pak dvojice počet kusů v balíčku-cena, například vstup

   5
   2
   1 3
   2 2

   znamená že zákazník chce koupit 5 kusů zboží a na vstupu jsou 2 balíčky - balíček obsahující 1 kus s jednotkovou cenou tři a balíček
   obsahující 2 kusy s jednotkovou cenou 2.
   Program vytiskne nejlevnější dosažitelnou cenu, mohl by tisknout i sestavu balíčků ale to už nechávám za domácí úkol ;-)
*/   
 
#include <limits.h>
#include <iostream>
#include <algorithm>

using namespace std;

struct balicek
{
  int pocet_kusu;
  int cena_za_kus;
};

bool cmp(const struct balicek& a, const struct balicek& b)
{
  if(a.pocet_kusu == b.pocet_kusu)
    return a.cena_za_kus < b.cena_za_kus;
  else
    return a.pocet_kusu < b.pocet_kusu;
}

int main(void)
{
  int N;
  int POCET_KUSU;

  cin >> POCET_KUSU >> N;
  struct balicek* a = new struct balicek[N]; 
  int* m = new int[POCET_KUSU+1];

  for(int i=0;i<N;i++)
    cin >> a[i].pocet_kusu >> a[i].cena_za_kus;
  sort(a,a+N,cmp);

  for(int i=0;i<POCET_KUSU+1;i++)
    m[i]=INT_MAX;
  m[0]=0;

  for(int i=1;i<POCET_KUSU+1;i++)
    for(int j=0;(j<N)&&(a[j].pocet_kusu<=i);j++)
      if(m[i-a[j].pocet_kusu]<INT_MAX)
        m[i]=min(m[i],a[j].pocet_kusu*a[j].cena_za_kus+m[i-a[j].pocet_kusu]);

  if(m[POCET_KUSU]<INT_MAX)
    cout << "Reseni: " << m[POCET_KUSU] << endl;
  else
    cout << "Pozadovany pocet kusu neni mozne poskladat z dostupnych balicku" << endl;

  delete [] a;
  delete [] m;
}


Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: vh 19. 08. 2010, 14:22:10
Kouknul jsem na zadni jen zbezne, ale vypada to jako uplne typicka (ale strasne trivialni) uloha linearniho programovani.
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: vokoun 19. 08. 2010, 15:33:25
Kouknul jsem na zadni jen zbezne, ale vypada to jako uplne typicka (ale strasne trivialni) uloha linearniho programovani.
To bude proto, že ses kouknul jen zběžně. :)
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: vh 19. 08. 2010, 15:46:27
Hmm, jasny je tam jaksi jen jedna omezujici podminka :) priste se radeji budu koukat pozorneji :)
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Václav Zajíc 27. 09. 2010, 10:53:25
Rekl bych, ze je to klasicka aplikace problemu batohu (jak narvat do batohu optimalni mnozstvi s ruznou vahou a dulezitosti)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 29. 09. 2010, 14:50:25
Zadání:
V internetovém obchode je možno zakoupit zboží v různých baleních za různou cenu.
např.:
bal1 (1ks, 20kč/ks)
bal2 (5ks, 18kč/ks)
bal3 (10ks, 19kč/ks)
bal4 (50ks, 17kč/ks)

Zákazník požaduje např 78ks zboží a program by měl optimální počty balení vložit do košíku, aby to pro zázaníka bylo cenově nejvýhodnější.
Dle mého názoru je to jednoduché, a o žádný NP-úplný problém se nejedná:

Algoritmus bude postupně hledat ideální nákupy pro k ks zboží, kde k=1 až 78. Pro každé k si ideální nákup zapamatuje.
Známe-li ideální nákupy pro 1 ks až např. 50 ks ( I(1), I(2), I(3)... jsou ideální nákupy), zjistíme ideální nákup pro 51 ks jako nejlevnější z těchto nákupů:
1] jednotlivá balení (nákup je tvořen jedinou položkou, tedy jedním balením (dle zadání je to 1ks nebo 5ks nebo 10ks nebo 50ks)
2] spojení dvou ideálních nákupů  I(50) a I(1); dále I(49) a I(2); dále I(47) a I(3) atd.

(Důkaz: rozložíme-li ideální nákup pro k ks zboží na jakékoli dvě skupiny o počtech zboží k1, k2, kde k1+k2=k, jsou příslušné dva nákupy pro k1 a k2 také ideální. Nelze-li nákup rozložit, jedná se o nákup typu 1] )
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ondřej Vaniš 29. 09. 2010, 18:24:38
Zadání:
V internetovém obchode je možno zakoupit zboží v různých baleních za různou cenu.
např.:
bal1 (1ks, 20kč/ks)
bal2 (5ks, 18kč/ks)
bal3 (10ks, 19kč/ks)
bal4 (50ks, 17kč/ks)

Zákazník požaduje např 78ks zboží a program by měl optimální počty balení vložit do košíku, aby to pro zázaníka bylo cenově nejvýhodnější.
Dle mého názoru je to jednoduché, a o žádný NP-úplný problém se nejedná:

Algoritmus bude postupně hledat ideální nákupy pro k ks zboží, kde k=1 až 78. Pro každé k si ideální nákup zapamatuje.
Známe-li ideální nákupy pro 1 ks až např. 50 ks ( I(1), I(2), I(3)... jsou ideální nákupy), zjistíme ideální nákup pro 51 ks jako nejlevnější z těchto nákupů:
1] jednotlivá balení (nákup je tvořen jedinou položkou, tedy jedním balením (dle zadání je to 1ks nebo 5ks nebo 10ks nebo 50ks)
2] spojení dvou ideálních nákupů  I(50) a I(1); dále I(49) a I(2); dále I(47) a I(3) atd.

(Důkaz: rozložíme-li ideální nákup pro k ks zboží na jakékoli dvě skupiny o počtech zboží k1, k2, kde k1+k2=k, jsou příslušné dva nákupy pro k1 a k2 také ideální. Nelze-li nákup rozložit, jedná se o nákup typu 1] )
V tomto případě je to jednoduché ale zkuste to vypočítat např pro 1000ks to už je jiná.
Pak se dostaneme k tomuto a*k1+b*k2+c*k3+d*k4=k.
Takže opět NP-úplný problém :-/
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 29. 09. 2010, 21:34:40
Ale kdepak.
I pro 1000 ks bude optimální nákup hledán mezi spojeními DVOU nákupů s počtem ks <1000.
Časová náročnost algoritmu je kvadratická.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 29. 09. 2010, 22:37:18
Máš a nemáš pravdu. To tvoje řešení je kvadratický a funguje, ale není kvadratický vzhledem k velikosti zadání - je to něco jako kdybys tvrdil, že řadit lze rychlejc než nlogn, protože radix sort.
Problém je v tom, že je to kvadratický vzhledem k chtěný ceně, tak je ale exponenciální vzhledem k velikosti vstupu (chtěný počet n se zapíše pomocí log n cifer).
Nicméně máš pravdu, že je to asi nejrozumější možný řešení. :-)

Více viz pseudopolinomiální algoritmy.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 30. 09. 2010, 00:02:40
"chtěná cena" - ta je přece neznámá, chtěná cena je ta nejmenší možná.
Asi jsi měl na mysli, že algoritmus je kvadratický vzhledem k požadovanému počtu koupených kusů - s tím souhlasím.
"velikost vstupu" - to máš na mysli počet elementárních balení (4 balení (1, 5, 10 , 50 ks) v našem zadání)? Vzhledem k počtu elementárních balení je časová náročnost programu lineární (lineární kombinace, které se ve vnitřním cyklu porovnávají, se lineárně prodlužují).

Takže žádnou exponencionální náročnost nevidím, maximálně kubickou, pokud budou proměnné jak počet požadovaných kusů tak počet elementárních balení, a budeme předpokládat že rostou "stejně rychle".
Podle mě ale lze počet elementárních balení považovat za proměnnou veličinu pouze ve velmi speciálních případech. Rozhodně ne tehdy, pokud se musí nejprve nějaký obchodník rozhodnout, že nabídne k prodeji nové balení, a někdo je pak bude muset přidat ručně do systému. Ano tehdy, pokud budou balení a jejich ceny určovány automatizovaně - budou vypočteny třeba na základě cen na trhu, a to i pro velmi (neomezeně) velká balení.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ondřej Vaniš 30. 09. 2010, 00:46:10
Citace
Algoritmus bude postupně hledat ideální nákupy pro k ks zboží, kde k=1 až 78. Pro každé k si ideální nákup zapamatuje.
A jakým způsobem zjistíš že je nákup ideální. To je práve základní zadání úlohy.
Ideálním nákupem je myslíš co? Kombinaci různých balení která má množství rovno k?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 30. 09. 2010, 01:31:53
Terminologie:
Elementární balení: to je snad jasné, v našem zadání bal1 (1ks, 20kč/ks), bal2 (5ks, 18kč/ks) atd.
Nákup: libovolná lineární kombinace elementárních balení (koeficienty jsou celočíselně nezáporné). např. 15* bal1 + 1*bal3 + 3*bal4
Jestliže do lineární kombinace dosadíme počty kusů v baleních, získáme počet nakoupených kusů zboží.
Jestliže do lineární kombinace dosadíme ceny balení, získáme cenu nákupu.
Ideální nákup I(k): uvažujme množinu všech nákupů, kterým nakoupíme k zboží (resp. alespoň k zboží - to záleží na zadání). Ideální nákup je každý takový nákup, který dosahuje v rámci této množiny minimální cenu.

A jakým způsobem zjistíš že je nákup ideální. To je práve základní zadání úlohy.
Ideální nákup zjistím tak, že porovnám ceny všech nákupů (dosazováním do lineární kombinace - viz odstavec výše) uvedených v bodech 1] a 2] v mém prvním příspěvku.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ondřej Vaniš 30. 09. 2010, 09:04:05
Ano to jsi popsal naprosto přesně.
Ale jakým způsobem dokážeš vypočítat tuto rovnici?
a*bal1+b*bal2+c*bal3+d*bal4=PozadovanyPocet

Kromě dosazování za a,b,c,d a zjištování jestli se rovna pozadovanemu poctu jsem nenasel.
Nebo mi neco uniklo?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 30. 09. 2010, 13:45:41
U nákupů typu 1] zjišťuji snadno, zda obsahují požadovaný počet.
U nákupů typu 2] to nemusím zjišťovat, protože to vím: Chci 51 ks zboží, a nákup I(3)+I(48) prostě obsahuje 51 kusů zboží. Včechny nákupy ve skupině 2] obsahují 51 ks zboží.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 30. 09. 2010, 13:49:17
slowthinker: samozřejmě chtěnej počet kusů, je to jen jiná formulace problému batohu, tak sem se upsal.

Tak ještě jednou a polopaticky. Tys navrhnul algoritmus, kterej je závislej kvadraticky na počtu chtěnejch kusů. A pomocí kolika bitů zakóduješ že chceš n kusů? Já to umim do log(n) bitů.
Takže vstup velikosti v=log_2(n) poběží rychlostí n^2. Proto n=exp_2(v) a tedy výsledná rychlost pro vstup v bitů je exp_2(v)^2. Samozřejmě s nějakym tim očkem, by to bylo precizně :-)
Jinými slovy, přidáním jednoho bitu na vstupu se ti zvýší čas čtyřnásobně. To prostě není polynomiální složitost...

Složitost algoritmu se vždy udává vzhledem k velikosti vstupu, nikoli k užitým hodnotám. Takže i když vymyslíš algoritmus, kterej je polynomiální, ale na něčem jinym než na velikosti vstupu, tak to nic neříká o náležitosti do NP. Btw. vymýšlíme tady opravdu kolo, tomudle algoritmu se říká pseudopolynomiální, patří mezi takzvané dynamické programování a učí se o nich asi v každym v základním kursu složitosti a NP úplnosti a už tu padly i linky na preciznější formulace. Zkus pohledat po netu, je tam hafo online skript.

PS:
Je to rozdíl oproti např. úlohám na setřídění, kde je daná složitost nikoli VELIKOSTÍ tříděných čísel, ale jejich POČTEM (přesněji čas porovnání dvou čísel roste s logaritmem jejich hodnoty respektive lineárně vzhledem k velikosti vstupu, takže tam je opravdu "nejdražší" samotné třídění: na porovnání dvou čísel lze hledět jako na atomickou operaci, protože je dražší zdvojnásobit počet čísel než zdvojnásobit možnou velikost tříděných čísel).


Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Martin Prokš 30. 09. 2010, 15:01:43
Hmm,

z prvniho nebo druheho semestru matematiky na CVUT FSI: hledani extremu funkce: parcialni derivace rovny nule -> pro dane zadani soustava linearnich rovnic stupne (od boku, nepocitam to, takze se mozna o jednicku spletu) n-1 stupne (n = pocet baleni). V tomto pripade to povede sice na necele reseni, ktere bude treba zaokrouhlit. Nic sloziteho. Symbolicky vyresit a je to. Smitec.

Matematicky ukol na ctvrt hodky pro studenta CVUT FSI ktery ma zkousku z matiky z parcialek za 3. Snazte se, preci jste lepsi ;-)
Název: Re: Optimální algoritmus výpočtu.
Přispěvatel: Karel 30. 09. 2010, 15:04:20
Hmm, jasny je tam jaksi jen jedna omezujici podminka :) priste se radeji budu koukat pozorneji :)

A to nestačí? Podle mě to je lineární programování. Minimalizuje se cena, neznámé jsou počty jednotlivých balení a omezující rovnice je daná součtem kusů = vyžádaný počet kusů. Viz http://cs.wikipedia.org/wiki/Lineární_programování (matice A nemusí být čtvercová).
Pro lin. programování existují P algoritmy, otázka je se vyplatí je implementovat. Problém je, že lin. prog. řeší úlohu v reálných číslech, takže výsledky je třeba upravit (zaokrouhlit nqa celá balení), což zavádí určitou chybu. Řešení pomocí problému batohu by tuto chybu eliminovalo, ale za cenu NP algoritmu.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 30. 09. 2010, 18:22:42
Přestaňte už konečně vymejšlet kolo. :-)
Lineární programování??? Parciální derivace???
Ufff. Tam vám jaksi kupodivu vždycky vyjde, že máte vzít 0.35467 kusů balení s nejnižší cenou za kus. Na to nemusim derivovat, abych todle určil, ani si dělat ty úžasný mentální tabulky na linprog.

Slowthinker postnul nejlepší řešení  (a pár lidí před ním odkaz na něj), nic lepšího se vymyslet nedá, je to prostě NP úplnej problém v trochu jinym ošacení.
Když už chcete nějaký přibližný řešení, tak se nabízí hladovej algoritmus, ale ten tady v podstatě taky zazněl (beru vždy nejlevnější balení, který se mi ještě vejde).



Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ghost 30. 09. 2010, 18:34:35
Je to jen mirne upraveny problem batohu. Prepokladam, ze muzu pouzit treba dve baleni po 20ks, pokud neni opakovani mozne tak je to klasicky batoh.
Nalezeni vzdy optimalni reseni.
1 hruba sila
2. B&B
3. dynamicke programovani

U prvnich dvou jde jen o to napsat generovani unikatnich (aby se nebloudilo ve stavovem prostoru, tj. aby to byl strom ) posloupnosti. V pripade bez opakovani vkladani je to trivialni problem (kdyztak popisu). Druhy pripad je akorat rozsiren o orezavani - tj nebudu expandovat dalsi stavy, kdyz vim, ze budou vzdy horsi, nez nejlepsi dosud nalezene reseni. A dale nebudu expandovat stavy, ktere zarucene nevedou k reseni. Oboji jde napsat velice jednoduse.

Dynamicke programovani je rychlejsi (a taky asi narocnejsi na pochopeni). ale predpoklada jiste vlastnosti problemu - takove reseni je pak pseudopolynomialni a zalezi jen na velikosti problemu a dalsim parametru (treba cene).


Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 30. 09. 2010, 23:30:58
Takže žádnou exponencionální náročnost nevidím, maximálně kubickou, pokud budou proměnné jak počet požadovaných kusů tak počet elementárních balení, a budeme předpokládat že rostou "stejně rychle".
Podle mě ale lze počet elementárních balení považovat za proměnnou veličinu pouze ve velmi speciálních případech. Rozhodně ne tehdy, pokud se musí nejprve nějaký obchodník rozhodnout, že nabídne k prodeji nové balení, a někdo je pak bude muset přidat ručně do systému. Ano tehdy, pokud budou balení a jejich ceny určovány automatizovaně - budou vypočteny třeba na základě cen na trhu, a to i pro velmi (neomezeně) velká balení.
Teď mi došlo, že tohle je nesmysl. Předpokládal jsem, že ve vnitřním cyklu je třeba počítat ceny I(48) a I(3) sečtením lineárních kombinací, a pak teprve je možné je sčítat. To ale není pravda: je jednodušší si ceny I(48) a I(3) pamatovat.
Takže se vždy jedná o kvadratickou náročnost: algoritmus je tvořen dvěma vnořenými cykly a ve vniřním cyklu se v zásadě jenom sečtou dvě čísla (např. ceny I(48) a I(3)) a porovnají se s dočasným minimem.

@Matyáš Novák:
K tvému polopatickému vysvětlení mám tři zásadní výhrady:

Složitost algoritmu se vždy udává vzhledem k velikosti vstupu, nikoli k užitým hodnotám.
1) Udávat ASYMPTOTICKOU složitost algoritmu v závislosti na velikosti čísel tvořících vstup by byl principiální nesmysl, protože v praxi mají hodnoty na vstupu vždy OMEZENOU velikost (ještě jsem neviděl program, který by byl zařízen na příjem neomezeně velkých čísel na vstupu).

2) Pokud by se takto měřila časová náročnost algoritmů, dala by se tvoje úvaha aplikovat na všechny algoritmy (včetně třídění). I obyčejný součet dvou čísel (tj. úloha s obecně uznanou konstantní náročností) by tedy podle tebe měl exponenciální náročnost, nebo  lineární, pokud uznáš bod 3) níže.

Jinými slovy, přidáním jednoho bitu na vstupu se ti zvýší čas čtyřnásobně.
3) Někde bude chyba. I když budu předpokládat stroj, který umí jenom bitové operace, zdvojnásobením počtu bitů se doba sčítání zdvojnásobí. Lineární závislost, nikoli exponencionální.

Je to rozdíl oproti např. úlohám na setřídění, kde je daná složitost nikoli VELIKOSTÍ tříděných čísel, ale jejich POČTEM
Ten rozdíl opravdu nevidím.
Uvědom si, jak jsou atomické operace u třídění a "mého algoritmu" podobné: u třídění se jedná o porovnání, u "mého algoritmu" o součet dvou čísel a pak porovnání. To je jedno a to samé.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 01. 10. 2010, 17:29:22
Tvuj nick je přesnej, tak ještě jednou. :-) :-)
Citace
1) Udávat ASYMPTOTICKOU složitost algoritmu v závislosti na velikosti čísel tvořících vstup by byl principiální nesmysl...
Ale to právě děláš ty!!! Vždyť ty měříš složitost dle požadovaného počtu předmětů - čili podle velikosti jednoho čísla na vstupu, což je právě blbina (respektive není to blbina, ale takový algoritmus se nazývá nikoli polynomiální ale pseudopolinomiální).

Složitost algoritmu se prostě měří dle závislosti rychlosti (popř. spotřebované paměti) na velikosti (počtu bitů) vstupu. (Pokud ji chceš měřit podle něčeho jinýho, můžeš, ale pak nemá smysl se bavit např. o NP atd... - na spoustu NP problémů existují pseudopolynomiální algoritmy - v podstatě z definice NPúplnosti pro všechny NP úplné).

Pokud chceš Tedy měřit rychlost tvého algoritmu dle velikosti čísla udávajícího žádaný počet, musíš to dělat podle velikosti vstupu toho čísla. Ale tam je exponenciální závislost.
 
Citace
Někde bude chyba. I když budu předpokládat stroj, který umí jenom bitové operace, zdvojnásobením počtu bitů se doba sčítání zdvojnásobí. Lineární závislost, nikoli exponencionální.
Chci 16 kusů (tzn vstup čtyři bity 1000). Jelikož tvuj algoritmus má závislost kvadratickou na požadovaný počet kusů, rychlost bude o(16^2)
Chci 32 kusů (tzn. vstup pět bitů 10000). Rychlost bude o(32^2) = 4*o(16^2). Tzn čtyřikrát větší.

Vůbec nejde o rychlost sčítání ale o to, že rychlost je kvadratický vzledem k něčemu, co jde na vstupu logaritmicky kódovat a tedy exponenciální k velikosti vstupu.

Citace
Uvědom si, jak jsou atomické operace u třídění a "mého algoritmu" podobné: u třídění se jedná o porovnání, u "mého algoritmu" o součet dvou čísel a pak porovnání. To je jedno a to samé.

* Znova - u třídění NEZÁVISÍ na tom, jak jsou tříděná čísla velká, závisí na tom, KOLIK jich na vstupu je. Zdvojnásobením počtu čísel se zdvojnásobí velikost vstupu (a 2*log(2) zpomalí výpočet).
* U tvého algoritmu závisí počet kroků na VELIKOSTI čísla, nikoli na jejich POČTU. Zdvojnásobení čísla se ale vstup prodlouží pouze o jeden bit. Tzn. jde o závislost na něčem jiném než na velikosti vstupu.
(že jsou na vstupu pak ještě data udávající počty ceny různě velkých balení je irelevantní - s jejich větším počtem rychlost poroste max lineárně, takže je můžeme zanedbat (stejně jako u třídění velikost tříděných čísel), jediné co hraje roli je požadovaný počet kusů).

Vůbec tady nejde o složitost porovnání či sčítání, ty mají lineární složitost. Jde o to, jak ovlivní nárůst délky vstupu počet operací. Ta je u třídění daná jako nlog(n), kde n je počet tříděných prvků a u tvého algoritmu exp(n)^2, kde n je počet bitů, kterým je zapsán
chtěný počet kusů.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: petr 01. 10. 2010, 22:21:06
Citace
Ufff. Tam vám jaksi kupodivu vždycky vyjde, že máte vzít 0.35467 kusů balení s nejnižší cenou za kus. Na to nemusim derivovat, abych todle určil, ani si dělat ty úžasný mentální tabulky na linprog.
Lineární programováni by opravdu šlo použít(ILP - integer linear programing) a vypadli by správné výsledky. Jediná nevýhoda je složitost, protože ILP úlohy jsou NP-úplné, a tak ILP řešení funguje v exponenciálním čase.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 02. 10. 2010, 01:04:00
@Matyáš Novák
:) ano, můj nick je přesný. Lepší myslet pomalu než blbě jako někteří, které nechci jmenovat :p

Po mnohahodinovém úsilí mi došlo, co mi chceš sdělit. Veškeré naše nepochopení se zřejmě točí kolem tvé následující věty:

Složitost algoritmu se prostě měří dle závislosti rychlosti (popř. spotřebované paměti) na velikosti (počtu bitů) vstupu.
(místo "rychlosti" má být zřejmě "doby běhu")

To je podle mne špatný způsob měření. Vysvětlím na dvou příkladech:

_______________________________________________________
Příklad 1

Porovnejme následující algoritmy:
Algoritmus A)
Na vstup dostane přirozené číslo n, spočte jeho faktoriál

Algoritmus B)
Na vstup dostane n čísel, spočte jejich součin

Algoritmus C)
Na vstup dostane čísla 1, 2 ,3, 4 ...n , ověří vzestupnost posloupnosti, pak spočte jejich součin stejným postupem jako A)

Všechny tři algoritmy mají stejný charakter: jedná se o jeden for cyklus od 1 do n, uvnitř cyklu se pouze násobí (A a C jsou dokonce v podstatě totožné). Tvrdím proto, že časová náročnost všech algoritmů je stejná. A také tvrdím, že způsob určování časové náročnosti, který toto popírá, nemá z praktického hlediska žádný význam (dále budu zkráceně říkat "je špatný")

Tvůj způsob určování časové náročnosti (tj. délka běhu programu striktně vztažená k bitové délce vstupu) je tedy špatný.
Je to způsobeno tím, že vstupy algoritmů A), B) a C) mají jistou charakteristiku (zcela nezávislou na bitové délce vstupu), a tou je "n". Toto "n" (a NIKOLI bitová dělka vstupu) je právě tou charakteristikou, která určuje smrštěni-natažení běhu programu a ovlivňuje dobu jeho běhu.
_____________________________________________________________
Příklad 2

Uvažujme algoritmus, který na vstupu dostane dvě čísla v daném formátu (dejme tomu word), a na výstupu odevzdá jejich součet. (algoritmus nedokáže přijímat a sčítat libovolně velká čísla)
Jak určíš časovou náročnost dle tvé definice? Ty říkáš, že je to exponenciální  náročnost (odpověď #33, 2. odstavec), což je samo o sobě dosti překvapivý závěr. Jenomže zapomínáš, že délka vstupu tohoto algoritmu je ve skutečnosti neměnná, takže nelze uvažovat ani žádnou asymptotickou funkci, ani určovat časovou náročnost.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 02. 10. 2010, 01:05:12
@Matyáš Novák, pokrač.
Musím přiznat, že o teorii algoritmů v podstatě nic nevím, a začal jsem pátrat, odkud bereš své tvrzení, že časová náročnost se musí udávat v závislosti na bitové délce vstupu.

Vzal jsem do ruky knihu L. Kučera, kombinatorické algoritmy, kde jsem se na str. 37 dočetl:
"Budeme říkat, že počítač ... pracuje v čase f(n), jestliže f je taková funkce, že každá přípustná vstupní data velikosti n zpracuje v čase nejvýše f(n)"

To odpovídá tvému určování časové náročnosti. Ale pak jsem si přečetl, co autor považuje za "vstupní data velikosti n":
"pro každá přípustná vstupní data určíme číslo, které budeme nazývat velikostí vstupních dat. Jeho volba závisí na druhu objektu, které data popisují. (příklady) ... za velikost matice řádu nxn se obvykle považuje číslo n (i když je třeba zadat n^2 čísel)"

Takže "velikostí vstupu" se nemyslí "bitová délka vstupu". A to je patrně ta chyba, kterou ve svých úvahách děláš.

Závěr: Možná, že s tvou definicí časové náročnosti některé teorie pracují. Nemá ale téměř žádný praktický význam.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: andrej 02. 10. 2010, 02:03:12
Zlozitost moze udavat hocico podla toho, co meriame. Ak robime HW design, zaujima nas napr. priestorova zlozitost (pocet hradiel), ak implementujeme algoritmus, zaujima nas cas a pamat. Napr. mame graf o N vrcholoch a v akom case nieco vieme? (cas f(N), napr N^3) Takze v tomto pripade ziadne bity.

K problemu batoha existuju aproximacne algoritmy, ktore ale nedaju vzdy optimalny vysledok, ale da sa dokazat o co bude (najviac) horsi oproti optimu. Ake su, to to tu uz niekto spominal.

Ak mas malo tych mnozstiev, pusti na to backtracking a je :).
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 02. 10. 2010, 02:48:38
@andrej: Reaguješ trochu z rychlíku.
Mluvíme o časové složitosti. Dohadujeme se o tom, v závislosti na čem časovou složitost měřit, tj. jaké hodnoty jsou možné/smysluplné jako x-ová složka f(N) .
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 02. 10. 2010, 12:29:08
petr: to jo, ale ILP a LP toho spolu IMHO moc společnýho nemaj (což je vidět např. z toho, že složitost LP je pokud se nepletu snad lineární, zatímco ILP exponenciální).

slowthinker, andrej etc..: Mixujete "naivní" definici složitosti, která se používá u jednoduchého porovnávání dvou algoritmů (ano, pro praxi je todle pojetí výhodnější, stejně jako je pro praxi často výhodnější používat newtonovy zákony, i když neplatěj :-))
s exaktní definicí složitosti, která se používá při definici tříd P, NP, NP úplnosti atd...
http://wiki.matfyz.cz/wiki/St%C3%A1tnice_-_NP-%C3%BAplnost
Jenže debata začla tím, zdali je tento problém NP úplný či nikoli. A v tu chvíli je třeba použít tu definici, pomocí které je definována třída NP :-)

Pro KAŽDEJ NP úplnej problém existuje pseudopolynomiální (tzn. polynomiálně závislý, ale ne na délce vstupu) algoiritmus. To však nic nemění na tom, že jsou to NP algoritmy.

Ta vaše definice totiž dobře a jednoduše porovnává algoritmy, které používají vstup stejné povahy. V okamžiku ale, kdy začnete porovnávat všechny algoritmy, tak se s ní dostanete do velkejch problémů, protože jak určíte, co je u danýho algoritmu "jednotka na vstupu" - kdo to určí? Obzvlášť u algoritmů, kde jde ten samý vstup interpretovat více způsoby?

Např. některé grafové algoritmy závisí na počtu hran. Jenže ten samý algoritmus lze chápat jako maticový algoritmus, kde je graf zapsán jako matice - a tam by podle té knížky najednou rozhodoval počet vrcholů. Nebo u libovolného algoritmu můžu vzít zadání jako jedno obrovské číslo (používá se např. v důkazu goodlovy věty v logice). ad...

---
pár konkrétních poznámek.

slowthinker:
C není identické s A,
zaprve ověřuje, že n_(i+1) == (n_i) +1,
zadruhé se musí "prohrabat vstupem", aby dostal N. Dá se tedy zapsat jako A(C'(x)).
a to C' slouži v podstatě jen jako filtr vstupu a to A je přesně to A jako v prvním případě se stejnou složitostí.

Ono bys pro každej NP úplněj problém mohl vymyslet způsob zadání, kdy by jeho složitost byla jen polynomiální - doplnil bys ho exponenciální délkou balastu. Jenže právě díky tomuto balastu by na něj nebyl žádnej jinej NPúplnej problém polynomiálně převoditelnej
(doplnit balast neni v P). Takže by Ti to k ničemu nebylo.

Stejně jako jde problém "zpomalit" nevhodnou volbou algoritmu, tak jde "zrychlit" nevhodnou délkou vstupu. Proto nemá smysl se bavit u daného algoritmu o ničem jiném než o nejlepším možném algoritmu nad nejúspornějším možným vstupem.
A pokud vstup není efektivní, předřadit před samotný algoritmus nějaký filtr, který ho vyčistí (ono C').

---

Ad A a B - ano, algoritmus dělá skoro to samé. Ale on je tam i rozdíl v praxi - u velkejch faktoriálů (např. miliarda) mám vstup furt pár bitů. U součinu miliardy čísel je ten vstup už opravdu hodně velkej. Když předhodim GB soubor ke zpracování, tak čekam, že to může trvat, když předhodim jedno číslo, budu překvapenej :-)

---
sčítání dvou čísel ve formátu word? Tam nemá moc smysl se bavit o složitosti, protože tam je vstup neměnný a algoritmus vždy poběží stejně rychle. Ale pokud bys to chtěl, tak rozhodně složitost není exponenciální a nikde to netvrdím. Naopak, já tvrdím, že je lineární (klasická akumulátorová sčítačka, stačí jednou proběhnout binární zápis čísel), zatímco ty bys tvrdil, že je logaritmický (na dvojnásobně velké číslo mi stačí o jeden krok víc).




Název: Re: Optimální algoritmus výpočtu
Přispěvatel: andrej 02. 10. 2010, 13:41:36
Slowthinker: ano, zabudol som, ze casova je od poctu krokov algoritmu v zavislosti na velkosti vstupu a ta velkost sa vyjadruje ako vseobecne N a nechce sa mi studovat vase skriepky v podstate neviem co riesite :). Pocty bitov zavanaju assembleristami a to s teoretickou informatikou nic nema spolocne..
Kto ma pochybnosti, odporucam pozriet si napr. jednoduchy counting sort na wikipedii, z toho sa da pochopit ten rozdiel (aspon si myslim :) )
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 02. 10. 2010, 14:44:13
Počet bitů si nahraď velikostí slova (přesněji velikost vstupu na pásce) turingova stroje s binární abecedou, ty rejpale. :-) Jen sem to přizpůsobil pro lidi, který to evidentně nestudovali...
A pokus tvrdit, že turingův stroj nepatří do TI... hmmm.... na to se asi odpovědět nedá....

A přečti si tu definici třídy NP
http://wiki.matfyz.cz/wiki/St%C3%A1tnice_-_NP-%C3%BAplnost (http://wiki.matfyz.cz/wiki/St%C3%A1tnice_-_NP-%C3%BAplnost)
než začneš vynášet soudy...
Při studiu NP úplnosti se prostě tadle definice složitosti používá, ať se Ti to zdá divný nebo ne...
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 02. 10. 2010, 19:40:59
sčítání dvou čísel ve formátu word? Tam nemá moc smysl se bavit o složitosti, protože tam je vstup neměnný a algoritmus vždy poběží stejně rychle. Ale pokud bys to chtěl, tak rozhodně složitost není exponenciální a nikde to netvrdím.
Jsem rád že si konečně rozumíme, že to nemá smysl.
Ale tvrdil's to v následující citaci (představ si "počet chtěných kusů" ve formátu word):
Tak ještě jednou a polopaticky. Tys navrhnul algoritmus, kterej je závislej kvadraticky na počtu chtěnejch kusů. A pomocí kolika bitů zakóduješ že chceš n kusů? Já to umim do log(n) bitů.
Takže vstup velikosti v=log_2(n) poběží rychlostí n^2. Proto n=exp_2(v) a tedy výsledná rychlost pro vstup v bitů je exp_2(v)^2. Samozřejmě s nějakym tim očkem, by to bylo precizně :-)
Jinými slovy, přidáním jednoho bitu na vstupu se ti zvýší čas čtyřnásobně. To prostě není polynomiální složitost...


------------------------------------------------------------------------------
Ta vaše definice totiž dobře a jednoduše porovnává algoritmy, které používají vstup stejné povahy. V okamžiku ale, kdy začnete porovnávat všechny algoritmy, tak se s ní dostanete do velkejch problémů, protože jak určíte, co je u danýho algoritmu "jednotka na vstupu" - kdo to určí? Obzvlášť u algoritmů, kde jde ten samý vstup interpretovat více způsoby?
Ta tvoje definice se dostala do problémů už u algoritmů A) a B), které se chovají stejně, ale tvoje definice to nebere v úvahu.
A nedokážeš určit časovou složitost u výpočtu faktoriálu (říkáš: "Tam nemá moc smysl se bavit o složitosti, protože tam je vstup neměnný")

"Co je to jednotka na vstupu" se dá exaktně určovat mnohem lépe, než určovat "co je to balast a co není". Jde o to nalézt takovou charakteristiku vstupních dat, která má přímý vliv na dobu výpočtu (bitová délka vstupu nemusí mít na dobu výpočtu vůbec žádný vliv; přesněji vliv může být marginální, spočívající pouze v delší fázi, kteropu se načítají data )
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 02. 10. 2010, 21:47:31
Citace
Jsem rád že si konečně rozumíme, že to nemá smysl.
Nemá to smysl, ale to proto, že jsi zadal pevnou délku vstupu. U toho mého výpočtu ale nic takového netvrdím. Stejně tak, jako tvůj algoritmus má složitost exponenciální, dle délky vstupu, tak sčítání dvou čísel má složitost lineární - s narůstající délkou vstupu bude lineárně narůstat počet provedených bitových operací.

V okamžiku, kdy ale zadáš pevnou délku vstupu, tak opravdu nemá smysl se bavit o závislosti rychlosti na délce vstupu: ať už u sčítání nebo u problému batohu.

Citace
Ta tvoje definice...
To neni moje definice složitosti. To je definice, pomocí které je definována třída NP. Pokud tedy chceš tvrdit něco o tom, kterej algoritmus do NP patří nebo ne, tak ji prostě musíš používat, jinak Tvoje tvrzení nemá smysl. 
Citace
...se dostala do problémlů
:-) nedostala. Prostě faktoriál má složitost exponenciální, zatímco násobení n čísel má lineární složitost. Nevím, proč by měl mít stejnou složitost algoritmy, když jeden z nich poběží při vstupu deseti bitů stejně dlouho jako druhej při vstupu deseti gigabytů.
Že to tak intuitivně cítíš? To je možný, ale tvoje definice prostě není ani exaktní, ani konzistentní.

Co třeba takhle program, kterej počítá faktoriál součtu deseti čísel na vstupu?

Citace
Jde o to nalézt takovou charakteristiku vstupních dat, která má přímý vliv na dobu výpočtu
Todle lze, pokud se budeš bavit o různých algoritmech na výpočet téhož. Pak samozřejmě
má smysl se bavit o závislosti rychlosti vzhledem k dané charakteristice (ať už ta charakteristika má nebo nemá vztah k velikosti vstupu).
Tady se ale bavíme o příslušnosti do patřičné třídy algoritmů a tedy o porovnávání algoritmů sloužících k různým účelům. A v tu chvíli to nejde, protože
a) každý algoritmus jde těch chrakteristik nalézt více - podle čeho se rozhodne který z nich se použije?  (viz např. tvůj algoritmus - já mám charakteristiku délka vstupu, ty máš charakteristiku chtěný počet) 
b) jeden algoritmus může i řešit více reálných problémů, kdy pokaždé bude "podstatná" jiná část vstupu. Tzn. ten samý algoritmus podle toho bude náležet do jiné třídy?
atd...

Proto když chceš porovnávat algoritmy, tak musíš nalézt kritérium, které je jednoznačné a stejné pro všechny algoritmy. A nic jiného než délku vstupu nemáš. Sám myslím cítíš, že "taková charakteristika, která...." není moc exaktně definovaný pojem. 
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 03. 10. 2010, 04:01:32
Nemá to smysl, ale to proto, že jsi zadal pevnou délku vstupu. U toho mého výpočtu ale nic takového netvrdím. Stejně tak, jako tvůj algoritmus má složitost exponenciální, dle délky vstupu, tak sčítání dvou čísel má složitost lineární - s narůstající délkou vstupu bude lineárně narůstat počet provedených bitových operací.
V okamžiku, kdy ale zadáš pevnou délku vstupu, tak opravdu nemá smysl se bavit o závislosti rychlosti na délce vstupu: ať už u sčítání nebo u problému batohu.
Tak abychom si rozuměli:
Tvrdíš, že
- pro sčítání dvou čísel ve formátu word nemá smysl mluvit o časové složitosti
- u algoritmu pro sčítání libovolně velkých čísel na vstupu je složitost lineární
?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 03. 10. 2010, 11:49:22
a) ano, pokud definuješ složitost tak, jak je běžně definována (pro účely porovnávání různých algoritmů)
http://wiki.matfyz.cz/wiki/St%C3%A1tnice_-_NP-%C3%BAplnost (http://wiki.matfyz.cz/wiki/St%C3%A1tnice_-_NP-%C3%BAplnost)
jelikož word má pevnou délku vstupu.
b) ano, (pokud se fatálně nepletu, pro každej bit navíc musíš udělat konstantní počet bitových operací navíc)

Ještě k tý složitosti: kdybys ji definoval dle "takovoé charakteristiky, která má vliv na dobu výpočtu", tak jak bys moh porovnávat složitost různejch algoritmů?
Co je rychlejší, hruška na pátou, jabko na čtvrtou nebo vůz na šestou (o koze nemluvě)? :-)

Navíc jsou algoritmy na sebe převeditelný.
Dejme tomu převedeme algoritmus A na B:
g(B(f(vstup))) = A(vstup)
(překóduju vstup do formátu vhodnym pro B, spočítam a z výsledku odvodím výsledek A).

Pokud je u obou definovaná složitost tak jak tvrdím, tak ze složitosti a znalosti výstupů B, g, f lze snadno odvodit složitost g * B * f a tedy porovnat ten algorimus s A (tzn. zjistit, jestli se ti hodí problém přeformulovat). Vzhledem k tomu, že f a g nebývají složité funkce, většinou stačí porovnávat přímo složitosti A a B.

  Pokud ale definuješ složitost tak jak ji definuješ Ty, tak Ti ani znalost složitosti B, g, f nic neříká o tom, v jakym je A a B vztahu (u A např. měříš složitost počtem čísel na vstupu, u B velikostí jednoho čísla na vstupu).
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 03. 10. 2010, 19:28:53
a) ano, pokud definuješ složitost tak, jak je běžně definována (pro účely porovnávání různých algoritmů)
http://wiki.matfyz.cz/wiki/St%C3%A1tnice_-_NP-%C3%BAplnost (http://wiki.matfyz.cz/wiki/St%C3%A1tnice_-_NP-%C3%BAplnost)
jelikož word má pevnou délku vstupu.
b) ano, (pokud se fatálně nepletu, pro každej bit navíc musíš udělat konstantní počet bitových operací navíc)
b) OK.
(V praxi se těžko setkáš s počítačem, který vykonává operace nad bity, počítače vykonávají operace nad slovy. Ale to situaci nijak nemění. Ano, pro každé slovo musíš udělat konstantní počet operací navíc.)

a) Začíná ti to nějak skřípat:

Algoritmus co počítá faktoriál má taky pevnou délku vstupu.
Takže teď říkáš, že složitost tohoto algoritmu nelze určit,
zatímco před chvílí jsi tvrdil, že složitost tohoto algoritmu je exponenciální (mimochodem to je z praktického hlediska také pěkný nesmysl).

A dále: Celá tvoje úvaha (označil jsem ji teď ""PolopatickáÚvaha"", viz na této straně výše), kterou jsi vysvětloval, že moje řešení je exponenciální, je založena na tom, jako by počet balení na vstupu byl podle b). Jenomže počet balení v naší úloze má taky pevnou délku vstupu, jedná se tedy o situaci a).
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 03. 10. 2010, 22:14:26
Tak znova. Pokud je u faktoriálu pevná délka vstupu, nemá smysl se bavit o složitosti
(tak jak je definovaná pro NP úplnost), protože ta je definovaná v závislosti na délce vstupu.
Pokud je variabilní, je složitost exponenciální.

Ono je ale např. u faktoriálu zadaném pevnou šířkou v podstatě záleží jen na prvních n bitech, na zadání se tedy dá hledět vždy jako na "variabilní" zadání s tím, že na začátku
se provede předchroustání vstupu (zjištění počtu významných bitů) - které má oproti zbytku algoritmu zanedbatelnou složitost (a pokud ne, pak je zpracování vstupu algoritmem samo o sobě a měla by se řešit jeho složitost zvlášť).

Citace
....že moje řešení je exponenciální, je založena na tom, jako by počet balení na vstupu byl podle b). Jenomže počet balení v naší úloze má taky pevnou délku vstupu...
???
1) Doufám, že se tady bavíme o algoritmech a nikoli o konkrétní implementaci na konkrétním fyzickém hardwaru. (Pokud se chceš bavit o konkrétní implementaci na Core2Duo 4Ghz s 800Mhz DDR2 pamětech....., tak je to o koze a o voze, ale obávám se, že na mé straně je to, jak je chápán pojem složitost algoritmu a celá teoretická informatika navrch :-)).
 
 Pokud už se ve složitosti používá nějaký konkrétní model počítače, tak turingův stroj. A jak známo, TS nepoužívá čísla zadaná pevnou šířkou....

2) zadání variabilní délkou čísla je přirozené zadání, pevná délka vstupu je čistě berlička vhodná pro konkrétní modely dnešních PC, není efektivní (pro sečtení dvou bitů jich musím tak jako tak sečíst 32) a omezená (nelze zadat libovolné číslo).
Co když to budu chtít počítat např. na osmibitu? Nebo to budu chtít řešit pro větší čísla než 2^64? Nebo....?

----

ale hlavně: jde o algoritmus, nikoli jeho konkrétní implementaci. Proto ani nemá moc smysl přemejšlet nad tím, jak je vstup zadaný, vstup je nějaká informace, jejíž velikost se dá změřit. A složitost závisí na velikosti té informace, nikoli na velikosti zápisu této informace v konkrétní implementaci algoritmu na konkrétnim HW. (přesněji - vždy se dá najít zápis, který bude asymptoticky potřebovat tolik paměti, kolik obsahuje daná informace a je rozumné předpokládat, že algoritmus bude tento zápis používat - V teorii NP úplnosti se samozřejmě počítá s konkrétní implementací na TS).


Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Oliver ggg 03. 10. 2010, 22:39:07
Ahoj, cital som kolko sa tu s tym trapite, ja len zopakujem ulohu ci je fakt tak lahka ako sa mi zda. Proste zakaznik da pocet kusov ktory chce, existuju rozdne balenia kde je rozdna cena za kus a ty chces pre neho najvyhodnejsiu cenu. A ono to ma vybrat balenia s najvyhodnejsou cenou...

1. No mna napadlo, algoritmicke zoradenie baleni kvality-vyhody podla ceny za KS.
2. Uz vieme co je najvyhodnejsie, a kolko tam toho je.
3. Vieme pocet kusov ktory zakaznik chce.

4. Zoberieme najvyhodnejsie mozne balenie a pozrieme ci je tam menej kusov ako to co zakaznik chce, ak ano tak mu ho dame to kosika.

4.1 Ak je najvyhodnejsie mozne balenie vacsie ako pocet kusov ktore zakaznik chce, ideme k druhemu najvyhodnejsiemu baleniu na cenu na kus a opat to iste...

Az bude na konci 0... ja v tom problem nevidim .. ci je tam iny problem ktory som prehliadol?

Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 03. 10. 2010, 23:07:51
Jo, je tam problém

chci 9 kusů
je
balení 5 kusů za 50 Kč
balení 3 kusy za 31 Kč

Tvým algoritmem bys vzal 5ks a pak bys neměl co vzít, bys měl 9ks  - problém 1.

Doplníme tedy balení 2 kusů za 10000 Kč. Vezmeš opět balení 5 kusů, pak 3 kusy a nakonec
musíš vzít předražené balení se dvěmi kusy od luise vuitona (nebo jak se ten exot píše :-)).
Problém 2.

Ono i kdybys moh zbytek zahodit a koupit kusů víc, tak to nebude fungovat - furt na začátku bereš balení po pěti kusech, i když bys měl vzít 3x3kusy.




Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ondřej Vaniš 03. 10. 2010, 23:41:57
Ano nyni pouzivam vkladani do kose zpusobem ktery navrhoval Oliver ggg, i kdyz vim ze to ma mouchy viz vyse.

problem 1. -  vzdy je k dispozici baleni ktere obsahuje 1ks
problem 2. - v 99% pripadu neni nejmensi baleni tak extreme predrazene.

asi zustanu u tohoto reseni i kdyz ne vzdy je optimalni.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 04. 10. 2010, 00:44:20
ale hlavně: jde o algoritmus, nikoli jeho konkrétní implementaci. Proto ani nemá moc smysl přemejšlet nad tím, jak je vstup zadaný,
No to teda má. Předpokládá-li stejná úloha
a) pevný formát vstupu
nebo
b) libovolně velká čísla na vstupu
potřebuješ na její řešení dva úplně jiné algoritmy. A je jedno, jestli pracuješ na Core2Duo 4Ghz s 800Mhz DDR2 pamětech, nebo čemkoli jiném.

Citace
zadání variabilní délkou čísla je přirozené zadání, pevná délka vstupu je čistě berlička vhodná pro konkrétní modely dnešních PC, není efektivní (pro sečtení dvou bitů jich musím tak jako tak sečíst 32) a omezená (nelze zadat libovolné číslo).
Na práci s čísly neomezené velikosti není nic přirozeného, je to jenom pořádná komplikace navíc. Místo atomických operací nad čísly, u kterých lze předpokládat stejnou dobu zpracování, dostaneme operace, pro něž doba zpracování závisí na velikosti.
Až budou existovat stroje o nekonečných fyzických rozměrech, pak s tebou budu souhlasit, že pevná délka vstupu je pouze zbytečná berlička.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 04. 10. 2010, 02:04:26
pro každý algoritmus jde těch chrakteristik nalézt více - podle čeho se rozhodne který z nich se použije?  (viz např. tvůj algoritmus - já mám charakteristiku délka vstupu, ty máš charakteristiku chtěný počet)
Pokusím se tedy formalizovat pojem "charakteristika vstupu, která má přímý vliv na dobu výpočtu":

Nechť A je daný algoritmus, I je množina přípustných vstupů A, a funkce t:I->N (N jsou přirozená čísla) je definována dobou běhu algoritmu pro jednotlivé vstupy. Funkce t přirozeně rozkládá I na třídy rozkladu podle doby běhu algoritmu. Jestliže třídy rozkladu vzestupně seřadíme (podle doby běhu algoritmu), získáme posloupnost tříd rozkladu r(1), r(2),...r(n).  Funkci t' definujme tak, že t'(n)=t(i), kde i je jakýhokoli vstup z třídy rozkladu r(n).
Funkce t' je rostoucí a charakterizuje časovou náročnost algoritmu (definice časové náročnosti A). Tyto funkce lze pro různé algoritmy asymptoticky porovnávat.

"Správnou" charakteristikou vstupu budu považovat takovou funkci ch: I->N,  kde ch(i)=x právě když i je prvkem r(x). Jinými slovy správná charakteristika vstupu říká, v "kolikáté" množině rozkladu se vstup nachází.

Když nyní v klasické definici časové náročnosti (definice B) budu vztahovat O(f(n)) ke "správné" charakteristice vstupu (místo k bitové délce vstupu), budou t' a f asymptoticky stejné a obě definice časové náročnosti A a B budou ekvivalentní.

__________________________________
Příklad 1
Říkal jsem, že intuitivně pokládám algoritmy A) a B) za stejně rychlé. Ano, pro funkce t' obou algoritmů platí, že existuje konstanta c, že t'A=c.t'B

(Připomínám, že algoritmus A) je výpočet faktoriálu) Pokud bych chtěl jako charakteristiku A) použít počet bitů vstupu, nefungovalo by to, protože vstupy se stejnou charakteristikou by padaly do různých tříd rozkladu: počet bitů vstupu není v tomto případě jako charakteristika dostatečně přesný.

Příklad 2
Násobení matice nxn konstantou
Správnou charakteristikou je n.
Délka vstupu (n^2) jako charakteristika nefunguje, protože není "na" množinu přirozených čísel (délka vstupu je zbytečně moc přesná)

Příklad 3
Na vstupu je řada celých čísel. Úkolem je najít první kladné číslo n na vstupu a vypsat přesuny disků u Hanojské věže s n disky.
Délka vstupu: nemá v podstatě žádný vliv na dobu výpočtu, jako vhodná charakteristika je absolutně mimo.
Tady je to se správnou charakteristikou horší. Intuitivně bych rád řekl, že je to n, ale není: do doby běhu malinko mluví i umístění n ve vstupním řetězci. (Mohl bych definovat "vhodnou charakteristiku" tak, že při jejím použití v definici B dostaneme stejnou časovou náročnost jako dává definice A (vhodných charakteristik by bylo více, zatímco správná je pouze jedna). n by pak nebyla "správná" charakteristika, pouze "vhodná")
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 04. 10. 2010, 15:21:51
Todle je vcelku hezká definice - ake už v příkladu 3 narážíš na problém. Nabídnu Ti jinou verzi téhož, mnou zmiňovaný faktoriál součtu dvou čísel. Co je tam charakteristikou?

Vidím tam dva zásadní problémy: co takhle takový (vzestupný) bubblesort? Na složitosti n^2, kde n je počet čísel na vstupu se doufám shodnem :-)
Teď dva vstupy
1) vzestupná posloupnost o délce n*(n+1)/2
2) sestupná posloupnost o délce n
Podle té definice (jestli ji rozumím) by oba dva vstupy běžely stejně dlouho, takže by pro ně platila stejná charakteristika. Obávám se, že dle tvé definice by vyhovovala charakteristika vstupu definovaná jako (plus mínus, je to nadhození) délka vstupu plus suma vzdáleností prvků posloupnosti od jejich cílového místa a asymptoitická složitost by byla lineární.

A co např. algoritmus: hledání cesty v grafu prohlédáváním do šířky.... Tady je zas charakteristikou počet hran vedoucích z vrcholů s délkou cesty ze startu kratší než je délka cesty do cíle.
Složitost se využívá i k hornímu odhadu běhu algoritmů - k čemu je mi ale složitost definovaná tak, že k získání odhadu, jak rychle algoritmus poběží musím problém vyřešit?

Když to shrnu, tak dva velké nedostatky jsou:
1) výsledná složitost se neshoduje s běžně definovanými složitostmi jednoduchých algoritmů
2) daná charakteristika může být u problému natolik složitě spočitatelná, že nejde použít jako horní odhad složitosti dané instance problému.

PS: V příkladu 2 zřejmě nemyslíš, že je ta fce na, ale že nemá definiční obor N. Ale to je detail.
PPS: Druhej (dosti podstatnej) detail je definice délky běhu. Ale ta se dá definovat dejmetomu jako počet kroků TS.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 10. 10. 2010, 10:06:22
1. příklad:

B:[[50,17],[10,19],[5,18],[1,20]];

funkce:

f(_n,_B):=block([A,B,L,i,j,k,c:0,m:0,n:_n],B:reverse(sort(_B)),A:copylist(B),L:length(B),
for i:1 thru L do (
if ( n > B[1] ) then (
A[1]:floor(n/B[1]),
m:m+A[1]*B[1],
n:n-A[1]*B[1],
A[2]:A[1]*B[1]*B[2],
c:c+A[2]
) else (
A[1]:0,A[2]:0
),
print("Pocet:",A[1],"x",B[1]," po ",B[2],"Kč =",A[2])
),
print("Celkem kusů:",m," za celkem ",c, "Kč")

);

Výpočet:
f(78,B);

Pocet: 1 x 50  po  17 Kč = 850
Pocet: 2 x 10  po  19 Kč = 380
Pocet: 1 x 5  po  18 Kč = 90
Pocet: 3 x 1  po  20 Kč = 60
Celkem kusů: 78  za celkem  1380 Kč

Druhý příklad:

B:[[1,12],[5,8],[2,8.5]];

Opět funguje.

(Programovací jazyk Maxima, funkce jdou volat i ze skriptů)

Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 10. 10. 2010, 11:05:18
Nefunguje - viz protipříklady v mojim postu #56 (uvádím tam vždy cenu balení, když si to budeš chtít zkusit).
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 10. 10. 2010, 11:56:01
B:[[5,50],[3,31]];
f(9,B);

Pocet: 1 x 5  po  50 Kč = 250
Pocet: 1 x 3  po  31 Kč = 93
Celkem kusů: 8  za celkem  343 Kč

Tak tady to nejde (z důvodu že nejmenší položka má 3 kusy).
Myslím, že bych to zvládnul upravit tak, aby to vyšlo i s méně příznivými kombinacemi.
Pak to sem šoupnu.

Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 10. 10. 2010, 12:25:41
:-) Nejde to proto, že je ten algoritmus blbě :-).
Vždyť
a) legální kombinace existuje
b) když doplníš 1 kus za 10.000, - , tak Ti to vybere 5+3+1, což bude poněkud předražená kombinace.
Smiřte se s tím, že problém baťohu je NP úplnej a jde vyřešit pseudopolynomiálně
dynamickým programováním, nic lepšího vymyslet nejde...

PS: Základní problém je v tom, že v ideální kombinai nemusí bejt zastoupený balení s nejlepším poměrem ceny, a naopak tam může bejt zastoupenej výrobek s nejhorším poměrem cena/výkon.... - takže jakékoli heuristiky selhávají a je třeba prohledat celý stavový prostor.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 10. 10. 2010, 12:59:54
Jo s tím jedním kusem za 10000 tisíc to mě nenapadlo. Myslel jsem spíš že vysloveně nevýhodné balíčky by se rovnou vyloučily. Jenže to by musel udělat ten program.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 10. 10. 2010, 13:19:04
Jenže jak zjistíš, který jsou vysloveně nevýhodný? Ten balíček nemusí stát 10000, stačí by byl za 13Kč a je to horší. Naopak za 11Kč je to nejlepší kombinace... To zjistit nejde, aniž bys to spočítal...
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 10. 10. 2010, 17:04:12
fr(_n,_c,_A,_k):=block([n:_n, c:_c, A:copylist(_A), i, j, x, ni, ci, imin, k:_k],
if k > 0 then (j:floor(n/A[k][1]),if j>0 then (
for i:0 thru j do (ni:n-i*A[k][1],ci:c+i*A[k][2],A[k][3]:i,fr(ni,ci,A,k-1))
) else (fr(n,c,A,k-1))) else (if (n=0) then (if z=0 then (AB:copylist(A),z:c)
  elseif (z>c) then (z:c,AB:copylist(A)))),[z,AB])$

f(_n,_B):=block([n:_n,A,AB,AA,c:0,L,z:0,s],AA:(sort(_B)),L:length(AA),A:[],
for i:1 thru L do (A:append(A,[flatten([AA,0])])),AB:copylist(A),s:fr(n,c,A,L),print(s))$

B:[[5,50],[3,31]];
f(11,B)$
[112,[[3,31,2],[5,50,1]]]

Celková cena 112Kč (1x po 5 ks á 50Kč, 2x po 3 ks á 31 Kč)

B:[[1,100],[2,8],[5,5]];
f(23,B);
[47,[[1,100,0],[2,8,4],[5,5,3]]]

Celková cena 47Kč
(žádný balíček:  1ks á 100Kč)
(4 balíčky po 2 ks á 8Kč)
(3 balíčky po 5 ks á 5Kč)

prochází možnosti od největších, ty které překročí limit zahazuje a nepočítá dál. Limit se snižuje.
Výpočet pro větší hodnoty je pomalý.



Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 10. 10. 2010, 17:23:09
Promiň, na todle se nedá reagovat. Chaotickej kód bez jedinýho komentáře s jednompísmenejma proměnejma u kterejch není jasný co vlastně znamenaj, navíc bez jakýhokoli rozumnýho formátování.

Nerozumím, co si tím chtěl říct, ale je to jasnej příklad, jak se programovat NEMÁ.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 10. 10. 2010, 19:08:41
Tak jsem to zjednodušil, sice to trvá déle, ale je to přehlednější:

Kód: [Vybrat]
funkce_rekurzivni(Pocet_polozek,Celkem_Kc,Pole_D,Polozka):=block(
[   i,
    Pocet,
    Pole_A: copylist(Pole_D)],

if Polozka > 0 then (
    Pocet: floor(Pocet_polozek/Pole_B[Polozka][1]),
    if Pocet > 0 then (
        for i:0 thru Pocet do (           
            Pole_A[Polozka]: i,
            funkce_rekurzivni(Pocet_polozek-i*Pole_B[Polozka][1],Celkem_Kc+i*Pole_B[Polozka][2],Pole_A,Polozka-1)
        )
    )
    else (
        funkce_rekurzivni(Pocet_polozek,Celkem_Kc,Pole_A,Polozka-1)
    )
)
else (
    if (Pocet_polozek=0) then (
        if ((Suma=0) or (Suma > Celkem_Kc)) then (
            Suma: Celkem_Kc,
            Pole_C: copylist(Pole_A)
        )
    )
),[Suma,Pole_C])$

optimum(Pocet_polozek,Pole_Balicku):=block(
[   Pole_A,
    Pole_B,
    Pole_C,
    Celkem_Kc: 0,
    Polozka,
    Suma: 0,
    Vysledek],

Pole_B: sort(Pole_Balicku),
Polozka: length(Pole_B),
Pole_A: makelist(0,Polozka),
Pole_C: copylist(Pole_A),

Vysledek: funkce_rekurzivni(Pocet_polozek,Celkem_Kc,Pole_A,Polozka),
[Vysledek,Pole_B]
)$

Zadám pole obsahující jednotlivé balíčky (1ks á 9Kč, 2 ks á 8Kč ...atd.):
Zavolám funkci obsahující právě toto pole a požadovaný počet položek:

Kód: [Vybrat]
B:[[1,9],[2,8],[5,5]]$
optimum(23,B);

Funkce vrátí vypočítanou celkovou cenu a seznam počtů jednotlivých balíčků.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 10. 10. 2010, 19:46:41
A čím se to liší od předchozího algoritmu?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 10. 10. 2010, 20:30:47
Projde to všechny možnosti.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 10. 10. 2010, 20:53:14
Jo, už jsem to pochopil. Fuj. Víc se k tomu říct nedá. Pročti si diskusi a najdeš tam několikrát zmiňovaný daleko rychlejší řešení. Heslo "dynamický programování".
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ghost 10. 10. 2010, 21:19:33
Dynamicke programovani je reseni, ale rekl bych, ze narocnejsi na pochopeni.

Mozny nastrel reseni, ktery by mel byt po malych upravach funkcni a optimalni.
Kosik si predstav treba jako list, nebo multiset.
Jednotlive velikosti baleni si ocisluj od jednicky treba.
Je to oklestena metoda B&B - orezevam jen stavy, ktere nikam nevedou.
Kód: [Vybrat]
1. vytvor trivialni konfiguraci - tj. v Tvem pripade prazdny kosik
2. oznac toto trivialni reseni jako dosud nejlepsi
3. vloz jej na zasobnik
4. pokracuj dokud neni zasobnik prazdny a delej nasledujici kroky:
1. generuj nove konfigurace
Tady je dulezite se neopakovat -> tj. nevytvaret si uz jednou vytvorene kosiky.
Ukladat si je do nejake mapy pod hashem a kontrolovat jestli uz jsi je nemel je blbost - pametova narocnost.
Reseni, ktere ti bude generovat unikatni neusporadane konfigurace by mohlo byt takoveto:
(Pozn. na zasobniku se bude generovat silne nevyvazeny strom nakloneny na jednu stranu - zalezi jak zacnes, ze je nevyvazeny nicemu nevadi :))
Dulezite je to ocislovani baleni! Ze stavu, ktery je na vrcholu zasobniku vygeneruj nove stavy tak, ze pridej
nove baleni - ale pridej vzdy jen ty, ktere maji CisloBaleni >= nez posledne vlozene baleni!
2. over u nove konfigurace jestli se jedna stale o platne reseni
3. pokud je neplatne tak stav vyjmy ze zasobniku a pokracuj
4. jestli je reseni tak over jestli se nejedna o lepsi reseni, nez je posledne nalezene. Jestli jo, tak jej oznac jako nejlepsi.
5. pokracuj
5. pokud je po vsech techto krocich nejlepsi reseni porad to trivialni tak reseni neexisuje


Ted jen kratka "vizualizace".
Mam tri baleni, ktere si ocisluju 1,2,3 - je jedno jakou maji cenu, jen popis jak se generuje.
Jednotlive kroky:
1. empty - tj. prazdny kosik
2. bytvorim stavy a na zasobniku mam ted {1}, {2}, {3} - predpokladejme, ze jsou vsechna resenim (poradi nezalezi, muze byt i naopak)
3. na vrcholu mam ted teda {1}, takze si jej vytahnu a stejnym postupem generuju dalsi stavy a dostanu {1,1}, {2,1}, {3,1}
4. stav {2} se expanduje uz jen na {2,2} a {3,2}
5. stav {3} se expanduje uz jen do {3,3}, tady jde videt to nakloneni doleva
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ghost 10. 10. 2010, 21:22:36
sakra, omluvte ty pravopisne chyby ..
zapomnel jsem dopsat:
2. over u nove konfigurace jestli se jedna stale o platne resenim jestli jo, tak zase vloz na zasobnik
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 10. 10. 2010, 22:09:37
Já nevim, imho to neni o nic jednodušší než dynamické programování. Prostě se mi to zdá jako snaha vymejšlet kolo....
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ghost 10. 10. 2010, 22:15:55
Jiste, jenze pokud si nevi rady se zaklady, tak je pro nej lehci na pochopeni urcite B&B. Reseni, ktere jsem tady napsal, se da napsat odhadem do max 50 radku v cemkoliv.

Jsou to jen dva vnorene cykly + pouziti zasobniku (pripadne rekurzivni volani).

Abych priznal barvu, metodu DP jsem uz dlouho nepouzil, takze bych ji z hlavy ted nejspis taky nedal. Naposledy kdysi davno prave pro batoh :)


Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 10. 10. 2010, 23:26:32
Právě že to dynamický programování je i zdaleka nejjednodušší algoritmus na napsání. Odhadem na 10 řádek v čemkoli (no dobře, assembler možná dvacet). nehledejte problém tam, kde neni.

Kód: [Vybrat]
Inicializuj mincena[1..n] na nekonečno.
pro i z 1 ... n
 pokud existuje balení o i prvcích: mincena[i] = cena i-prvkového balení
 pro j z 1 ... i/2
    pokud mincena[j]+mincena[i-j] < mincena[i]: mincena[i] = mincena[j] + mincena[i-j]

That's all folks. Tádydádydádydááá.... :-)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ghost 11. 10. 2010, 00:06:26
Ok, rikam, dlouho jsem nepouzil.
Lehci na pochopeni pro neznale mi porad prijde B&B - pravda, jen se musi vymyslet dobre generovani konfiguraci, aby se neduplikovaly ...

Jen doplnim k DP co si jeste pamatuju:
1. chybi zminka o trivialnim reseni, bez ktereho se nehnes (vim, jedno prirazeni :))
2. chybi rekonstrukce toho, co mas dat do kosiku, ted mas jen nejlepsi cenu
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 11. 10. 2010, 14:04:51
Nebuď dogmatik. To přiřazení tam je - akorát v jiný formě.
Je jím první řádek cyklu. Schválně jsem čekal, jestli se někdo chytne :-)
Klasický dynamický programování jede "po prvcích" - ale já jedu po "počtech".
Po prvcích by šlo taky - pak bych musel s každým prvekm vytvořit
všechny možné kombinace s dosud existujícími kombinacemi a nebylo by to tak elegantní.


A rekonstrukci košíku jsem sem nedal úmyslně - důležitý je pochopit myšlenku a ta se snadnějc pochopí z tohodle, a kdo to pochopí, ten si to snadno dopíše....

---

Jinak ono dynamický programování je v podstatě totéž, co B&B, akorát prohledává stavovej prostor v jinym pořadí.
Mů invariant je: než sestrojím stav s počtem prvků X, sestrojím všechny stavy s počtem prvků menším než X.
Tvuj invariant je: než v dané konfigurac košíku na Y tém místě v košíku vyzkouším prvek X, vyzkouším na tom místě všechny prvky menší než X a větší rovny než prvek na místě Y-1.

Že by ten Tvůj invariant byl jednodušší se mi moc nezdá.

Důkaz "dynamického" algoritmu je jednoduchá indukce dle ceny:
- Je-li košík N minimálním (má nejmenší možnou cenu) pro počet prvků n, pak jakékoli dva košíky A a B, pro které platí A+B=N (sesypání košíků) jsou minimální.
Sporem: není-li tomu tak, pak BÚNO existuje stav minimální košík A' a tedy i cena N' = A' + B je menší než N, což je spor.
- Pro nula prvků je nejlevnější prázdný košík.
- Vyřešil-li jsem stavy 0..n-1, pak každý minimální košík pro n je kombinací dvou minimálních košíků pro 1..n, nebo se sestává z jednoho balení. (triviální důsledek předchozího lematu)

V případě B&B to imho takhle elegantně nepůjde.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 13. 10. 2010, 07:33:14
- Pro nula prvků je nejlevnější prázdný košík.
Tohle tvrzení k důkazu nijak nepřispívá, ze dvou prázdných košíků stejně nic nesestavíš. S tou indukcí bych na tvé místě začal od jedničky...  :P

Smiřte se s tím, že problém baťohu je NP úplnej a jde vyřešit pseudopolynomiálně
Předpokládám, že tím chceš říct, že totéž platí i o úloze probírané v tomto vlákně: no s tím se teda nesmíříme  >:(
Můj algoritmus je podle "tvé" definice časové náročnosti lineární:
Na vstupu je požadovaný počet kusů zboží n (fixní délka vstupu) a atomická balení (neomezená délka vstupu). Takže ta část algoritmu, která k sobě skládá dvojice nákupů, je časově omezená maximálním n, a doba běhu závisí lineárně na délce vstupu (kvůli zjišťování, jestli lze nákup sestavit z jediného atomického balení - tj. nákup typu 1] v popisu algoritmu (http://forum.root.cz/index.php?topic=805.msg5896#msg5896))
(Edit: A podle "mé" definice (která zatím neexistuje) je algoritmus kvadratický.)

Todle je vcelku hezká definice - ake už v příkladu 3 narážíš na problém
Ještě se k tomu zkusím vrátit, nemám na to teď čas.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: ghost 13. 10. 2010, 09:46:15
uff, tak tvuj algoritmus jsem teda nijak nekoumal, ale tvrdit, ze to jde linearne je odvaha ...
jedna se o problem batohu a ten je zkratka NP-uplny, takze nejlepsi (optimalni) reseni nemas sanci najit v polynomialnim case - leda v pseudo a to za pomoci DP.

Ber to jako hotovou vec, ptz optimalni reseni muze byt v kteremkoliv stavu. V pripade 0/1 batohu mas takovych reseni 2^<celkovy_pocet_veci> - jak vidis, tak zavislost je exponencialni, stejne tak v tomto pripade, navic nemas omezenu kapacitu kosiku - jen potrebujes co nejlevneji koupit urcity pocet kusu
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 13. 10. 2010, 10:15:35
Nevím v čem je dynamické programování lepší proti mému programu, který projde podle stromové struktury pouze jednou jedinkrát existující možnosti, které vyhovují zadání. To znamená, že vůbec negeneruje možnosti, které nesplňují zadaní a také znovu nevytváří kombinace, které byly už jednou vytvořeny. A také navíc začíná od cenově výhodnějších kombinací, takže vždy přijde na nejvýhodnější kombinaci v několika prvních cyklech. Pak zbývající čas už jenom ověřuje, zda neexistuje nějaká lepší.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: ghost 13. 10. 2010, 10:55:23
Nevím v čem je dynamické programování lepší proti mému programu, který projde podle stromové struktury pouze jednou jedinkrát existující možnosti, které vyhovují zadání. To znamená, že vůbec negeneruje možnosti, které nesplňují zadaní a také znovu nevytváří kombinace, které byly už jednou vytvořeny. A také navíc začíná od cenově výhodnějších kombinací, takže vždy přijde na nejvýhodnější kombinaci v několika prvních cyklech. Pak zbývající čas už jenom ověřuje, zda neexistuje nějaká lepší.
DP muze byt pro nektera zadani o dost rychlejsi, nez B&B. Co se tyka stromove struktury jak popisuje. Tak asi podobne reseni jsem poslal i ja. Akorat zacinam od trivialniho - tj. prazdneho kosiku a pridavam veci. Zadny stav se mi nenavstivi 2x a stav, ktery neni resenim se uz dal neexpanduje.

Co se tyka vety: najdu nejvyhodnejsi reseni v nekolika cyklech ... to bych se ja osobne neopovazoval tvrdit. Ptz vse zavisi na tom jak generujes stavy prostor a take na konfiguraci baleni. Takze se ti klidne muze stat, ze to optimalni bude az uplne to posledni :)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 13. 10. 2010, 11:07:58
Vzhledem k tomu, že začínám kombinace tak, abych měl nejvíce balíčků nejlevnějších a jak postupně levné balíčky snižuji a tím přidávám dražší balíčky, ale stále tak, aby celkový počet položek byl stále rovný zadání (to znamená, že se mi tam neobjeví kombinace, která mi dá celkový počet položek jiný, než zadaný).
Tímto způsobem se mi nemůže stát, aby se nejvýhodnější sestava objevila na konci hledání, neboť by musela být kombinací těch nejdražších balíčků.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: ghost 13. 10. 2010, 11:27:51
Vzhledem k tomu, že začínám kombinace tak, abych měl nejvíce balíčků nejlevnějších a jak postupně levné balíčky snižuji a tím přidávám dražší balíčky, ale stále tak, aby celkový počet položek byl stále rovný zadání (to znamená, že se mi tam neobjeví kombinace, která mi dá celkový počet položek jiný, než zadaný).
Tímto způsobem se mi nemůže stát, aby se nejvýhodnější sestava objevila na konci hledání, neboť by musela být kombinací těch nejdražších balíčků.
hm, zajimave, ale takto popsane reseni mi silne pripomina hladovy algoritmus - ktery u batohu nemusi byt optimalni ... sic nevim co si mam (resp. nevim jak provadis) predstavit pod dohledani lepsich
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 13. 10. 2010, 11:41:29
Tady je řešení jak lineárního programu, které samozřejmě nenajde nejlepší řešení, pokud je v zadání podraz.

Tak i rekurzivního, které má vlastnosti jenž jsem popisoval.
(http://img718.imageshack.us/img718/1224/optimumbaleni.png)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 13. 10. 2010, 11:49:53
uff, tak tvuj algoritmus jsem teda nijak nekoumal, ale tvrdit, ze to jde linearne je odvaha ...
Lineární není podle mne, ale podle definice časové náročnosti, kterou používá Matyáš Novák.
Podle mne je to řešení kvadratické, alespoň podle "intuitivní" definice časové náročnosti (jedná se o dva vnořené cykly od 1 do n, kde n je určeno vstupními hodnotami).

(viz tato debata pár stránek zpět)

Nevím v čem je dynamické programování lepší proti mému programu, který projde podle stromové struktury pouze jednou jedinkrát existující možnosti, které vyhovují zadání.
Jakmile procházíš strom, je časová náročnost exponenciální. Kvadratické řešení je lepší.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 13. 10. 2010, 12:54:09
Jakmile procházíš strom, je časová náročnost exponenciální. Kvadratické řešení je lepší.

Aha, ale to nevím jak bych naprogramoval.
Tohle je pro mne jednodušší, už z toho důvodu, že je obecné a funguje pro libovolný počet balíčků. Je fakt, že pro velký počet kusů, vzniká obrovské množství kombinací, které je časově náročné. V tomto příkladu (3 balíčky a 24 kusů) je to stále ještě rychlé.

Například pro 5 balíčků:
B:[[1,20],[5,18],[10,19],[50,17]]

a 1024 kusů přišel na řešení okamžitě, ale vlastní kontrola ještě trvala 8 sekund.

a při 2048 kusech sice také měl správné řešení ihned, počítal však ještě 101 sekund.

a při 4096 kusech našel správné řešení ihned, počítal však ještě 1360 sekund.

Podle mně by vůbec nemusel procházet všechny řešení. Stejně na to přijde okamžitě. Možná by stačilo ho po nějaké krátké době useknout a považovat nalezené řešení za správné.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 13. 10. 2010, 12:56:31
slowthinker:Fixní élka vstupu u složitosti je nesmysl. Už třeba proto, že se bavíme o asymptotické složitosti, tedy o složitosti kdy délka vstupu se limitně blíží k nekonečnu. Takže buďto můžeš prohlásit n za konstantu, nebo mu povolit růst do nekonečna (to ale nejde s fixní délkou vstupu).
Ono pokud měříš složitost dle délky vstupu pro n zadané fixní délkou, tak samozřejmě nejdéle to vždy poběží, když n je maximální. A vstup je furt stejně dlouhý, takže vlastně měříš složitost algoritmu: "jaký je nejlevnější košík pro C", kde C je konstanta (2^délku n). Ale to je už trochu jinej algoritmus.
(např. proto, že neumí řešit všechny případy).

Seřazení dvaceti čísel variabilní délky má taky lineární složitost. (s délkou čísel roste jen lineárně) - a přesto má řazení složitost větší: n*log(n).



Citace
Tohle tvrzení k důkazu nijak nepřispívá, ze dvou prázdných košíků stejně nic nesestavíš. S tou indukcí bych na tvé místě začal od jedničky... 
Při indukci je vyžadováno, aby pro krok n byl vyřešen krok n-1. Takže mám dvě možnosti, buď vyřeším úplně triviální případ pro nulu (byť z nulového košíku nikdy další skládat nebudu), nebo pro jedničku, kdy je to složitější. Jsem línej člověk a tak radši vyřeším tu nulu. :-P.
PS: Jedička se pak vyřeší jako běžnej krok, holt se tam prostě půlka neuplatní, protože neexistuje žádná vhodná kombinace A a B, ale co mi po tom?

jaromír:
V čem je lepší?
Ty jen projdeš stromovou strukturu.... :-) Že je velikost té stromové struktury exponenciální (2^n vrcholů stromu)ty už jaksi nevadí.... Vždyť sám píšeš, že pro větší počty to bude pomalý.
Jestli chceš přesně vědět, v čem je dynamický programování lepší, tak třeba v tom, že pokud máš balení s jedním a dvěma kusama, obě za korunu kus, tak zatímco dynamické programování rozvine jen jedno řešení a u druhého zjistí, že není lepší a zahodí ho už hned jak vezme do ruky to dvoukusový balení, tak ty rozvíjíš obě možnosti a zjistíš, že jsou ekvivalentní teprve poté, co prohledáš celý podstrom.
Exaktnějc řečeno, tvoje řešení není pseudopolynomiální, zatímco dynamické programování ano.

Citace
Tímto způsobem se mi nemůže stát, aby se nejvýhodnější sestava objevila na konci hledání, neboť by musela být kombinací těch nejdražších balíčků.
Ach jo. Opravdu?
Chceš 1600 kusů
400 kusů celkem za 4000
1 kus za 10000000
+ hromada 300 - 399 kusových balení za cenu pod 3000.
Výsledná kombinace bude obsahovat 4x4 kusy, ale na tu přijdeš skoro až jako poslední.

Další věc je, že i když přijdeš na nejlepší kombinaci rychle, tak pokud jsou ceny hodně podobné, tak stejně zbytek stromu musíš projít hodně do hloubky, než přijdeš na to, že
ostatní kombinace jsou horší.




Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 13. 10. 2010, 13:05:20
jaromir: Složitost se vždy řeší dle nejhoršího možného vstupu dané délky. Navíc program, který nenajde správné řešení vždy je na nic - jak můžeš vědět, že nalezené řešení je správné?
Stejnětak čas kdy se najde optimální řešení je nic neříkající údaj: jediný, co je směrodatný je čas, kdy algoritmus doběhne. Protože než doběhne, tak nevíš, jestli to optimum je opravdu optimum.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 13. 10. 2010, 16:01:00
Aha, ale to nevím jak bych naprogramoval.
Tohle je pro mne jednodušší, už z toho důvodu, že je obecné a funguje pro libovolný počet balíčků.
Vždyť se tady o tom algoritmu (http://forum.root.cz/index.php?topic=805.msg5896#msg5896) pořád mluví, např. důkaz Matyáše Nováka v #78 je právě o něm.
Ten algoritmus funguje pro libovolný počet balíčků.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 13. 10. 2010, 16:07:19
Fixní délka vstupu u složitosti je nesmysl. Už třeba proto, že se bavíme o asymptotické složitosti, tedy o složitosti kdy délka vstupu se limitně blíží k nekonečnu.
Chceš tím říct, že "tvoje" definice je v praxi nepoužitelná, zvlášť pokud je délka vstupu konstantní? Pak souhlasím. Protože v praxi algoritmy pracují s daty ve fixním formátu.

Citace
Ono pokud měříš složitost dle délky vstupu pro n zadané fixní délkou, tak samozřejmě nejdéle to vždy poběží, když n je maximální. A vstup je furt stejně dlouhý, takže vlastně měříš složitost algoritmu: "jaký je nejlevnější košík pro C", kde C je konstanta (2^délku n). Ale to je už trochu jinej algoritmus.
(např. proto, že neumí řešit všechny případy).
Pokud bude n zadané fixní délkou (např. formát word), není vstup stejně dlouhý, protože ve vstupu budou i atomická balení a jejich počet není omezený. A opakuji: podle "tvé" definice je tento algoritmus lineární (viz #86).
Algoritmus, který by uměl pracovat s libovolně velkým n, je jiný algoritmus (složitější a pomalejší - alespoň dokud nebudou existovat stroje, které umějí zpracovávat libovolně velká data) . Ale nikdo ho nepotřebuje, tak ho tady snad nemusíme teoreticky rozebírat.

Citace
Při indukci je vyžadováno, aby pro krok n byl vyřešen krok n-1.
Tohle je ale jiná indukce:
Pro krok n je vyžadováno, aby byly vyřešeny všechny kroky od 1 do n-1. Zdůrazňuji termíny "všechny" a "1". Krok pro nulu nemá žádný význam.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 13. 10. 2010, 17:40:50
Citace
Chceš tím říct, že "tvoje" definice je v praxi nepoužitelná, zvlášť pokud je délka vstupu konstantní? Pak souhlasím. Protože v praxi algoritmy pracují s daty ve fixním formátu.
Chci tim říct, že bavit se o ASYMPTOTICKÉ složitosti, tedy vyšetřovat jaké je chování algoritmu při přibližování nějaké veličiny (ať již jde o délku vstupu nebo o cokoli jiného) limitně k NEKONEČNU, je u fixního vstupu blbost, protože fixní vstup se nikdy k nekonečnu blížit nebude, anžto má horní hranici.

Jako bys tvrdil, že třídění má složitost lineární a dokazoval to tím, že když uděláš algoritmus, kterej bude mít na vstupu pevných sto chlívků pro čísla, z nichž některé budou prázdné, ale ty chlívky budou mít libovolnou velikost, tak algoritmus, co ten vstup seřadí bude mít lineární složitost.

Citace
Algoritmus, který by uměl pracovat s libovolně velkým n, je jiný algoritmus (složitější a pomalejší - alespoň dokud nebudou existovat stroje, které umějí zpracovávat libovolně velká data).
1) Nový kolečko? NP třídy jsou definovaný pomocí turingova stroje. Ne na reálnym HW.
2) Zpracovámí dlouhých čísel je i na současném HW vcelku jednoduchá úloha s lineární složitostí (potřebuji jen sčítání a porovnávání). Takže nevím, proč by mělo jít o "pomalejší" algoritmus. Jelikož je sublineární algoritmus je nesmysl (BÚNO vždycky alespoň vstup přečtu), tak předělání algoritmu z fixed width na variable length neudělá s asymptotickou složitostí vůbec nic.
3) Asymptotická složitost z definice prostě nemůže používat pevný zápis vstupu, protože ten je omezen (viz předchozí odstavec).
4) Ty se fakt chceš bavit o složitosti na reálném hardware? A budeš do toho počítat velikosti různejch cache a pamětí? Takže na spoustě míst najednou nastane skok, jak nebude stačit na ta a ta data L1/L2/L3 cache či paměť - jak to do výpočtu zahrneš?
A můžu na tom stroji akcelerovat pomocí GPGPU? A jak do výpočtu zahrneš TLB, asociativitu cache, branch prediction....? A jak chceš řešit asymptotickou složitost, když od určitý velikosti se Ti to nevejde ani na harddisk? A....

Promiň, ale to je prostě blbina, složitost se vždy počítá na nějakém abstraktním stroji a pokud je důležité kódování vstupu, tak na TS.

Citace
Tohle je ale jiná indukce:
Pro krok n je vyžadováno, aby byly vyřešeny všechny kroky od 1 do n-1. Zdůrazňuji termíny "všechny" a "1". Krok pro nulu nemá žádný význam.
?????? Ano, a kdo to stanovil, že se musí začít od jedničky? Báťuška Stalin a tak je to pravda? Nebo to učili v mateřský škole? A oni jsou nějaký dvě matematický indukce? Omlouvám se za sarkasmus, ale fakt by to chtělo, aby sis o věcech, o kterejch píšeš něco zjistil, nebo to alespoň netvrdil tak jistojistě.

Jak např. dokážeš, že kůň na šachovnici n*n doskáče všude, když to platí jen na šachovnici 4x4 a větší? To jako tady indukci použít nesmím, protože se MUSÍ začít od jedničky?

Pro matematickou indukci je nutné dokázat že:
1) P(n_0), n_0 náleží do Z
2)  Pro každé n ze Z: n >= n_0 platí P(n) => P(n+1)
A tím dokážeš, že tvrzení P platí pro každé n větší rovné n_0
http://math.feld.cvut.cz/habala/teaching/dma/dmknih03.pdf

světe div, se, pokud to chci dokázat pro všechna celá čísla, tak dokonce budu dokazovat i
P(n+1) => P(n). Jaká svatokrádež! :-) :-) :-)

PS: (pro složitější důkazy se druhá implikace nahrazuje)
2)  Pro každé n ze Z: n > n_0 platí: P(n_0) & P(n_0 + 1) & ...  & P(n - 1) => P(n)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 13. 10. 2010, 23:53:23
Ach jo. Opravdu?
Chceš 1600 kusů
400 kusů celkem za 4000
1 kus za 10000000
+ hromada 300 - 399 kusových balení za cenu pod 3000.
Výsledná kombinace bude obsahovat 4x4 kusy, ale na tu přijdeš skoro až jako poslední.

Ale já jsem říkal, že můj algoritmus prochází nejvýhodnější řešení jako první (zkouší nejdříve nejlevnější balíčky), takže na správné přijde okamžitě. Zrovna před chvílí jsem to ověřil.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 14. 10. 2010, 07:35:12
Ano, a kdo to stanovil, že se musí začít od jedničky? Báťuška Stalin a tak je to pravda? Nebo to učili v mateřský škole? A oni jsou nějaký dvě matematický indukce?
Stanovil to ten algoritmus:
Máš-li určit řešení Ř(n), budeš k tomu potřebovat spojit Ř(1) a Ř(n-1), Ř(2) a Ř(n-2), Ř(3) a Ř(n-3) atd. Musíš tedy znát právě Ř(1) až Ř(n-1).
Ř(0) potřebovat nebudeš.



S definicí časové složitosti jsem odskočil do nového vlákna Definice časové složitosti (http://forum.root.cz/index.php?topic=1039.0).
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ghost 14. 10. 2010, 10:29:21
Ale já jsem říkal, že můj algoritmus prochází nejvýhodnější řešení jako první (zkouší nejdříve nejlevnější balíčky), takže na správné přijde okamžitě. Zrovna před chvílí jsem to ověřil.
Otazka zni: Jak poznas, ze prochazis nejvyhodnejsi reseni hned na zacatku?
To, ze zkousis jako prvni nejlevnejsi balicky je hladovy postup, ktery nemusi byt vzdy optimalmi!!
Kdyz budes mit dva druhy balicku - 1ks/1kc a 5ks/3kc. Budes chtit koupit 6ks. Jaky dostanes vysledek?

Nastuduj si neco o metodach prochazeni stavoveho prostoru a vubec o kombinatoricke optimalizaci.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 14. 10. 2010, 12:01:01
Ale já jsem říkal, že můj algoritmus prochází nejvýhodnější řešení jako první (zkouší nejdříve nejlevnější balíčky)....
Já jsem to říkal, takže je to pravda?
Dal jsem Ti jasný protipříklad, kde je řešení složeno z nejdražších balíčků.

Citace: jaromír
Zrovna před chvílí jsem to ověřil.
A víš vůbec, že jsou všechny čísla dělitelný pěti? Právě jsem to ověřil: 15 je dělitelný pěti a 35 taky....

Citace: slowthinker
Máš-li určit řešení Ř(n), budeš k tomu potřebovat spojit Ř(1) a Ř(n-1), Ř(2) a Ř(n-2), Ř(3) a Ř(n-3) atd. Musíš tedy znát právě Ř(1) až Ř(n-1).
Ř(0) potřebovat nebudeš.
A to mi má vadit? Tak prostě dokážu něco navíc.

A mimo to, co když opravdu chci nejlevnější sadu nula výrobků?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 14. 10. 2010, 12:32:12
Otazka zni: Jak poznas, ze prochazis nejvyhodnejsi reseni hned na zacatku?
To, ze zkousis jako prvni nejlevnejsi balicky je hladovy postup, ktery nemusi byt vzdy optimalmi!!
Kdyz budes mit dva druhy balicku - 1ks/1kc a 5ks/3kc. Budes chtit koupit 6ks. Jaky dostanes vysledek?

Nastuduj si neco o metodach prochazeni stavoveho prostoru a vubec o kombinatoricke optimalizaci.

Algoritmus mi našel řešení 6 balíčků po 1 kuse. Druhý balíček vůbec nepoužil.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 14. 10. 2010, 12:49:51
A to mi má vadit? Tak prostě dokážu něco navíc.

A mimo to, co když opravdu chci nejlevnější sadu nula výrobků?
;) Připadá mi, že neumíš přiznat, že jsi udělal chybu.
Nebereš náhodou debatu trochu jako soutěžení kdo je větší borec, místo jako způsob jak se dobrat řešení/pravdy atd.?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ghost 14. 10. 2010, 13:04:13
Otazka zni: Jak poznas, ze prochazis nejvyhodnejsi reseni hned na zacatku?
To, ze zkousis jako prvni nejlevnejsi balicky je hladovy postup, ktery nemusi byt vzdy optimalmi!!
Kdyz budes mit dva druhy balicku - 1ks/1kc a 5ks/3kc. Budes chtit koupit 6ks. Jaky dostanes vysledek?

Nastuduj si neco o metodach prochazeni stavoveho prostoru a vubec o kombinatoricke optimalizaci.

Algoritmus mi našel řešení 6 balíčků po 1 kuse. Druhý balíček vůbec nepoužil.
A to ti pripada spravne? 6x1ks = 6kc? neni treba lepsi 1x5k + 1x1ks = 4kc ?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jary 14. 10. 2010, 13:08:41
Algoritmus mi našel řešení 6 balíčků po 1 kuse. Druhý balíček vůbec nepoužil.
Jenže to není optimální (správné) řešení. Optimum je, nepletu-li se, řešení takové, že není možné najít řešení lepší. Jenže lepším řešením je balíček 1 kus za 1Kč a 5 kus za 3Kč, dohromady tedy 6kusů za 4Kč. To je lepší, než 6ks za 6kč.
Citace
takže na správné přijde okamžitě. Zrovna před chvílí jsem to ověřil.
Právě jsme dokázali, že tvůj hladový algoritmus nedává optimální řešení.

Mimochodem, optimum je možná definováno jako unikátní, tedy že není možné najít lepší ani stejně dobré řešení. Jistě to ale není de finováno jako "Ne zrovna špatné řešení".
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Ghost 14. 10. 2010, 13:09:05
A to mi má vadit? Tak prostě dokážu něco navíc.

A mimo to, co když opravdu chci nejlevnější sadu nula výrobků?
;) Připadá mi, že neumíš přiznat, že jsi udělal chybu.
Nebereš náhodou debatu trochu jako soutěžení kdo je větší borec, místo jako způsob jak se dobrat řešení/pravdy atd.?
Tady placase prave, ze ty :) Prazdny kos je taky reseni, a je to reseni ktere s jistotou znas a z ktereho pri DP ci B&B vychazis. To je prave ten indukcni zaklad, ktery ty vis a ktery nevyvratis :)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 14. 10. 2010, 13:45:21
Ke ghostově replice není co dodat.

Klidně si to dokazuj indukcí od jedničky. Pokud bude v zadání omezeno, že chtěný počet balení musí být větší než nula, nebo ještě spešl vyřešíš případ pro nulu, bude důkaz samo korektní taky. Jen si stojím za to, že indukce od nuly je
a) korektní
b) Důkaz je o něco jednodušší, protože řešení pro nulu je triviálnější než řešení pro jedničku a indukční krok bude totožný.

Citace
Připadá mi, že neumíš přiznat, že jsi udělal chybu.
Plácáš hezky, ale furt jsi nevysvětlil, v čem by ta chyba měla být.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 14. 10. 2010, 15:48:38
furt jsi nevysvětlil, v čem by ta chyba měla být.
Chyby v uvozovkách:
"Při indukci je vyžadováno, aby pro krok n byl vyřešen krok n-1. Takže mám dvě možnosti, buď vyřeším úplně triviální případ pro nulu..."

První věta je špatně, jak jsem vysvětlil, tohle je jiný druh indukce (a ty jsi to dobře pochopil, když jsi doeditovával příspěvek s definicí indukce v #92).
A druhá věta je taky obecně špatně, od nuly má smysl začínat, jedině pokud funguje indukční krok 0->1 (což obecně neplatí).

"Jen si stojím za to, že indukce od nuly je
a) korektní
b) Důkaz je o něco jednodušší, protože řešení pro nulu je triviálnější než řešení pro jedničku a indukční krok bude totožný."


V naší úloze indukční krok 0->1 neexistuje (indukční krok představuje skládání nákupů, a z 0-nákupů nelze nic složit).
(Dokonce neexistuje ani indukční krok 3->4, existuje pouze indukční krok 1,2,3->4.)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 14. 10. 2010, 16:22:26
Citace
V naší úloze indukční krok 0->1 neexistuje
?? Jaktože neexistuje ?? Ty chceš popřít existenci tohodle tvrzení???

Je-li P(0) nejnižší cena košíku s nula prvky, pak nejnižší cena košíku s jedním prvekm je minimum množiny vzniklé sjednocením množin A, B.
A = { Nejnižší cena balení s jedním prvkem }
B = { P(i) + P(1-i), kde i a 1 - 1 jsou přirozené }

Nebo snad chceš snad říct, že to tvrzení není pravdivé??
Protože přesně todle tvrzení je indukční krok pro T(0) => T(1).

Nebo neumíš dělat sjednocení s prázdnou množinou? Nebo Ti vadí, že se tu nepoužil indukční předpoklad? Tak si dej pozor, ať Tě nezavřou za znásilnění, nástroj máš, tak ho podle tvojí logiky musíš použít...
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 14. 10. 2010, 17:21:34
Takže jsme se shodli, že první text kurzívou byla chyba? Očekávám od tebe "Udělal jsem chybu a hluboce se omlouvám za báťušku Stalina".  :D

V definici B je nějaké typo?

Edit: typo jsem našel a opravil

Ano, to tvoje tvrzení s P(0) je pravdivé. Pravdivé je ale i odpovídající tvrzení s P(-55).
Takže podle tebe je následující tvrzení indukční krok pro T(-55) => T(1):

Je-li P(-55) nejnižší cena košíku s -55 prvky, pak nejnižší cena košíku s jedním prvekm je minimum množiny vzniklé sjednocením množin A, B.
A = { Nejnižší cena balení s jedním prvkem }
B = { P(i) + P(1-i), kde i a 1 - i jsou přirozené }
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 14. 10. 2010, 19:36:05
Už jen krátce, protože todle nejde, předtim se snažíš předefinovat složitost, teď zas matematickou indukci.

Citace
Při indukci je vyžadováno, aby pro krok n byl vyřešen krok n-1....
AAuuuuuuu. Todle Ti právě úplně stačí..... Vždyť právě to Ti matematická indukce zajišťuje.
Protože když je vyřešen krok n-1, tak právě díky MI je vyřešen krok n-2 a proto je vyřešen i krok n-3 atd... Takže proto v kroku n můžeš předpokládat, že máš vyřešený všechny kroky předtím. Takže je to prostě úplně stadardní "typ" indukce. Není žádnej jeden druh indukce, kde dokazuješ P(n) => P(n+1) a druhej P(n_0) .. P(n) => P(n+1), je to jedna a ta samá indukce.

Jinými slovy, platí-li P(0), pro n>=n_0 je indukční krok P(n) => P(n+1) ekvivalentní s P(n_0) .. P(n) => P(n+1)
(zleva doprava je to triviální, zprava doleva to dostaneš pomocí modus ponens a dokázaných tvrzení pro nižší n).

Citace
Takže podle tebe je následující tvrzení indukční krok pro T(-55) => T(1):
Buďto povolím košík se záporným počtem balení, pak není T(1) pravda, nebo to nepovolím, a pak je to nesmysl.
Navíc bys musel hodně odhout definici principu MI, aby to splňovalo princip MI - ale to by nějak šlo, ale to je vzhledem k výše uvedeným faktům irelevantní.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 14. 10. 2010, 22:16:45
AAuuuuuuu. Todle Ti právě úplně stačí..... Vždyť právě to Ti matematická indukce zajišťuje.
Protože když je vyřešen krok n-1, tak právě díky MI je vyřešen krok n-2 a proto je vyřešen i krok n-3 atd... Takže proto v kroku n můžeš předpokládat, že máš vyřešený všechny kroky předtím. Takže je to prostě úplně stadardní "typ" indukce. Není žádnej jeden druh indukce, kde dokazuješ P(n) => P(n+1) a druhej P(n_0) .. P(n) => P(n+1), je to jedna a ta samá indukce.
To, že z A lze odvodit B ještě neznamená, že B je nic. Najdi si "complete induction" v http://en.wikipedia.org/wiki/Mathematical_induction (http://en.wikipedia.org/wiki/Mathematical_induction).

Citace
Buďto povolím košík se záporným počtem balení, pak to není pravda, nebo to nepovolím, pak je to nesmysl.
Pokud povolíš košík s nulovým počtem balení, nevidím důvod proč nepovolit i se záporným počtem balení. Ale o to, jestli povolit nebo nepovolit tu vůbec nejde.
To tvrzení pravdivé je, a já jsem je uváděl proto, aby ti pomohlo navést tě k následujícímu:

Pravdivé je i tvrzení
Nejnižší cena košíku s jedním prvkem je minimum množiny vzniklé sjednocením množin A, B.
A = { Nejnižší cena balení s jedním prvkem }
B = { P(i) + P(1-i), kde i a 1 - i jsou přirozené }


Jinými slovy tvůj předpoklad "Je-li P(0) nejnižší cena košíku s nula prvky" je zcela zbytečný. Snažíš se vyrobit indukční krok 0->1 tam, kde žádný není.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 14. 10. 2010, 23:03:07
Citace
Najdi si "complete induction" v http://en.wikipedia.org/wiki/Mathematical_induction (http://en.wikipedia.org/wiki/Mathematical_induction).
A tim jako tvrdíš co?
edit po editu:
Už tuším. Ty jsi napadal mé tvrzení, že v MI stačí vědět, že je vyřešen krok 0 a pro krok n že je vyřešen krok n-1. Tak jsem Ti dokázal, že tomu tak je. Pokud nevěříš mému naznačení důkazu, tak věta 3.3a
v
http://math.feld.cvut.cz/habala/teaching/dma/dmknih03.pdf

Druhou věc, kterou jsem tvrdil bylo, že neexistuje jiná indukce. Pokud je slabý a silný princip indukce EKVIVALENTNÍ, nemůže být JINÝ. protože kdyby byl jiný, nemohl by být ekvivalentní.

Citace
To, že z A lze odvodit B ještě neznamená, že B je nic.

Já jsem netvrdil, že je něco k ničemu. Trochu to obracíš ne? Ty Celou dobu tvrdíš, že já něco musím dokazovat tak a tak, že na to musím použít jinou indukci atd....
Já ti jen vyvracím tvoje tvrzení, ukazuju, že můj přístup je korektní ba i v něčem ekvivalentní s tvým.

---

Btw. i v tom textu máš:
Usually, n = 0 or n = 1.
Takže sis sám vyvrátil, že musíš začít u jedničky.

Citace
Pokud povolíš košík s nulovým počtem balení, nevidím důvod proč nepovolit i se záporným počtem balení. Ale o to, jestli povolit nebo nepovolit tu vůbec nejde. To tvrzení pravdivé je...
Nevidíš důvod u takhle triviální věci a poučuješ tady lidi o (vzhledem k tomu) poměrně složitejch věcech jako je korektnost MI a teorie složitosti a NP-úplnosti?

Pokud povolíš košík se záporným počtem kusů, tak můžeš např. udělat košík s jedním kusem jako 1x3kusy + (-1)x2kusy. Takže jaksi už vůbec nejde použít indukce, on samo ani nebude fungovat ten algoritmus, dokonce ani nebude (v drtivé většině případů) existovat minimální cena za X kusů (proč si vymysli sám).

Citace
Jinými slovy tvůj předpoklad "Je-li P(0) nejnižší cena košíku s nula prvky" je zcela zbytečný. Snažíš se vyrobit indukční krok 0->1 tam, kde žádný není.
Jaktože tam není? Dolazuju indukcí od nuly, takže tam je z definice MI.
Pokud P(0) platí a P(0),..,P(n-1) => P(n), tak je to prostě korektní důkaz. Ani jedno z těch tvrzení jsi nijak nevyvrátil, jen furt s odpuštěním mektáš, že to nesmím (proč?) nebo že je to zbytečný (což není, nějakej první krok udělat musím a P(1) je složitější než P(0)) a i kdyby nakrásně bylo, tak to na správnosti důkazu nic nemění.

Navíc ten důkaz i odpovídá algoritmu - algoritmus přeci nezačne tak, že si dá do košíku balení s jedním prvkem a pak začne cyklus, algoritmus začne cyklus s prázdným košíkem.

Citace
Jinými slovy tvůj předpoklad "Je-li P(0) nejnižší cena košíku s nula prvky"
Ano, v prvním kroku indukce je tento předpoklad zbytečný. Tak se mám kvůli tomu oběsit? Dokážeš pochopit, že když se pracuje s MI, že prostě dokážeš P(n_0) a P(0),..,P(n-1) => P(n) a tím máš důkaz hotovej? Že tě nezajímá jak to je konkrétně v prvním, druhém, stém kroku, ani jestli a jak v kterém kroku použiješ indukční předpoklady. Prostě pokud tyto dvě implikace platí, výrok je dokázanej. Tečka.

Co třeba důkaz MI že pro posloupnost
a0=1
a_2i=2*a_(2i-2)
a_2i-1=1
Platí:Je-li i je sudé pak a_i=2^(i/2) jinak a_i=1

Tam dokonce nejen A(1), ale dokonce každej druhej indukční krok nebude potřebovat indukční premisu. Vadí to snad nějak tomu důkazu? Nebo jako nesmím použít MI, když v některejch krocích nepoužiju premisu? To Stalin zakázal?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 14. 10. 2010, 23:25:20
A to ti pripada spravne? 6x1ks = 6kc? neni treba lepsi 1x5k + 1x1ks = 4kc ?

Můj algoritmus jsem vytvořil na původní zadání. To znamená, že zadávám balíček, který obsahuje počet kusů a cenu za kus. Bohužel jsem si nevšiml, že za 5 ks je cena za celek a to 3Kč, Předpokládal jsem, že je cena za jeden kus.
Takže program určil správné řešení: 6x1 ks po 1Kč, ale já jej zadal špatně. To druhé řešení zamítl, neboť 1 x 5 ks po 3Kč + 1x 1 ks po 1Kč by dalo 16Kč což by bylo nevýhodné.
Takže jsem zadal znovu, tentokrát balíček o 5 ks a ceně 60 haléřů za kus a vypočítal to opět správně. Tj. 1+1 kus.




Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 14. 10. 2010, 23:54:18
Aby jste si udělali představu jak můj program to počítá:

1. Nejprve seřadím balíčky od nejvýhodnějších po nejméně výhodné (zleva-doprava).
2. Pak porovnám vždy dva vedle sebe balíčky zda ten napravo má součin počtu prvků a ceny menší než ten nalevo. Pokud ne tak se vyřadí. (Je příliš drahý a dokáže jej nahradit levý za nižší cenu).
3. Pomocí rekurze generuji sestavy balíčků tak, aby nejprve bral výhodnější balíčky a pak méně výhodné a nekonec ty mejméně výhodné. Tím zaručím, že na předních místech budou nejlepší sestavy a na posledních ty nejméně výhodné. Pro každou sestavu vypočítám cenu a pokud je nižší než předcházející, pak ji zaznamenám.

Ta připojeném obrázku je vidět jak se generují sestavy pro 4 balíčky:
40ks po 7 Kč
10ks po 8Kč
3ks po 9Kč
1ks po 10Kč

Na jednotlivých řádkách je vidět jak tvoří sestavy.
Nejprve se snaží použít co nejvíce levé položky (hladovost).
A pak postupuje k těm pravým.
Napravo je vidět cena.
Všimněte si, že cena s přibývajícími řádky klesá.

(http://img839.imageshack.us/img839/642/optimumrekurze.png)

Tímto jednoduchým řešením jsem dosáhl toho, že je mnohem vyšší pravděpodobnost, že optimální sestava se bude nalézat spíše na začátku, než na konci.

Taky si všimněte, že balíčky nesestavuji podle počtu kusů, ale podle cenové výhodnosti, tím zajistím, že optimální sestava bude nalezena dříve (bude na řádku s nižším číslem). Balíčky jsou seřazeny podle ceny za kus!
Balíček A je tedy cenově výhodnější než balíček B, ale neznamená to, že má více prvků.

Ještě si všimněte, že negeneruji kombinace, jejichž součet je jiný jak zadaný.


Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 14. 10. 2010, 23:59:27
Oprava: cena s přibývajícími řádky stoupá.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 15. 10. 2010, 00:03:07
jaromire, my všichni víme, jak tvuj program počítá. Akorát zároveň víme.
a) jeho složitost je exponenciální.
b) nemusí najít nejlepší řešení v rozumném čase
Viz protipříklad
x balení s
3300-3990 kusů
                       á 1Kč
4000 kusů á 2Kč
1 kus     á   1000000Kč
a chci 1600 kusů.
c) v každém případě to počítá pomaleji než dynamické programování
(neboť to zařezává řešení až při přesažení doteď nalezené ceny, zatímco dynamické programování zařezává řešení mnohem dříve).

Tak prosím o čem nás chceš přesvědčit?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: jaromír 15. 10. 2010, 00:10:46
No a to bych chtěl, zaříznout to ve správném okamžiku, protože pak zbytečně dlouho počítá.
... Ale to ještě nevím jak.
Jdu spát.

Asi si opravdu budu muset něco nejdřív nastudovat...

Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 15. 10. 2010, 00:13:44
Jenže zaříznout to dřív opravdu nejde - nikdy nevyloučíš, že v těch zaříznutejch možnostech není lepší řešení.
Btw. pokud bys opravdu to dokázal udělat polynomiálně, tak dostaneš cenu tuším 100000$ (nebo milion, teď nevim)? Tak máš dobrou motivaci pro studium :-)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 15. 10. 2010, 16:24:57
Druhou věc, kterou jsem tvrdil bylo, že neexistuje jiná indukce. Pokud je slabý a silný princip indukce EKVIVALENTNÍ, nemůže být JINÝ. protože kdyby byl jiný, nemohl by být ekvivalentní.
To, že jsou dvě věci ekvivalentní přece neznamená, že nemohou být jiné. To bys mohl úplně stejně tvrdit, že neexistuje žádná matematická indukce, protože ji lze odvodit ze základních důkazních metod. Ano, každý důkaz indukcí můžeš přepsat tak, že formálně půjde o důkaz bez použití indukce, jenomže ten princip indukce tam bude pořád vidět.

Podobně i silná indukce je od slabé dobře rozlišitelná:
Jestliže máš silnou indukci
T(1)+T(2) ...+T(n-1) => T(n)
můžeš ji sice převést na slabou tak, že definuješ
U(n)=T(1)+T(2) ...+T(n) a získáš indukční krok U(n-1)=>U(n).
Jenomže na tom tvrzení U bude dobře vidět, že je v onom speciálním tvaru.

Citace
Citace
Pokud povolíš košík s nulovým počtem balení, nevidím důvod proč nepovolit i se záporným počtem balení. Ale o to, jestli povolit nebo nepovolit tu vůbec nejde. To tvrzení pravdivé je...
Nevidíš důvod u takhle triviální věci a poučuješ tady lidi o (vzhledem k tomu) poměrně složitejch věcech jako je korektnost MI a teorie složitosti a NP-úplnosti?
Pokud povolíš košík se záporným počtem kusů, tak můžeš např. udělat košík s jedním kusem jako 1x3kusy + (-1)x2kusy.
Máš pravdu, moje chyba. Nechápu takovou triviální věc a opovažuju se tady poučovat.
 :P Ale trvám na tom, že není pravdivé tvoje tvrzení, že moje tvrzení není pravdivé. A také není pravdivé tvoje tvrzení, že by bylo nutné povolovat nějaké záporné počty balení.

Citace
Co třeba důkaz MI že pro posloupnost
a0=1
a_2i=2*a_(2i-2)
a_2i-1=1
Platí:Je-li i je sudé pak a_i=2^(i/2) jinak a_i=1

Tam dokonce nejen A(1), ale dokonce každej druhej indukční krok nebude potřebovat indukční premisu. Vadí to snad nějak tomu důkazu? Nebo jako nesmím použít MI, když v některejch krocích nepoužiju premisu?
U důkazu matematickou indukcí, kterým budu dokazovat, že pro každé přirozené n platí sqrt(n^2)=abs(n), dokonce žádný "indukční krok" nebude potřebovat indukční premisu, a důkazu to taky nijak nevadí...

Citace
nějakej první krok udělat musím a P(1) je složitější než P(0)
...
Ano, v prvním kroku indukce je tento předpoklad zbytečný
Tak já ti prozradím pointu:
První krok udělat nemusíš. A tvůj indukční předpoklad je zbytečný ve všech krocích, a zbytečné jsou i samotné kroky:
Snažíš se nacpat indukci tam, kde žádná není potřeba. Následující tvrzení přece platí i bez jakýchkoli premis:

Nejnižší cena košíku s n prvky je minimum množiny vzniklé sjednocením množin A, B.
A = { Nejnižší cena balení s n prvky }
B = { P(i) + P(n-i), kde i a n - i jsou přirozené }
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 16. 10. 2010, 16:36:28
Citace
To, že jsou dvě věci ekvivalentní přece neznamená, že nemohou být jiné.
To už je slovíčkaření - tak si pojďme definovat, o čem se bavíme. Ty jsi mě napadal, že nemůžu použít tudle indukci a musím použít jinou. Čimž si "jinost" definoval jako schopnost dokázat jinou množinu tvrzení. A v tomto smyslu ty dvě indukce prostě jiné nejsou.
Jinými slovy - ekvivalentní znamená v matematice záměnné. Takže pokud jsou dvě věci ekvivalentní, není pravda, že musím použít jednu a nesmím použít druhou.

Citace
První krok udělat nemusíš. A tvůj indukční předpoklad je zbytečný ve všech krocích, a zbytečné jsou i samotné kroky. Snažíš se nacpat indukci tam, kde žádná není potřeba. Následující tvrzení přece platí i bez jakýchkoli premis...
Samozřejmě, že to tvrzení je pravdivé samo o sobě. Btw. jestli sis všimnul, tak ve svém důkazu jsem právě podobné lema zavedl. Jenže to Ti nestačí - ty totiž při výpočtu P(n) hodnoty P(i) neznáš!
Protože ty přeci v tom algoritmu nesčítáš minimální košíky, ty sčítáš nějaké čísla, o kterých tvrdíš, že to jsou minimální košíky. A to, že ta čísla co sčítáš jsou opravdu minimální košíky je právě ten indukční předpoklad.

Formálněji: Máš funkci danou předpisem:
f(0) = 0
f(n) = min( i(n), f(a) + f(b): a+b = n), a,b,n je z N, i(n) = nejnižší cena balení s i prvky,
existuje-li, jinak nekonečno.
Tudle funkci počítá ten můj algoritmus (nemám tam teda pro jednoduchost ošetřenou nulu na vstupu). Chceš dokázat, že pro každé n z N platí tvrzení T(n).
P(n) = f(n)
K tomu, abys toto tvrzení dokázal tu indukci potřebuješ. Protože pro každé n potřebuješ aplikovat ono lema + indukční předpoklad, že f(a) a f(b) jsou minimální košíky pro a/b prvků.

Pokud nevěříš mě, tak si přečti to, co jsem už asi pěštrát postoval:
http://math.feld.cvut.cz/habala/teaching/dma/dmknih03.pdf
příklad 3a.d algoritmus pro výpočet faktoriálu. V podstatě to samé.
Pro důkaz n! =n*(n-1)! indukci nepotřebuješ. Pro důkaz korektnosti algoritmu tento vzorec užívajícího však ano.

A pokud jde o to, že nikde dál nepoužiješ předpoklad pro nulu, tak to je MI úplnej šumák.
Pro MI je prostě potřeba mít nějakej pevnej bod, z kterýho začneš. Jelikož se bod pro nulu sestrojí nejjednodušeji a zároveň nezesložití indukční krok, je velmi vhodné začít z něho. Je úplně jedno, jestli ho pak někdy použiješ nebo ne.

Citace
U důkazu matematickou indukcí, kterým budu dokazovat, že pro každé přirozené n platí sqrt(n^2)=abs(n), dokonce žádný "indukční krok" nebude potřebovat indukční premisu, a důkazu to taky nijak nevadí...
A proto klidně můžu MI užít. Ale tady je jednodušší to tvrzení dokázat jinak, takže užití MI není nejvhodnější, byť možné. To však není náš případ, my jak jsem ukázal MI užít musíme.

Citace
Ale trvám na tom, že není pravdivé tvoje tvrzení, že moje tvrzení není pravdivé. A také není pravdivé tvoje tvrzení, že by bylo nutné povolovat nějaké záporné počty balení.
Na to, aby šlo psát f(a) + f(b) je třeba definovat operaci sesypání košíku a co je to košík. Definujeme ho tedy jako n-rozměrný vektorový prostor nad pologrupou jejíž hodnoty jsou počet balení, kde bázi tvoří jednotlivá balení. Sesypání košíku je pak součet vektorů. Cena košíku c(k) je daná jako skalární součin vektoru košíku a vektoru ceny jednotlivých balení. Velikost košíku v(k) je skalární součin s vektorem počtu produktů v balení.
P(n) a f(n) má pak definiční obor daný oborem hodnot funkce v(k).

Není-li možný záporný počet balení, pak je danou grupou grupa N_0 a obor hodnot v(k) a tedy definiční obor f(n) je taktéž N_0.
v T(-55) je užito f(-55), ta je však definovaná taktéž pouze nad N_0. Tvrzení tedy nemá smysl. (stejně jako nemá smysl tvrzení, ve kterém je dělení nulou.

Je-li možný záporný počet balení, pak T(1) neplatí. Protože
T(1) je P(1) = f(1), kde f(1) = min(i(1)), tedy
Přitom snadno se sestrojí protipříklad s balením po dvou za 2Kč a po třech za 3(Kč), kde
f(1) = nekonečno, přitom P(1) <= 1
neboť pro k= {1*3kusy - 2*2kusy} je v(k)=1 a c(k)=1.
A T(1) tedy neplatí. Co jiného jsem předtím tvrdil?

Pozn.: T(-55) => T(1) je v tomto případě pravdivé: (false => false) <=> true, ale nemůže být indukčním krokem, protože T(n) je nepravdivé pro každé n (a tedy vůbec nelze užít indukci). O pravdivosti této celé implikace jsem předtím ale nemluvil.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 18. 10. 2010, 22:45:31
[slovíčkaření]
[/slovíčkaření]



Aby nedošlo k omylu, označím
Lemma:
Nejnižší cena košíku s n prvky je minimum množiny vzniklé sjednocením množin A, B.
A = { Nejnižší cena balení s n prvky }
B = { P(i) + P(n-i), kde i a n - i jsou přirozené }


Lemma+ bude tvoje původní tvrzení s předpokladem
"Je-li P(n) nejnižší cena košíku s n prvky"



Citace
Formálněji: Máš funkci danou předpisem:
f(0) = 0
f(n) = min( i(n), f(a) + f(b): a+b = n), a,b,n je z N, i(n) = nejnižší cena balení s n prvky,
existuje-li, jinak nekonečno.
...
 Chceš dokázat, že pro každé n z N platí tvrzení T(n).
P(n) = f(n)
K tomu, abys toto tvrzení dokázal tu indukci potřebuješ. Protože pro každé n potřebuješ aplikovat ono lema + indukční předpoklad, že f(a) a f(b) jsou minimální košíky pro a/b prvků.
Přesněji:
Pokud je f(n) definována korektně, P(n) = f(n) plyne okamžitě z Lemmatu, na to indukci nepotřebuješ.
Indukcí dokazuješ to, že f(n) je definována pro každé n z N (tj. že f(a) a f(b) jsou "v pravý čas" k dispozici).

Citace
A pokud jde o to, že nikde dál nepoužiješ předpoklad pro nulu, tak to je MI úplnej šumák.
Pro MI je prostě potřeba mít nějakej pevnej bod, z kterýho začneš. Jelikož se bod pro nulu sestrojí nejjednodušeji a zároveň nezesložití indukční krok, je velmi vhodné začít z něho. Je úplně jedno, jestli ho pak někdy použiješ nebo ne.
Obecně pro jakoukoli úvahu platí, že je nesmyslné vytvářet pevný bod, od kterého se stejně nebudu nikdy odrážet. Navíc není pravda, že pro MI je třeba mít pevný bod (vysvětlím dále).

A teď k naší konkrétní úloze:
Indukční krok (odpovídá bodu (b) dále) zní:
Pro každé n z N: jestliže je f(k) definováno pro každé k, 1<=k<n, je definováno i f(n).
Indukcí dokazuješ korektnost rekurzivní části definice funkce f, tj. od jedničky nahoru; jak je definováno f(0) nebo f(-55), nebo jestli je vůbec definováno, nemá na důkaz vůbec žádný vliv.

Možná, že tě plete, že většinou indukce pevný bod vyžaduje, a ty se do pozice pevného bodu snažíš vmanévrovat nulu. V našem případě ale pevný bod není u indukce vůbec potřeba:

Silná indukce s pevným bodem vypadá takto:
(a) T(1) platí
(b) pro každé n>=2 jestliže T(k) platí pro k=1..n-1, pak platí i T(n)

(a) bývá většinou potřeba proto, že (b) nefunguje pro n=1. Ale v našem případě (b) funguje i pro n=1, takže pevný bod (a) není třeba.



Citace
A proto klidně můžu MI užít. Ale tady je jednodušší to tvrzení dokázat jinak, takže užití MI není nejvhodnější, byť možné.
Souhlasím. Do důkazu pro sqrt(n^2)=abs(n) je možné přicpat indukční kroky pro každé n, a nepoužívat je. Důkaz se tím ale bezdůvodně zkomplikuje.
Stejně tak ale uměle přicpáváš každý druhý indukční krok u důkazu pro a_2i=2*a_(2i-2): normální by bylo použít slabou indukci a skákat po sudých číslech. Jestliže chceš mermomocí skákat po jedničkách, musíš použít silnou indukci, a rozlišovat jestli jsi na sudém nebo lichém čísle, a indukční krok používat jenom u sudých. Důkaz se tím bezdůvodně komplikuje.
No a v našem případě naší úlohy s baleními je to podobné. Můžeš uměle přidat indukční krok pro 0 nebo i pro -55, ale důkaz se jenom bezdůvodně zkomplikuje.



Citace
...co je to košík. Definujeme ho tedy jako n-rozměrný vektorový prostor nad pologrupou jejíž hodnoty jsou počet balení, kde bázi tvoří jednotlivá balení.
Technická poznámka: Formálně vektorový prostor nad pologrupou (která není současně tělesem) nesestavíš. Množina košíků tedy není podprostorem vektorového prostoru, ale jde o část podprostoru - lineární kombinace s koeficienty z N_0.

Citace
Není-li možný záporný počet balení, pak je danou grupou grupa N_0 a obor hodnot v(k) a tedy definiční obor f(n) je taktéž N_0.
Technická poznámka: Pokud úloha zní, že chci v košíku "přesně" x ks zboží a ne "alespoň" x ks, nemusí být obor hodnot v(k) celé N_0.  Představ si "bázi" tvořenou jediným balením s 2 ks zboží.
Ale to neznamená problém, v definici f to řešíš pomocí nekonečna.

Citace
v T(-55) je užito f(-55), ta je však definovaná taktéž pouze nad N_0. Tvrzení tedy nemá smysl. (stejně jako nemá smysl tvrzení, ve kterém je dělení nulou.
(Pozn.: Přesněji bys měl říct "je užito P(-55)": Funkci f pro Lemma+ nepotřebuješ.)

Předpoklad Lemmatu+ by měl být správně zapsán takto: "Je-li P(n) definováno, ...". Pak je tvrzení T(-55) v pořádku.
Formálně nelze Lemma+ napsat pomocí "Je-li P(n) nejnižší cena košíku s n prvky,...": Formálně je totiž Lemma+ zapsáno ve tvaru "pro každé n platí T(n)", a formule by takto nebyla korektně sestavená, jak jsi zrovna vysvětlil.

edit: typo: označení Lemma' místo Lemma+
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 19. 10. 2010, 11:39:10
Citace
Habala v tom článku taky říká, že silná indukce existuje, a ty mu to popíráš.
Popírám to ve smyslu, že silnou indukcí lze dokázat jinou množinu tvrzení než slabou. Silná a slabá indukce jsou jen dva pohledy na axiomy indukce z teorie množin, jestli to chceš přesně:
http://logika.wz.cz/files/baktm.pdf (http://logika.wz.cz/files/baktm.pdf)

Citace
Pokud je f(n) definována korektně, P(n) = f(n) plyne okamžitě z Lemmatu, na to indukci nepotřebuješ.
f(n) není definována korektně nebo nekorektně. f(n) je definována algoritmem.

f(0) = 0
f(n) = min( i(n), f(a) + f(b): a+b = n), a,b,n je z N, i(n) = nejnižší cena balení s i prvky,

kdyby byla f(n) definována jako
f(n) = min( i(n), P(a) + P(b): a+b = n), a,b,n je z N, i(n) = nejnižší cena balení s i prvky,
tak indukci nepotřebuješ. Jenže tato ta funkce definovaná prostě není. Takže potřebuješ vědět, že jsi v kroku n  vyřešil předchozí kroky.

V podstatě se dá vulgárně říci: pokud v n-tém kroku algoritmu používáš výsledky z předchozích kroků, dokazuje se algoritmus indukcí.

Citace
Možná, že tě plete, že většinou indukce pevný bod vyžaduje, a ty se do pozice pevného bodu snažíš vmanévrovat nulu. V našem případě ale pevný bod není u indukce vůbec potřeba:
Prosím, přestaň psát nějaké dojmy a používej matematicku. Jak je definovaná věta o MI? Platí-li P(n_0) a P(n_0) ... P(n) => P(n+1), pak....
Tak jaktože není pevný bod potřeba? K tomu, abys použil větu, musíš splnit všechny předpoklady.

Ano, můžeš si jestli chceš zopakovat důkaz věty o MI aplikovanej na tento konkrétní příklad, tím si dokázat slowthinkerovu větu o matematické indukci problému batohu a tu pak aplikovat bez potřeby pevného bodu. Pravda, bude diskutabilní, jestli vůbec jde o indukci (ta v sobě inherentně nese potřebu pevného bodu, viz schéma axiomu o induxi) a bude to asi desetkrát složitější a daleko méně čitelné, ale jde to. Jestli si chtěl slyšet todle... :-)
Já preferuju, že si udělám byť nepotřebný pevný bod, který mám dokázán hned a použiju již existující větu. To je taková úchylka matematiků, že když vyřešej jeden příklad, tak ostatní na něj převáděj.

Znáš ten vtip s tim, hoří barák, máš hadici a hydrant a sirky, co uděláš?
No a teď seš ve stejné situaci a barák nehoří.... Co uděláš teď?
Do praktickýho života seš asi použitelnější, ale na matiku se Tvuj přístup fakt nehodí...



Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 20. 10. 2010, 10:57:48
[slovíčkaření]
[/slovíčkaření]

Citace
f(n) není definována korektně nebo nekorektně. f(n) je definována algoritmem.

f(0) = 0
f(n) = min( i(n), f(a) + f(b): a+b = n), a,b,n je z N, i(n) = nejnižší cena balení s i prvky,
Matematickou teorii, ve které se definuje algoritmem, bohužel neznám. Já používám teorii množin, kde se může definovat rekurzí, kterážto je úzce spojena s principem indukce. (pokud bys nevěděl o čem mluvím, podívej se do článku, který jsi už 5x postnul).
Připadá mi ale, že moje definice rekurzí bude odpovídat tvé definici algoritmem, takže v tom asi nebude žádná potíž.

Potíž je v tom, že definice rekurzí/algoritmem nemusí být definována korektně - zaměn v definici třeba "a+b" za "a-b", a máš zásadní problém.
Korektnost dokážeš právě indukcí.

Pokud se podívám na tvůj indukční krok pro 0 (tak jak je na začátku #104)

"Je-li P(0) nejnižší cena košíku s nula prvky, pak nejnižší cena košíku s jedním prvekm je minimum množiny vzniklé sjednocením množin A, B.
A = { Nejnižší cena balení s jedním prvkem }
B = { P(i) + P(1-i), kde i a 1 - 1 jsou přirozené }"


tak vidím, že v důkazu nemá P co dělat (P je takto použito v Lemmatu a sám jsi uznal, že pro Lemma indukce není třeba), na jeho místě má být f.
Osobně odhaduji, že intuitivně důkaz asi chápeš, jenom ho nedokážeš zformalizovat, protože máš zřejmě zkušenosti jenom s intuitivní matematikou a s formální matematikou ne. Odhaduji, že jsi asi chtěl vyjádřit toto:

"Je-li f(0) definováno, pak je definováno i f(1). Důkaz: f(1) je minimum množiny vzniklé sjednocením množin A, B, A= ..."

Potom by důkaz byl formálně v pořádku.

Citace
Já preferuju, že si udělám byť nepotřebný pevný bod, který mám dokázán hned a použiju již existující větu. To je taková úchylka matematiků, že když vyřešej jeden příklad, tak ostatní na něj převáděj.
Zapomněl jsi na drobný detail: Matematici převádějí, pokud je převádět skutečně třeba.
Tohle je tvůj způsob uvažování:

Máš dokázat, že pro každé n z N platí sqrt(n^2)=abs(n).
Znáš matematickou indukci.
Víš o úchylce matematiků, převádět problémy na dříve vyřešené věci.
Pro důkaz proto použiješ matematickou indukci.
Dokážeš nejprve pevný bod sqrt(1^2)=abs(1).
To, že pevný bod dále nepoužiješ, tě netrápí: naučil ses, že indukce vyžaduje pevný bod.
Pak dokážeš indukční krok. To, že že indukční předpoklad nepotřebuješ, tě netrápí: naučil ses, že indukce vyžaduje indukční krok.

Citace
Prosím, přestaň psát nějaké dojmy a používej matematicku. Jak je definovaná věta o MI? Platí-li P(n_0) a P(n_0) ... P(n) => P(n+1), pak....
Tak jaktože není pevný bod potřeba? K tomu, abys použil větu, musíš splnit všechny předpoklady.
:) Neměl by se tolik ohánět matematikou, pokud neznáš matematické základy a teorii množin.
Budeš se možná divit, ale "čistá" věta o indukci (a obecněji  transfinitní indukci) v teorii množin pevný bod nepotřebuje: nejjednodušší verze věty o indukci zní takto:
Je-li M podmnožina N_0 taková, že
pro každé x platí: x je podmn. M => x je prvkem M
(toto je "indukční krok")
pak M = N_0.

Pevný bod (neboli "0 je prvkem M") tam samozřejmě je schovaný, plyne však z "indukčního kroku", a není třeba jej samostatně uvádět.

Podobně je tomu u "slowthinkerova důkazu" (nebo jak mu říkáš): pevný bod tam je, ale protože je zabudován v indukčním kroku, není třeba jej zvlášť dokazovat.

Citace
Ano, můžeš si jestli chceš zopakovat důkaz věty o MI aplikovanej na tento konkrétní příklad, tím si dokázat slowthinkerovu větu o matematické indukci problému batohu a tu pak aplikovat bez pevného bodu. Pravda, bude diskutabilní, jestli vůbec jde o indukci (ta v sobě inherentně nese potřebu pevného bodu, viz schéma axiomu o induxi) a bude to asi desetkrát složitější a daleko méně čitelné, ale jde to.
To, že něcomu nerozumíš, neznamená, že je to 10x složitější, než to co chápeš.
"slowthinkerův důkaz" je v podstatě tvůj důkaz, správně naformulovaný a ořezaný o všechny zbytečnosti.



Shrnutí:
Shrnutí chyb ve tvém důkazu (první chyba je fatální, druhá důkaz zbytečně komplikuje):
- v indukčním kroku používáš P na místě f
- zcela zbytečně do důkazu přidáváš krok 0->1

Pokud máš nějaké konkrétní výhrady k mému důkazu (kromě toho, že si pletu dojmy s pojmy), sem s nimi. (pokud se v něm neorientuješ, protože je rozesetý po vlákně, můžu ti ho znovu zformulovat)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 20. 10. 2010, 14:47:26
Citace
Matematickou teorii, ve které se definuje algoritmem, bohužel neznám
Nevím, co se snažíš dokázat Ty, ale já dokazuju platnost algoritmu. Čili dokazuji, že funkce f, kterou vyčísluje ten algoritmus, je ekvivalentní s funkcí P.
Pokud dokazuješ něco o nějaké jiné funkci definované nějakou rekurkzí, můžeš, ale pak nechápu proč to děláš v tomto vlákně, tady je debata o důkazu algoritmu a tedy o funkci definované tímto algoritmem.

Jinak jestli nevíš, co je to fce definovaná algoritmem, tak to je Tvůj problém. Např. se dá definovat jako funkce, která jedefinovaná na množině vstupů algoritmu, pro který algoritmus doběhne a hodnota funkce pro daný vstup je výsledek algoritmu.

Druhá možnost jak definovat funkci pomocí algoritmu konstrukční: přes ekvivalenci TS a rekurzivně vyčíslitelných funkcí. Tzn. funkce definovaná algoritmem je taková funkce, která je ekvivalentní TS implementujícímu daný algoritmus.

Ať to uděláš jak checš, v každym případě musíš dokazovat něco o funkci, která je počítaná tak, jak počítá ten algoritmus. Takže tak funkce je tím algoritmem definovaná.

Citace
Potíž je v tom, že definice rekurzí/algoritmem nemusí být definována korektně - zaměn v definici třeba "a+b" za "a-b", a máš zásadní problém.
Ano máš problém. Budeš totiž dokazovat tvrzení, které s algoritmem nesouvisí. No a?
Popř. pokud by v algoritmu bylo a-b, tak by důkaz prostě nešel provést - což neni divu, protože by algoritmus nefungoval...
Nebo (v tomto případě) dokážeš z definice funkce spor. A tak dokážeš, že taková fce neexistuje. No a?

Citace
tak vidím, že v důkazu nemá P co dělat (P je takto použito v Lemmatu a sám jsi uznal, že pro Lemma indukce není třeba), na jeho místě má být f.
Ach jo. Tak znova. Dokazuji, že P(a) = f(a). Tak jaktože v důkazu nemá P(a) co dělat??

f(a) je definována jako
f(n) = min (f(i)+ f(j) ....)
protože tak vyčísluje tu funkci algoritmus.

Abych T(n) dokázal, tak
1) použiji indukční předpoklad, že f(k) = P(k) pro všechna f(k) v definici f(n) a tedy
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...)
2) použiju Lemma, že min (P(i)+ P(j)...) = P(n)
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...) = P(n)
      ◻   

Citace
Je-li M podmnožina N_0 taková, že pro každé x platí: x je podmn. M => x je prvkem M (toto je "indukční krok") pak M = N_0.
Teorii množin tolik neumim, ale to, co popisuješ je co vím modifikované tvrzení o
transfinitní indukci a nikoli o MI. Takže
1) to co popisuješ IMHO není matematická indukce
2) M podle předpokladu obsahuje sama sebe a tedy obsahuje prvek: množinu všech přirozených čísel. Množina všech přirozených čísel je první nekonečno. Takže prvkem M je nekonečno a tedy M není podmnožina N_0. Spor.

Tzn. žádná taková M neexistuje a toto tvrzení není ani matematická, ani transfinitní ani jiná indukce ale tvrzení o ničem.

Citace
To, že pevný bod dále nepoužiješ, tě netrápí: naučil ses, že indukce vyžaduje pevný bod.
Hele já asi končím. Todle nemá cenu. Prostě existuje věta o matematické indukci s danými předpoklady. Pokud někdo používá důkaz MI, znamená to (alespoň mezi všema lidma na MFF, co jsem se zatím setkal), že aplikují danou větu. V předpokladech MI je existence pevného bodu. Takže buď použiju větu o MI a musím dokázat tvrzení pro pevný bod, nebo nepoužiju větu o MI - ale pak nedokazuju matematickou indukcí. Žádná jiná možnost prostě není.

Btw. i v Tvém důkazu je vlastně pevný bod. Tvrdíš, že pro P(1) nepotřebuješ předpoklady. Jenže to je třeba taky dokázat (byť je to taky vcelku trivoš). Tím ale přistupuješ k P(1) jinak než ke všem ostatním. Takže také používáš pevný bod. A navíc protože nedokazuješ explicitně P(n_0) nemůžeš použít větu o MI, takže asi používáš nějakou svojí indukci. a tu bys měl dokázat.

Ono to totiž bez pevného bodu to nejde! Např platí   (a = a - 1) =>  ((a+1) = (a+1) - 1). To ale neznamená, že a = a - 1. Proto je pevný bod pro MI nutnost. Ona i ta věta o transfinitní indukci se pak musí užít s pevným bodem:
http://mathworld.wolfram.com/TransfiniteInduction.html (http://mathworld.wolfram.com/TransfiniteInduction.html)

Citace
Pokud máš nějaké konkrétní výhrady k mému důkazu (kromě toho, že si pletu dojmy s pojmy),
Nesouhlasím s tím, že pokud
f(n) = min (f(i)+ f(j) ....)
pak tvrzení
P(n) = f(n) plyne okamžitě Lematu, aniž bys použil MI (popř. postup MI podobný). Pokud nesouhlasíš, tak to formálně dokaž.

PS: Co se týče mojeho matematického vzdělání, doporučil bych Ti se krotit, by ses neztrapnil.... :-) Ale to jen tak na okraj.... :-)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 23. 10. 2010, 01:38:45
Indukce

co popisuješ je co vím modifikované tvrzení o
transfinitní indukci a nikoli o MI. Takže
1) to co popisuješ IMHO není matematická indukce
2) M podle předpokladu obsahuje sama sebe a tedy obsahuje prvek: množinu všech přirozených čísel. Množina všech přirozených čísel je první nekonečno. Takže prvkem M je nekonečno a tedy M není podmnožina N_0. Spor.
1) matematická indukce není nic jiného než transfinitní indukce oříznutá na přirozená čísla.
2) to jsi mě dostal. Zapomněl jsem omezit implikaci na konečné množiny. Správně má ve větě být "pro každé konečné x platí:"

Citace
Btw. i v Tvém důkazu je vlastně pevný bod. Tvrdíš, že pro P(1) nepotřebuješ předpoklady. Jenže to je třeba taky dokázat (byť je to taky vcelku trivoš). Tím ale přistupuješ k P(1) jinak než ke všem ostatním. Takže také používáš pevný bod. A navíc protože nedokazuješ explicitně P(n_0) nemůžeš použít větu o MI, takže asi používáš nějakou svojí indukci. a tu bys měl dokázat.
Mluvíš o důkazu Lemmatu? V tom důkazu je pevný bod, ale nevyžaduje speciální důkaz. Důkaz Lemmatu funguje stejně pro jedničku jako pro libovolné n.
Používám tu větu o MI, na které jsi mě nachytal a kterou jsem opravil.

Citace
Ono to totiž bez pevného bodu to nejde! Např platí   (a = a - 1) =>  ((a+1) = (a+1) - 1). To ale neznamená, že a = a - 1. Proto je pevný bod pro MI nutnost. Ona i ta věta o transfinitní indukci se pak musí užít s pevným bodem:
http://mathworld.wolfram.com/TransfiniteInduction.html (http://mathworld.wolfram.com/TransfiniteInduction.html)
Ta věta v odkazu není dobře zapsaná: není řečeno, pro jaká a má platit indukční krok 2.=>3.
Pokud pro a>=1, pak je pevný bod 1. potřeba (označím takovou indukci "verze s pevným bodem").
Pokud pro a>=0, pak není bod 1. potřeba (resp. je obsažený v indukčním kroku) (ozn. "verze bez pevného bodu").

Při důkazu verzí bez pevného bodu implikace "(a = a - 1) =>  ((a+1) = (a+1) - 1)" pro a=0 nefunguje, protože a nemá předchůdce. Takže žádný problém.

Mnou uvedená definice (transfinitní) indukce pro přirozená čísla/ordinály odpovídá verzi bez pevného bodu.

Mimochodem, věta v odkazu je věta o transfinitní indukci pro dobře uspořádané množiny, nikoli pro ordinály. Dobře uspořádaná množina nemusí být uspořádaná právě relací náležení, takže ten jednoduchý zápis věty o indukci pomocí relace náležení není pro dobře usp. množiny možný.

Tvůj/můj důkaz

Citace
Citace
tak vidím, že v důkazu nemá P co dělat (P je takto použito v Lemmatu a sám jsi uznal, že pro Lemma indukce není třeba), na jeho místě má být f.
Ach jo. Tak znova.
"Znova"? Až doteď jsem se vyjadřoval k tvému indukčnímu kroku v příspěvku #104 (http://forum.root.cz/index.php?topic=805.msg6446#msg6446). A tam nebylo po f ani památky.
Teprve následující důkaz je formálně (téměř) v pořádku...
Citace
Dokazuji, že P(a) = f(a).
...
Abych T(n) dokázal, tak
1) použiji indukční předpoklad, že f(k) = P(k) pro všechna f(k) v definici f(n) a tedy
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...)
2) použiju Lemma, že min (P(i)+ P(j)...) = P(n)
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...) = P(n)
... až na to, že zapomínáš na jeden detail:

Nemužeš dokazovat, že
P(a) = f(a)
jestliže nevíš, zda f(a) existuje.
Ve skutečnosti dokazuješ
f(a) existuje a P(a) = f(a)

a pro rovnost
f(n) = min (f(i)+ f(j) ....)
musíš využít indukční předpoklad taky.
(ovšem pokud se na f nedíváš jako na funkci definovanou rekurzí, ale jako na funkci definovanou algoritmem, čeká tě ještě práce navíc.)
Citace
Nesouhlasím s tím, že pokud
f(n) = min (f(i)+ f(j) ....)
pak tvrzení
P(n) = f(n) plyne okamžitě Lematu, aniž bys použil MI (popř. postup MI podobný). Pokud nesouhlasíš, tak to formálně dokaž.
Důkaz: Z Lemmatu plyne, že P splňuje náš rekurzivní předpis P(n) = min (P(i)+ P(j) ....). Ale věta o definici rekurzí říká, že taková funkce je jen jedna, tedy P=f.
(Jak už jsem zmiňoval, rekurze je založena na indukci, takže s tou potřebou indukce máš pravdu.)

Edit:
Rozdíl mezi našimi dvěma důkazy:
Já používám větu o definici rekurzí, a ty dokazuješ větu o definici rekurzí pro náš specifický případ.
(:P jako bys zapomínal na úchylku matematiků převádět problémy na dříve vyřešené)



[off-topic][/off-topic]
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: ferren 23. 10. 2010, 15:24:25

tohle tema me docela pobavilo. priznam se,po precteni zadani jsem taky zbrkle naletel a napadlo me to nejtrivialnejsi "temer" idealni reseni zminene prakticky v prvnich odpovedich. ano,pak jsem se zamyslel ano,mame tu NP. zbylych snad 8 stranek jsem jen zbezne proskakal,a mam na vas vsechny par poznamek. predne,puvodni tazatel asi nebude studentik,plni nejake pracovni zadani v e-shopu. suboptimalni reseni funguje v 99% pripadu,navic z praktickeho pohledu se slevova baleni resi procentualne vuci cene za 1 kus.v praci opravdu tezko vzniknou divoke cenove kombinace,kde ten nejtrivialnejsi algoritmus selhava.ani dost dobre v praxi nedochazi k nakupum radove vetsiho mnozstvi nez v tom nejvyhodnejsim balicku,protoze balicky tak nejak reprezentuji REALNE mozne nakupy. navic,zadavatele prace tj. e-shop netrapi,ze sem tam na zakaznikovi o trosku vic vydela, navic pokud je zakaznik vubec schopen poznat,ze mu to navrhlo nevhodnou kombinaci,tak si sam zvoli pro nej kombinaci lepsi. troufam si odhadnout, ze v realnem e-shopu tohle nenastane NIKDY.

takze,nic proti akademickym debatam o algoritmech,ale tohle je presne rozdil v skolnim a praktickem pristupu,a jako majitel e-shopu bych vas vsechny vyhodil ;-) kanon na vrabce bych v zivote nezaplatil....

Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 23. 10. 2010, 15:45:53
 ::) Je vidět, že jsi 8 stránek jen běžně proskákal, a tudíž nevíš o čem mluvíš. Optimální řešení je mnohem jednodušší než suboptimální.
(a aby bylo jasno: akademické debaty nejsou o tom, co je nejlepší řešení, ale jak formálně dokázat správnost tohoto nejlepšího řešení)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: ferren 23. 10. 2010, 15:54:30
:-) jednodussi? mas pravdu,preskakoval jsem,ale co jsem nepreskocil,byly Tve prvni prispevky,zvlast jsem nepreskocil ten,kde uznavas ze nick sedi,ze jsi nad necim den premyslel...i tohle staci k tomu,abych si stale stal za tim uvedenym nejjednodusim resenim a zaverem, co bych udelal kdyz bych byl ja ten co takoveho developera plati ;-)))))) nic ve zlem.jednoduche reseni neni o cistote algoritmu,jeho slozitosti a delce kodu,ale o case,ktery nad nim clovek stravi...
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Jaromír 24. 10. 2010, 03:46:20
Koukám, že jediný funkční (a tudíž i nejlepší) algoritmus jsem tu dal já. Jinak ostatní tady o tom jenom tlachají...
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 24. 10. 2010, 20:36:08
Citace
Já používám větu o definici rekurzi....
Mě se zdá, že v každym postu používáš něco jinýho. Nejdřív si tvrdil, že používáš  matematickou indukci bez pevnýho bodu, pak zas že indukci nepoužíváš vůbec, pak užíváš omezenou transfinitní indukci, potom zas větu o definici funkce rekurzí.

Jinak ano, pomocí věty o definici rekurzí ten algoritmus jde dokázat taky (a je to vcelku hezký důkaz, asi i kratší než s použitím MI). Pro korektnost tam zas musíš definovat dobré uspořádání - takže taky je tam ještě nějaká práce, kterou neděláš u MI. A btw. to uspořádání Ti definuje nejmenší člen a ten je pak pevným bodem.
Nicméně je to jiný důkaz a tedy nevypovídá nic o tom, zdali pro důkaz pomocí MI potřebuješ pevný bod či nikoli.

Citace
Při důkazu verzí bez pevného bodu implikace "(a = a - 1) =>  ((a+1) = (a+1) - 1)" pro a=0 nefunguje, protože a nemá předchůdce. Takže žádný problém.
A co když to tvrdím na celých číslech? Tam každé číslo předchůdce má... Naopak právě to, že na celých číslech to nefunguje je důkaz toho, že potřebuješ nějaký pevný bod. Celá indukce funguje tak, že vezmeš nějakej pevnej bod, kde to tvrzení platí a pomocí indukčního kroku infikuješ platností ostatní.

 To, že teorie množin popisuje aritmetiku ještě neznamená, že se při používání výsledků TEMNA nemusí dbát jisté opatrnosti na to, jak se aplikuje. Proto je imho jednodušší dokazovat pomocí MI, kde máš větu s naprosto jasným mustrem důkazu.

TI říká pouze něco o vlastnostech přirozených čísel, MI rozvnou o tvrzeních, aplikovaných na ně. Takže pokud chceš užít TI (respektive navíc omezenou na přirozená čísla, což si vyžádá další práci navíc) musíš kus toho, co je ve větě o MI již dokázaný dokázat ručně. V rámci toho se Ti může stát, že dokážeš i platnost tvrzení v pevném bodě (ten tam opět je, ani TI by nefungovala bez pevného bodu - tzn. bez tvrzení, P(n_0), které lze dokázat bez předpokladu P(n)).
 To však neznamená, že Ti to ušetří práci, ani že tam ten pevný bod není (právě předpoklad uspořádání množiny je v podstatě ekvivalentní předpokladu existence pevného bodu).

PS: Jinak existenci f ověřovat nemusím, protože P existuje, dokážu-li tedy ekvivalenci P a f, musí existovat i f.

jaromir: :-) :-) Ne, tys jen postoval myšlenkově nejjednodušší algoritmus kterej je pomalej a tak ostatní nezajímá.... Ale jasně, seš king...

ferren: rozdíl v akademickém a praktickém přístupu je v tom, že zatímco akademici se dokážou bavit, tak "praktici" všechno počítaj na peníze? Sice nejsem čistej akademik, ale jestli to tak je, tak se na ten doktorát určitě přihlásim...
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 24. 10. 2010, 21:50:31
Mě se zdá, že v každym postu používáš něco jinýho. Nejdřív si tvrdil, že používáš  matematickou indukci bez pevnýho bodu, pak zas že indukci nepoužíváš vůbec, pak užíváš omezenou transfinitní indukci, potom zas větu o definici funkce rekurzí.
Říkal jsem, že na důkaz Lemmatu nepotřebuješ indukci. A ty tři ostatní věci jsou plus minus jedno a to samé.

Citace
A co když to tvrdím na celých číslech? Tam každé číslo předchůdce má...
Tvrdit to můžeš, ale nemůžeš to dokazovat žádnou indukcí, protože ta funguje pouze pro dobře uspořádané množiny.
Dobře uspořádané množiny samozřejmě počátek (=pevný bod) vždy mají. Jiná věc je, že pro tento počátek není vždy nutné provádět separátní důkaz.

Citace
TI říká pouze něco o vlastnostech přirozených čísel, MI rozvnou o tvrzeních, aplikovaných na ně. Takže pokud chceš užít TI (respektive navíc omezenou na přirozená čísla, což si vyžádá další práci navíc)
Ale já nepoužívám TI, používám MI. Jenom jsem mimochodem konstatoval, že
MI = TI omezená na přirozená čísla

Jinak TI a MI říká to samé, jenom to říká o jiné množině. "Říkat něco o tvrzeních, aplikovaných na přirozená čísla" to není součást indukce, to je jenom přílepek:
MI indukce (ve smyslu teorie množin) říká, že má-li M, která je podmnožinou N, nějakou vlastnost, je pak rovna celému N. Nic víc.
Při řešení problému pak definujeme M ={n z N; tvrzení T(n) platí}. a použijeme MI.
(a přijde mi odvážné říkat minulému řádku "práce navíc")

Citace
PS: Jinak existenci f ověřovat nemusím, protože P existuje, dokážu-li tedy ekvivalenci P a f, musí existovat i f.
To bys ale nesměl začít psát důkaz rovností
f(n) = min (f(i)+ f(j) ....)
Musel bys začít z druhé strany P(n)=...
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: TomK 25. 10. 2010, 00:10:04
Indukce bez pevného bodu neobstojí. Stačí ten příklad jen trochu upravit, aby byl korektně definován i pro 0:
Dokazuju tvrzení: a = a+1
Indukční krok, tj. (a = a + 1) =>  ((a+1) = (a+1) + 1), je triviální dokázat, přesto je snad zřejmé, že uvedené tvrzení neplatí.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 25. 10. 2010, 00:19:07
Citace
Říkal jsem, že na důkaz Lemmatu nepotřebuješ indukci.
Nikoli. Říkal jsi:
Citace
Pokud je f(n) definována korektně, P(n) = f(n) plyne okamžitě z Lemmatu, na to indukci nepotřebuješ.
Což jsi se pak snažil obhájit tím, že použiješ větu o konstrukci rekurzí. Která se sama dokazuje indukcí....

Citace
Jinak TI a MI říká to samé, jenom to říká o jiné množině.
IMHO v teorii množin se o matematické indukci v podstatě nemluví. Přirozený čísla jako objekt v TEMNU je vcelku nezajímavej objekt a TEMNO se mj. na zkoumání spočetnejch věcí moc nehodí (byť je na něco nutná). V TEMNU se používá transfinitní indukce, protože ta se týká toho, čemu se TEMNO mj. věnuje hlavně - nekonečnejm množinám. Je možný, že někdo MI v rámci teorie množin definuje, to je pak ale nejspíše z didaktickejch důvodů, aby člověku nepřišla TI tak divná.
S google jsem našel všehovšudy jedinou zmíňku - a to pouze ve formě s pevným bodem, v podstatě parafrázi věty o matematický indukci
http://ufal.mff.cuni.cz/~pajas/vyuka/logika_temno_2x2.pdf (http://ufal.mff.cuni.cz/%7Epajas/vyuka/logika_temno_2x2.pdf)

Když se řekne matematická indukce, tak se tím prostě myslí věta o matematický indukci (respektive o slabym a silnym principu). Je to jak s tou složitostí - můžeš si vymejšlet vlastní definice a názvosloví - pak ale budeš mluvit o koze a ostatní o voze.

Citace
Tvrdit to můžeš, ale nemůžeš to dokazovat žádnou indukcí, protože ta funguje pouze pro dobře uspořádané množiny.
Dík TomK, opravils mi to perfektně :-).

Navíc MI (z věty o slabém principu) je definovaná pro n ze Z, takže jsou dvě možnosti:
a) buďto MI v analýze je něco jinýho než MI v temnu (což je zjevně blbost)
b) nebo MI v temnu vyžaduje pevný bod.

Citace
Při řešení problému pak definujeme M ={n z N; tvrzení T(n) platí}. A použijeme MI
Co to znamená a použijeme MI. To znamená ověřit předpoklady. Předpoklad pak je, že je-li x podmnožinou a ordinálem (tos tam taky zapoměl, bez toho to imho nejde), pak je i prvkem. To celé bys měl ověřit prostředky TEMNA (axiomy, množiny, ne žádný čísla a podobný "výdobytky civilizace"). Vopruz.
Ty bys prostě chtěl mixovat "vágnost" aplikovaný matematiky s tím největším formalismem, co snad existuje. Promiň, ale vznikne mišmaš.

Citace
To bys ale nesměl začít psát důkaz rovností
f(n) = min (f(i)+ f(j) ....)
Musel bys začít z druhé strany P(n)=...
Proč ne? Indukcí mám přeci zajištěnou existenci f(i) a f(j). Ten důkaz zároveň dokazuje existenci i rovnost.
Nikde nepoužívám nic, co by předem nebylo dobře definovaný - vždyť sáms psal, že v podstatě trochu kopíruju větu o konstrukci rekurzí.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 26. 10. 2010, 22:27:45
Dokazuju tvrzení: a = a+1
Indukční krok, tj. (a = a + 1) =>  ((a+1) = (a+1) + 1), je triviální dokázat, přesto je snad zřejmé, že uvedené tvrzení neplatí.
To je ale to samé v bledě modrém. Matyáš napsal indukční krok pro a, tohle je stejný indukční krok, jenom zapsaný pro a+1. Pro a+1=0 nelze  důkaz použít, protože a neexistuje.

Důkaz indukcí "bez pevného bodu" vyžaduje abys ukázal
platí-li tvrzení pro všechny předchůdce a, platí i pro a.
Pro a=0 to znamená, že důkaz musí fungovat, aniž by bylo možné se opřít o jakéhokoli předchůdce.

IMHO v teorii množin se o matematické indukci v podstatě nemluví. Přirozený čísla jako objekt v TEMNU je vcelku nezajímavej objekt
O přirozených číslech a MI se mluvit musí, jinak by teorie množin nemohla sloužit jako základ ostatních matematických oborů.
Mimochodem, někdy někde jsem viděl Godel-Bernaysovu teorii množin, včetně pasáže o přirozených číslech a definice MI (včetně "Fin(x)",  na které jsem o pár příspěvků výše zapomněl).

Citace
Navíc MI (z věty o slabém principu) je definovaná pro n ze Z, takže jsou dvě možnosti:
a) buďto MI v analýze je něco jinýho než MI v temnu (což je zjevně blbost)
b) nebo MI v temnu vyžaduje pevný bod.
MI definovaná pro celá čísla? Tomu nerozumím.
a) souhlasím, nevidím žádný rozdíl, kromě toho, že v analýze se zřejmě vždy pracuje s konstrukcí M ={n z N; tvrzení T(n) platí}
a indukce "s pevným bodem"-"bez pevného bodu" jsou jak v MA tak v TeMnu, navíc jsou obě indukce v podstatě jedno a to samé
b) chceš snad říct, že ta věta nefunguje, ani po opravách?

Citace
Co to znamená a použijeme MI. To znamená ověřit předpoklady. Předpoklad pak je, že je-li x podmnožinou a ordinálem (tos tam taky zapoměl, bez toho to imho nejde), pak je i prvkem. To celé bys měl ověřit prostředky TEMNA (axiomy, množiny, ne žádný čísla a podobný "výdobytky civilizace"). Vopruz.
Máš pravdu, zapomněl jsem, že x má být ordinál.

Číslo 2 nebo pojmy "funkce", "matematická indukce" jsou nějak teorií množin definované. Jakmile je definuji, mohu je pak normálně používat, bez axiomů.
Teorie množin není žádná uzavřená exotická část matematiky, naopak se "spojitě" rozvětvuje do ostatních disciplín matematiky.

A v každém matematickém odvětví, ať je to teorie množin nebo analýza nebo cokoli jiného, mohu dělat důkazy čistě formální jen jako posloupnost formulí na základě výrokové a predikátové logiky (vopruz), nebo jako mix přirozeného jazyka a matematických symbolů (což je nejběžnější), ale i zcela bez matematických symbolů.
Takže když řeknu
matematická indukce říká: platí-li, že (jsou-li v podmnožině přirozených čísel všichni předchůdci n (ve smyslu uspořádání relací náležení), je tam také n), jsou v této podmnožině všechna přirozená čísla
tak je to taky teorie množin, i když pouze neformální.

Citace
Citace
To bys ale nesměl začít psát důkaz rovností
f(n) = min (f(i)+ f(j) ....)
Musel bys začít z druhé strany P(n)=...
Proč ne? Indukcí mám přeci zajištěnou existenci f(i) a f(j). Ten důkaz zároveň dokazuje existenci i rovnost.
Nikde nepoužívám nic, co by předem nebylo dobře definovaný - vždyť sáms psal, že v podstatě trochu kopíruju větu o konstrukci rekurzí.
Napsal jsem hloupost, je jedno z které strany začneš. V každém případě f nemůžeš používat, pokud nevíš, jestli existuje jako celek: existence f(i), f(j) nestačí.

To znamená, že formálně je to takhle: rovnicí
f(n)=min (f(i)+ f(j) ....)=min (P(i)+ P(j) ....)=P(n)
nedokazuješ
P=f
nýbrž
jestliže f existuje, pak P=f.
(pozn. důkaz tohoto tvrzení odpovídá důkazu jednoznačnosti funkce definované rekurzí)

K tomu musíš dokázat, že f existuje, ale to je jasné, stačí do předpisu dosadit P.
(
pozn. naopak u rekurze je důkaz existence funkce složitější. Takže není tak úplně pravda, jak jsem říkal, že kopíruješ důkaz věty o definici rekurzí.

Jenomže tvůj důkaz se rekurzi (resp. existenční části důkazu věty o definici rekurzí) stejně nevyhne:
Máš funkci definovanou předpisem na základě svých vlastních hodnot v jiných bodech. Víš sice, že existuje právě jedna funkce daná předpisem, ale nevíš, jestli lze na základě toho předpisu sestavit algoritmus, který funkci vyčíslí.
Zřejmě platí následující tvrzení:
jestliže je předpis rekurzivní, tj. jestliže pro každé n je hodnota funkce určena na základě hodnot předchůdců, lze na základě tohoto předpisu algoritmus sestavit.
Důkaz tohoto tvrzení bude zřejmě analogický s existenční částí důkazu věty o definici rekurzí.

Takže i když se zkusíš vyhnout rekurzi, použiješ myšlenky jak existenční tak jednoznačnostní části důkazu věty o rekurzi.
)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: TomK 26. 10. 2010, 23:53:08
To je ale to samé v bledě modrém. Matyáš napsal indukční krok pro a, tohle je stejný indukční krok, jenom zapsaný pro a+1. Pro a+1=0 nelze  důkaz použít, protože a neexistuje.

Je to v podstatě to samé. Ale tvrdím, že ta implikace platí pro všechna přirozená nebo i celá čísla. Konkrétně pro nulu vypadá takto: (0)+1=(0) => (0+1)+1=(0+1), opět lze i jednoduše dokázat.

Důkaz indukcí "bez pevného bodu" vyžaduje abys ukázal
platí-li tvrzení pro všechny předchůdce a, platí i pro a.
Pro a=0 to znamená, že důkaz musí fungovat, aniž by bylo možné se opřít o jakéhokoli předchůdce.
S tímhle souhlasím. Ale platí-li to pro 0 bez jakýchkoliv předpokladů, dělá to z nuly to, co je v této diskuzi označováno jako pevný bod (nejsem si jistý, jestli korektně, zatím jsem se s touto terminologií nesetkal, ale možná jde jen o mou neznalost). Možná je celý spor ohledně indukce jen o nejasné definici pevného bodu.

Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 27. 10. 2010, 01:08:35
S tímhle souhlasím. Ale platí-li to pro 0 bez jakýchkoliv předpokladů, dělá to z nuly to, co je v této diskuzi označováno jako pevný bod (nejsem si jistý, jestli korektně, zatím jsem se s touto terminologií nesetkal, ale možná jde jen o mou neznalost).
Ano, to jsem říkal. Pevný bod je tam vždy, jde jen o to, jestli je třeba pro nulu/počátek/pevný bod dělat zvlášť důkaz.
Pokud indukční krok funguje od počátku (nic=>0), tak to není třeba, pokud až od počátku+1 (0=>1), je třeba udělat zvlášť důkaz pro počátek.
Jinak terminologii si tu asi děláme vlastní...
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 27. 10. 2010, 15:22:06
Terminologii si tu právě děláš vlastní ty. Jediný co já používám "nestandardně" je termín pevný bod - nikdo nikdy co jsem na MFF zažil jeho potřebu nezpochybňoval, takže myslím nějaký extra název nemá - všude se bere jako fakt.

Citace
Pro a=0 to znamená, že důkaz musí fungovat, aniž by bylo možné se opřít o jakéhokoli předchůdce.
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.

Citace
MI definovaná pro celá čísla? Tomu nerozumím.
No indukci můžeš použít i pro všechna záporná čísla, pro čísla větší než -10 atd....  Co je na tom k nechápání? Jediné co potřebuješ je platnost pro n0 a indukční krok.

Citace
Teorie množin není žádná uzavřená exotická část matematiky,
Která teorie množin? ZFC? Vopěnkova alternativní? Goldstein-bernsteinova? A s jakým modelem?

Citace
naopak se "spojitě" rozvětvuje do ostatních disciplín matematiky.
Nikoli. Např. analýza má svoje vlastní axiomy a pracuje pozue s nimi. TEMNO se snaží vytvořit logické teorie a modely, které by splňovali axiomy této teorie, není však pravda, že TEMNO = Analýza.
V TEMNU často jdou dokázat tvrzení, která v analýze nejdou - a v každém temnu a v každém modelu jiná tvrzení!

Citace
Číslo 2 nebo pojmy "funkce", "matematická indukce" jsou nějak teorií množin definované.
V každé teorii množin jsou definovány jinak, mají třeba i jiný model, popř. mají víc možných modelů, jdou pro ně dokázat různě silná tvrzení... Takže jestli chceš použít TEMNO, tak bys nejdříve měl říct kteoru vlastně teorii používáš a co pro ni platí.

Citace
Jakmile je definuji, mohu je pak normálně používat, bez axiomů.
Jo, ale furt sou to objekty TEMNA. Tzn. např. věta o MI pracuje s podmnožinou. Tzn. abys byl korektní, tak to musíš dokázat pro všechny ordinální konečné podmnožiny dané množiny (jestli Ti je od pohledu jasné, že veškeré ordinální podmnožiny N musí být přirozená čísla, tak mě teda ne - existují i pěkně divoký modely ZFC TEMNA. Pozor, netvrdim, že to tak neni, jen že to není "zřejmé"). Atd. postě přirozený číslo v ZFC není až tak "jednoduchá věc" jako v analýze.

Používat na důkaz algoritmu TEMNO je jako používat v rámci pascalu strojovej kód. Jde to, ale je to zdlouhavější, nečitelnější, musíš se omezit na jednu konkrétní architekturu (rozuměj teorii množin) a explicitně uvést kterou. Za to můžeš dostat výsledky, které by s packalem nešly. Ale psát tak věci, co se dají napsat v pascalu, je blbina a nikdo to nedělá.
 
Citace
a) souhlasím, nevidím žádný rozdíl, kromě toho, že v analýze se zřejmě vždy pracuje s konstrukcí M ={n z N; tvrzení T(n) platí}
No právě takhle se v MA s MI nepracuje. V MA se pracuje s větou o slabíém či silném principu MI, které jsou založeny tuším na axiomech indukce.
MA je postavená na svejch axiomech o číslech, takže něco jako relace náležení ordinálů a z ní vyplývající princip indukce se tam prostě nepoužívá, má vlastní princip indukce a nějaká množina n, pro který platí daný tvrzení se tam prostě nekonstruuje. Nebo jsem to alespoň za svejch x let na mff nikdy nikoho neviděl dělat.

Citace
A v každém matematickém odvětví, ať je to teorie množin nebo analýza nebo cokoli jiného, mohu dělat důkazy... ....tak je to taky teorie množin, i když pouze neformální.
Ano, jde programovat eshop v strojovém kódu. Já bych to nedělal.
Stejně tak jde si nad assemblerem napsat vlastní "hezčí" jazyk a ten používat. Zaprvý je to ztráta času a za druhý Ti nikdo nebude rozumět.

Citace
Mimochodem, někdy někde jsem viděl Godel-Bernaysovu teorii množin, včetně pasáže o přirozených číslech a definice MI (včetně "Fin(x)",  na které jsem o pár příspěvků výše zapomněl).
A už je to tady - tak používáme ZFC nebo GB? A co axiom výběru? Ano nebo ne? A jaký model teda používáme? To všechno musíš říct, aby byl tvůj důkaz  korektní a vůbec srozumitelnej....

Citace
Napsal jsem hloupost, je jedno z které strany začneš. V každém případě f nemůžeš
používat, pokud nevíš, jestli existuje jako celek: existence f(i), f(j) nestačí.
Takže f nemůžu ani definovat, protože k její definici musím prostě použít musím?
Nebo jsou povolené a nepovolené užití f? Zase báťuška?
Koukni se někde na důkaz věty o konstrukci rekurzí. Kupodivu v důkazu, že existuje f ji používaj...
Je to jako s řešením kvadratický rovnice. Taky ji řešíš, i když třeba nemá řešení. Tzn. děláš s ní úpravy, aniž bys bys věděl, že existuje řešení, když třeba z obou stran odečteš x, tak to x vůbec nemusí existovat. Ale platí, že řešení rovnice před úpravou - existuje-li - je shodné s řešením po úpravě a naopak.

Citace
Zřejmě platí následující tvrzení:
jestliže je předpis rekurzivní, tj. jestliže pro každé n je hodnota funkce určena na základě hodnot předchůdců, lze na základě tohoto předpisu algoritmus sestavit.
Právě si napsal větu o konstrukci rekurzí. A ta kupodivu platí. (algoritmus je funkce, viz věta o ekvivalenci TS a částečně rekurzivních funkcí).
Navíc zaměňuješ "existenci" s definičním oborem (repektive množinou vstupů, na kterých se TS zastaví). Pokud je předpis fce daný, jde algoritmus sestavit vždy, akorát ne vždy se zastaví.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 28. 10. 2010, 14:39:04
Indukce

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íš
Např. tvůj důkaz
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)

Matematické teorie

Citace
Která teorie množin? ZFC? Vopěnkova alternativní? Goldstein-bernsteinova? A s jakým modelem?
...
A už je to tady - tak používáme ZFC nebo GB? A co axiom výběru? Ano nebo ne? To všechno musíš říct, aby byl tvůj důkaz  korektní a vůbec srozumitelnej...
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 úroveň axiomů jsme se tu v debatě nedostali, takže je jedno, z které z těch dvou teorií vycházíme, a axiom výběru jsme nepotřebovali, takže nemusíme řešit, jestli jej povolujeme nebo ne.

Citace
Jo, ale furt sou to objekty TEMNA. Tzn. např. věta o MI pracuje s podmnožinou. Tzn. abys byl korektní, tak to musíš dokázat pro všechny ordinální konečné podmnožiny dané množiny.
...
Atd. postě přirozený číslo v ZFC není až tak "jednoduchá věc" jako v analýze.
Indukci v teorii množin lze zapsat jak pomocí podmnožin, tak pomocí relace < (sám jsi uváděl odkaz na takovou definici), a pořád je to indukce a teorie množin.
Relaci < musím nejprve definovat, ale jakmile to udělám, je to stejné < jako v analýze.
(Mimochodem i relaci podmnožina musím nejprve definovat)
Jakmile odvodím příslušné vlastnosti přirozených čísel a definuji 2 = {0,{0}}, je dvojka stejná dvojka jako v analýze.

Citace
MA je postavená na svejch axiomech o číslech, takže něco jako relace náležení ordinálů a z ní vyplývající princip indukce se tam prostě nepoužívá, má vlastní princip indukce a nějaká množina n, pro který platí daný tvrzení se tam prostě nekonstruuje.
...
Nikoli. Např. analýza má svoje vlastní axiomy a pracuje pozue s nimi. ...
V TEMNU často jdou dokázat tvrzení, která v analýze nejdou - a v každém temnu a v každém modelu jiná tvrzení!
(aby nedošlo znovu k nedorozumění, mluvím o stále o GB/ZFC:)

Rád se nechám poučit. Jaké vlastní axiomy má MA? (Vím, že termín "axiom" se občas používá v rámci definic, ale to nejsou skutečné axiomy.)
Já chápu analýzu jako čistou nadstavbu nad teorií množin, to znamená pouze jako definice a věty. (A upřímně řečeno o některých definicích/větách ani nevím, jestli ještě spadají do teorie množin nebo jinam. Např. definici reálných čísel jsem viděl jak v teorii množin tak v analýze.)

A zajímal by mě příklad tvrzení, které nelze dokázat v analýze, ale v teorii množin ano.

Důkazy

Citace
Takže f nemůžu ani definovat, protože k její definici musím prostě použít musím?
Nebo jsou povolené a nepovolené užití f? Zase báťuška?
Říkají to základní matematické principy. f jsi definoval tak, že nevíš, zda existuje.
V důkazu můžeš pracovat pouze s existujícími objekty. Pokud nevíš jestli objekt existuje, musíš si pomoci předpokladem jeho existence.

Když řešíš rovnici, tak vyjdeš z předpokladu, že existuje řešení x a odvodíš, že pak x=a. Tím jsi ukázal, že a je jediným řešením, které připadá v úvahu, ale ne že je řešením, to musíš ještě ověřit.

Jestli si myslíš, že se někde v důkazu věty o konstrukci rekurzí používá f, aniž by se vědělo, zda existuje, tak mi to místo ukaž.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: branchman1 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.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 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".
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 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 (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íš.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: slowthinker 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 (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.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 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??
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Koly 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...
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 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 :-)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Michal Illich 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.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: vandrovnik 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?
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 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ší).
Název: Řešení
Přispěvatel: Paja 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
   
 
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 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 :-)¨)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Paja 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.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 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í :-)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Paja 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.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 05. 12. 2010, 00:53:04
Tak, jak je definována složitost v NP úplnosti (pokud bude vstup zadanej efektivně), tak to polynomiální nebude. Viz předchozí post.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Paja 05. 12. 2010, 01:06:59
Proc by nebylo ? Ted to je O((n+max(pocet_v_baleni))^2)

Pridavam predelany kod ktery respektuje vyse zminenou diskuzi

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
  // cena za nejmensi baleni - budu ji potrebovat
  end($baleni);
  $nejmensibalenicena=current($baleni)*key($baleni);
  if (!isset($baleni[1])) {
    if ($muzuvyhazovat) {
      // naplnim baleni mensi nez nejmensi s tim ze se musi vyhodit nejake kusy
      for ($i=key($baleni)-1;$i>=1;$i--) {
        $baleni[$i]=$nejmensibalenicena;
      }
    } else {
      // zkontroluju zda to muzu vubec dodat z dannych baleni
      $deleno=false;
      foreach ($baleni as $pocet=>$tmp)
        if (!$deleno and ($ks % $pocet==0)) $deleno=true;
      if (!$deleno) die("pocet neni mozno poskladat z moznych baleni");
    } 
  } 
  // 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;
  // jestli muzu vyhazovat, pridam jeste nejvetsi baleni k vypoctu
  reset($baleni);
  if ($muzuvyhazovat) $n+=current($baleni);

  /* 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.
  if (isset($baleni[1])) {
    $ceny[1]["cena"]=$baleni[1];
  } else {
    $ceny[1]["cena"]=$nejmensibalenicena*2;
  } 
  // 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ázev: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 05. 12. 2010, 11:21:28
T a k  j e š t ě  j e d n o u  a  p o m a l u .  : - )

Složitost v NP úplnosti je (trochu zjednodušuji) definována jako složitost na základě BITOVÉ délky vstupu.
n na vstupu bude efektivně kódováno pomocí m=log(n) bitů. Takže zanedbám-li počet
balení, na kterém to roste pomaleji, výsledná složitost je O(exp(m)^2).

edit: oprava log za exp, nějak mi to uteklo :-)
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Paja 06. 12. 2010, 07:35:56
To mi hlava nebere.
Dycky nas ucili, ze treba u bubblesortu je to O(n^2). N je pocet prvku ktere se maji setridit. Quicksort je O(n*log n). Atd ...

Takze pokud je vstup n = pocet_hledanych_ks +  pocet_v_nejvetsim_baleni (nejhorsi pripad) a algoritmus provede maximalne n (inicializace) + n^2/4 (hledani variant) + 2*n (ziskani vysledku vypoctu) kroku je slozitost O(n^2)

Tudiz se jedna po polynomialni problem - narust slozitosti lze vyjadrit polynomem.

Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Paja 06. 12. 2010, 07:49:26
Jeste bych dodal ze opravdu nas zajima zavislost casu vypoctu na poctu objednanych ks.
Ne na logaritmu poctu objednanych ks.
Predstavte si kolik vlaku by jste potreboval pro odvoz baleni hmotnosti 1kg a objemu 1l pri poctu n, kdy je logaritmus o zakladu 2 z n je 64 ....
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 07. 12. 2010, 14:20:31
Jak je definovaná složitost jinde je pooměrně irelevantní - pokud se bavíme o NP úplnosti, tak prostě musíme brát složitost tak, jak je definovaná v NP úplnosti.

Jinak problém téí naivní definice je v tom, že to není deinice. Ono podle toho bys moh tvrdit, že složitost je lineární - jde vyjádřit lineární závislostí na počtu nutných prohození prvků aby to bylo setříděné.
Jednoduše řečeno, jiný relevantní údaj než délka vstupu, který bybyl společný pro všechny algoritmy nemáš.

Btw. Složitost bublesortu je i podle definice v NP úplnosti O(n^2), protože délka vstupu je úměrná počtu prvků.

Co jsi chtěl vyjádřit tím vblakem už vůbec nechápu, zaprve výpočet a převoz zboží je jaksi něco jiného, zadruhé pokud bych připustil nějakou analogii, tak na vstupu algoritmu převez
n balíků nemůže být počet balíků, ale ty samotné balíky, takže ne log n prvků, ale n prvků.

Pokud bych měl počet těch balíků, tak jediné co mohu převést je zas jen ten počet balík. A ten jde vyjádřit opravdu v log n bitů, takže pokud bych uměl zabalit jeden bit do jedné krabice, tak bych opravdu musel převést pouze log n krabic.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Paja 11. 12. 2010, 21:20:37
No proste si predstav, ze delka vstupu v tomto pripade je umerna poctu objednanych ks.

Jina interpretace delky vstupu je iracionalni. Coz jsem popsal variaci na tema sachovnice a zrnka ryze.

Kdyby jsi pouzil stejny pristup jako k tomuto pripadu i k bubblesortu, mohl by jsi prohlasit, ze te zajima zavislost na nizsi z hodnot pocet trizenych cisel, logaritmus z maximalni trizene hodnoty.

Pokud si chces definovat slozitost algoritmu vyse uvedeneho prikladu, jako zavislost na logaritmu poctu kusu, je to tva volba. Ja bych to takto nikdy nedefinoval, protoze to nema zadny smysl.

A za pravdu mi da to, ze pro rozumne priklady vypoctu (tedy fyzikalne realizovatelne dodavky), se to da spocitat v malem case. Na rozdil od obchodniho cestujiciho. U ktereho pro 100 zastavek nebudes schopen spocitat nejlepsi variantu v rozumnem case.

Coz se presne shoduje s definici NP.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 12. 12. 2010, 10:44:25
Citace
No proste si predstav, ze delka vstupu v tomto pripade je umerna poctu objednanych ks.
Ano, pokud by byla, tak by to platilo. Ale vstup by byl velmi neefektivní. Když se baví lidé o algoritmu bez zadaného vstupu, bere se za samozřejmé, že je vstup optimální.

Stejnětak bych mohl tvrdit, že POC není NP, protože můžu vzít jeho vstup, doplnit 2^N bytama redundance a kontrolních součtů a mám z toho polynomiální algoritmus.


Citace
Na rozdil od obchodniho cestujiciho. U ktereho pro 100 zastavek...
Ano, ale tam musí být každá zastávka ve vstupu jako samostatnej kus dat se vzdálenostma od ostatních. Nejde napsat vyřeš POC, který má sto zastávek. To je právě ten rozdíl.

Citace
Coz se presne shoduje s definici NP.
Neshoduje. Prosím, přečti si definici NP. Tam je složitost prostě definovaná tak jak je. Nemá smysl se bavit o NP, když nevíš, jak je definovaná.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Paja 20. 12. 2010, 23:39:49
Myslim ze michas pojmy.

Definice slozitosti:
N se většinou myslí velikost vstupních dat. Treba pro trizeni je to pocet prvku. V nasem pripadu to je pocet ks.
Pojem asymptotická složitost znamená, že nás zajímá chování funkce pro velká N. Treba bublesort je O(n^2), quicksort O(n*log n)
Je zrejme ze slozitost vyse uvedeneho algoritmu je O(n^2).

Definice P uloh
Třída P obsahuje problémy, které se dají řešit tak, že není potřeba víc kroků, než kolik se dá vyjádřit polynomem. A n^2 je polynom. Dokonce maly polynom - jen druheho stupne.
Uloha je tedy ze tridy P.

Prozatim se predpoklada ze P je podmnozina NP. A nikdo zatim nedokazal ze P=NP.
Název: Re: Optimální algoritmus výpočtu
Přispěvatel: Logik 21. 12. 2010, 02:49:46
To cos napsal není ani definice složitosti (v NP úplnosti), ani definice třídy P. Jestli nevěříš, tak běž na MFF na přednášku Úvod do složitosti a NP úplnosti, nebo si přečti o NP úplnosti nějakou knihu.

PS: http://mj.ucw.cz/vyuka/0910/ads2/11-np.pdf
úloha batoh optimalizace je v podsatatě to samé a je tady uvedena mezi NP-úplnými úlohami.

PPS: To, cos napsal, je parafráze definice asymptotické složitosti. Ta se hodí pro sledování složitosti algoritmů řešících konkrétní problém v závislosti na daném kritériu. Nejde však použít k srovnání různých algoritmů, protože nemusí mít shodné kritérium.... tedy, jedno shodné kritérium dva libovolné algoritmy mají: délku vstupu....