Příspěvky

526

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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.

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.

527

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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
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).

528

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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í
?

529

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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 )

530

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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) .

531

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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.

532

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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.

533

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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é.

534

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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ží.

535

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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.

536

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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í.

537

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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á.

538

Vývoj / Re: Optimální algoritmus výpočtu

« kdy: 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] )