Optimální algoritmus výpočtu

Re: Optimální algoritmus výpočtu
« Odpověď #105 kdy: 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é }
« Poslední změna: 14. 10. 2010, 19:17:30 od slowthinker »
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."


Logik

  • *****
  • 962
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #106 kdy: 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í.
« Poslední změna: 14. 10. 2010, 20:54:16 od Matyáš Novák »

Re: Optimální algoritmus výpočtu
« Odpověď #107 kdy: 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.

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í.
« Poslední změna: 14. 10. 2010, 22:25:56 od slowthinker »
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

Logik

  • *****
  • 962
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #108 kdy: 14. 10. 2010, 23:03:07 »
Citace
Najdi si "complete induction" v 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?
« Poslední změna: 14. 10. 2010, 23:58:06 od Matyáš Novák »

jaromír

Re: Optimální algoritmus výpočtu
« Odpověď #109 kdy: 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.






jaromír

Re: Optimální algoritmus výpočtu
« Odpověď #110 kdy: 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á.



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ý.



jaromír

Re: Optimální algoritmus výpočtu
« Odpověď #111 kdy: 14. 10. 2010, 23:59:27 »
Oprava: cena s přibývajícími řádky stoupá.

Logik

  • *****
  • 962
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #112 kdy: 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?

jaromír

Re: Optimální algoritmus výpočtu
« Odpověď #113 kdy: 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...


Logik

  • *****
  • 962
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #114 kdy: 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 :-)

Re: Optimální algoritmus výpočtu
« Odpověď #115 kdy: 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é }
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

Logik

  • *****
  • 962
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #116 kdy: 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.
« Poslední změna: 17. 10. 2010, 19:14:16 od Matyáš Novák »

Re: Optimální algoritmus výpočtu
« Odpověď #117 kdy: 18. 10. 2010, 22:45:31 »
[slovíčkaření]
  • V tom slovíčkaření si protiřečíš:

    Ty jsi mě napadal, že nemůžu použít tudle indukci a musím použít jinou.
    (pozn. na upřesnění: já říkal "tohle je jiná indukce", ne co musíš použít. Pro mě za mě si použij třeba pouze axiomy teorie množin s Hilbertovskou logikou a nic víc.)
    Jestliže místo jakékoli silné indukce můžeš použít slabou (což je pravda), tak taky místo jakéhokoli důkazu slabou indukcí můžeš použít důkaz, který se bez indukce obejde úplně. A neměl bys tvrdit toto:
    Citace
    K tomu, abys toto tvrzení dokázal tu indukci potřebuješ.
  • Citace
    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
    ;) Habala v tom článku taky říká, že silná indukce existuje, a ty mu to popíráš.
[/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+
« Poslední změna: 19. 10. 2010, 09:43:33 od slowthinker »
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

Logik

  • *****
  • 962
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #118 kdy: 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

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í...



« Poslední změna: 19. 10. 2010, 13:09:05 od Matyáš Novák »

Re: Optimální algoritmus výpočtu
« Odpověď #119 kdy: 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)
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."