Optimální algoritmus výpočtu

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


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

Logik

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

jaromír

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

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


Ghost

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

Logik

  • *****
  • 951
    • Zobrazit profil
    • E-mail
Re: Optimální algoritmus výpočtu
« Odpověď #96 kdy: 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ů?
« Poslední změna: 14. 10. 2010, 12:02:32 od Matyáš Novák »

jaromír

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

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

Ghost

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

jary

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

Ghost

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

Logik

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

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

Logik

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