Zobrazit příspěvky

Tato sekce Vám umožňuje zobrazit všechny příspěvky tohoto uživatele. Prosím uvědomte si, že můžete vidět příspěvky pouze z oblastí Vám přístupných.


Příspěvky - slowthinker

Stran: 1 ... 33 34 [35] 36
511
Vývoj / Re: Optimální algoritmus výpočtu
« 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í.

512
Vývoj / Re: Optimální algoritmus výpočtu
« 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é }

513
Vývoj / Re: Optimální algoritmus výpočtu
« 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.)

514
Vývoj / Re: Definice časové složitosti
« kdy: 14. 10. 2010, 13:16:16 »
ghost: ty vole, to snad ne  ::)
 :) Doufám, že sis všiml, že celou dobu mluvím velmi spisovně, a že tvůj příspěvek mi patrně způsobil dosti silný otřes.
Tvůj předminulý příspěvek měl jistou informační hodnotu, i když obsahoval vesměs nesporné skutečnosti. Ovšem tvůj poslední příspěvek neměl vůbec žádnou informační hodnotu.
Debatu na dané téma myslím vedeme dost konkrétně, snaž se prosím také odpovídat konkrétně.

515
Vývoj / Re: Optimální algoritmus výpočtu
« 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.?

516
Vývoj / Re: Definice časové složitosti
« kdy: 14. 10. 2010, 12:38:39 »
j.:
Otázek v té debatě zatím vyvstalo hodně, ale i v mých prvních dvou příspěvcích lze nalézt hodně otázek, opravdu je tu musím vypisovat?

  • Je formální definice [1] (link v prvním příspěvku) nějak používána v praxi, nebo má význam jenom pro teoretické úvahy?
  • Jak bys ohodnotil časovou složitost algoritmu pro výpočet faktoriálu, a pro "nakupovací algoritmus"?
  • Má se pro stanovení časové složitosti uvažovat, že "velká čísla na vstupu mají větší objem než malá"? Příklad: výpočet faktoriálu, na vstupu jediné slovo. Mám velikost vstupu počítat tak, že 16 na vstupu má délku 4, a 32 délku 5?

Problem je, ze skustecne nemas teoreticke zazemi ani neovladas terminologii, a proto mas tendenci sklouzavat k naivnim definicim, coz prirozene vede k nepochopeni.
Já si naopak myslím, že k naivním definicím je potřebné sklouzávat (alespoň dokud nebudu vědět o jejich formálním ekvivalentu}, a vysvětlil jsem to už dříve v debatě. Zkusím argumenty shrnout znovu:
1. argument
Formální definice [1] (link v prvním příspěvku), podle které je algoritmus pro faktoriál exponenciální a "nakupovací algoritmus" lineární, nemá dle mého názoru praktický význam.
2. argument
Když argumentaci vezmu trochu obecněji: formální definice [1] nemá praktický význam, protože závisí na tom, jak je zakódovaný vstup. Matyáš Novák sice napsal, že by toto bylo možné vyřešit takto:
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í
jenomže to už se nebude jednat o formální definici (alespoň já si nedovedu představit, jak formálně definovat "nejúspornější vstup").

A mimochodem, naivní definice [2] je používána i v dosti teoretických publikacích (Kučera: Kombinatorické algoritmy.)



Porad se drzis toho, ze jedno cislo = jedno slovo na vstupu, a ze jedna aritmeticka operace nad cislem je provedena v konstatnim case. Diky masivni optimalizaci dnesnich stroju mas v tak v 80% pripadu pravdu, ale ne vzdy, a prave pri analyze chovani algoritmu nad obecnymi vstupy (kdyz cisla nejsou limitovana velikosti slova) se pouziva formalni definice, protoze abstrahuje od hardwarove optimizace, ktera se muze lisit masinu od masiny a vstupu od vstupu.
O hardwarové optimizaci se snad nebavíme: všechny tři definice uvedené v 1. příspěvku abstrahují od hardwarove optimizace.

Číslem myslíš hodnotu vstupující do algoritmu? ( :P nechtěl bys zapracovat na terminologii?). V tom, že hodnoty nejsou limitovány velikostí slova, přece není problém, pokud je každý typ hodnoty reprezentován pevně daným počtem slov.
Změna nastává, pokud jsou hodnoty ukládány do neomezeného počtu slov: představ si algoritmus třídění, kde jednotlivé hodnoty určené ke setřídění nebudou reprezentovány K slovy (K pevné), ale libovolným počtem slov (vstupní hodnoty budou moci být neomezeně velké). Takový algoritmus se bude lišit od svého klasického protějšku, ale nevidím žádný důvod, proč bych měl na měření jeho složitosti potřebovat jinou definici. Je to algoritmus jako každý jiný.

517
Vývoj / Re: Definice časové složitosti
« kdy: 14. 10. 2010, 12:25:46 »
Ghost: no to jsem si všiml, že nevíš co řešíme. Nechceš si debatu nejdřív přečíst, promyslet, a pak teprve reagovat?

518
Vývoj / Re: Optimální algoritmus výpočtu
« 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.

519
Vývoj / Re: Definice časové složitosti
« kdy: 14. 10. 2010, 07:28:40 »
Odpověď na příspěvek Matyáše Nováka:

2) Neřekl jsem, že algoritmus, který by uměl pracovat s libovolně velkým n, je algoritmus složitější a pomalejší asymptoticky. Podstatné na tom mém sdělení je, že se jedná o jiný algoritmus: bude "nafouknutý" o tu "lineární" část, která bude zpracovávat neomezeně velká data.
1) + 4) Teorii algoritmů neumím, ale nemyslím si, že NP třídy a složitost musejí být definovány na Turingových strojích. Turingův stroj, počítač s libovolným přístupem, nebo reálný HW jsou výpočetně ekvivalentní, definice složitosti založené na těchto různých strojích budou také ekvivalentní.
Předpokládám, že i na reálném HW se časová složitost bude definovat podle počtu elementárních operací, nikoli podle doby běhu programu, takže věci jako branch prediction nás nezajímají.
3) Co má být jako omezeno při fixním zápisu vstupních dat? Počet slov na vstupu je vždy neomezený.

Citace
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.
Přibližování "nějaké veličiny"?? Tak moment, když jsem říkal, že tou veličinou má být vhodná charakteristika vstupu, oponoval jsi, že to musí být jedině bitová délka vstupu a nic jiného. A to z důvodu, že formální definice musí být jednoznačná (což považuji za důvod velmi rozumný).

Jestli tomu dobře rozumím, náš současný spor je založen na tomto: měříš velikost vstupu bitově a představuješ si, že velká čísla na vstupu mají větší objem než malá. Toto má samozřejmě vliv při výpočtu složitosti algoritmu.
Jenomže pokud chceš měřit délku vstupu, měl bys jí měřit počtem slov na vstupu. Pro abstraktní počítač bit vůbec neexistuje, a tím pádem nemůže existovat ani tvoje představa, že velká čísla na vstupu mají větší objem než malá.

520
Vývoj / Definice časové složitosti
« kdy: 14. 10. 2010, 07:15:26 »
Debata o tomto tématu začala mezi mnou a Matyášem Novákem ve vláknu Optimální algoritmus výpočtu, a aby se v jednom vlákně neprobírala dvě témata, odskočil jsem s ní sem.
(většina mých příspěvků a asi polovina Matyášových příspěvků ve vláknu "Optimální algoritmus výpočtu" je na toto téma)


Shrnutí dosavadní debaty:

Debata začala na tom, jaká je časová náročnost tohoto algoritmu (dále "nakupovací algoritmus"), já jej považuji za kvadratický, Matyáš Novák za pseudopolynomiální.

definice [1]
Matyáš Novák vychází z formální definice, a uvažuje asymptotickou časovou náročnost v závislosti na velikosti vstupu, za velikost vstupu striktně pokládá objem dat resp. bitovou délku vstupu.

definice [2]
Já říkám, že za velikost vstupu v této definici by se měla považovat "vhodná" charakteristika vstupu, v tomto konkrétním případě požadovaný počet kusů zboží (takováto definice by se ale špatně formalizovala - je těžké určit pro obecný algoritmus, která charakteristika je vhodná): potom vyjde složitost kvadratická.

definice [3]
Stejný výsledek dá "intuitivní definice" časové náročnosti podle struktury algoritmu: výše zmíněný algoritmus je tvořen dvěma dva vnořenými cykly od 1 do n, kde n je určeno vstupními hodnotami: je tedy kvadratický. (Tato intuitivní definice půjde asi těžko formalizovat, protože je založena na algoritmu probíhajícím v lidském mozku, a formalizace by znamenala určení tohoto algoritmu. Tento algoritmus by ale nedokázal určit svou vlastní složitost.)

Tyto rozdílné definice dávají také rozdílnou složitost algoritmu pro faktoriál (zde).

Edit: pojmenoval jsem definice a úlohu

521
Vývoj / Re: Optimální algoritmus výpočtu
« 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.

522
Vývoj / Re: Optimální algoritmus výpočtu
« 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ů.

523
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 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ší.

524
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 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)
(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.

525
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 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á")

Stran: 1 ... 33 34 [35] 36