Optimální algoritmus výpočtu

[Logik]

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

[Reklama]

[andrej]

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 )

[Logik]

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

[slowthinker]

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 )

[Logik]

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.

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. 

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

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. 

[Reklama]

[slowthinker]

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

[Logik]

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

[slowthinker]

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

[Logik]

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ášť).

....ž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).

[Oliver ggg]

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?

[Logik]

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.

[Ondřej Vaniš]

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.

[slowthinker]

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.

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.

[slowthinker]

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á")

[Logik]

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.