Příspěvky

991

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

« kdy: 04. 10. 2010, 15:21:51 »

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.

992

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

« kdy: 03. 10. 2010, 23:07:51 »

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.

993

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

« kdy: 03. 10. 2010, 22:14:26 »

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

994

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

« kdy: 03. 10. 2010, 11:49:22 »

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

995

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

« kdy: 02. 10. 2010, 21:47:31 »

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. 

996

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

« kdy: 02. 10. 2010, 14:44:13 »

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

997

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

« kdy: 02. 10. 2010, 12:29:08 »

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

998

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

« kdy: 01. 10. 2010, 17:29:22 »

Tvuj nick je přesnej, tak ještě jednou. :-) :-)

1) Udávat ASYMPTOTICKOU složitost algoritmu v závislosti na velikosti čísel tvořících vstup by byl principiální nesmysl...

Ale to právě děláš ty!!! Vždyť ty měříš složitost dle požadovaného počtu předmětů - čili podle velikosti jednoho čísla na vstupu, což je právě blbina (respektive není to blbina, ale takový algoritmus se nazývá nikoli polynomiální ale pseudopolinomiální).

Složitost algoritmu se prostě měří dle závislosti rychlosti (popř. spotřebované paměti) na velikosti (počtu bitů) vstupu. (Pokud ji chceš měřit podle něčeho jinýho, můžeš, ale pak nemá smysl se bavit např. o NP atd... - na spoustu NP problémů existují pseudopolynomiální algoritmy - v podstatě z definice NPúplnosti pro všechny NP úplné).

Pokud chceš Tedy měřit rychlost tvého algoritmu dle velikosti čísla udávajícího žádaný počet, musíš to dělat podle velikosti vstupu toho čísla. Ale tam je exponenciální závislost.
 

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

Chci 16 kusů (tzn vstup čtyři bity 1000). Jelikož tvuj algoritmus má závislost kvadratickou na požadovaný počet kusů, rychlost bude o(16^2)
Chci 32 kusů (tzn. vstup pět bitů 10000). Rychlost bude o(32^2) = 4*o(16^2). Tzn čtyřikrát větší.

Vůbec nejde o rychlost sčítání ale o to, že rychlost je kvadratický vzledem k něčemu, co jde na vstupu logaritmicky kódovat a tedy exponenciální k velikosti vstupu.

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

* Znova - u třídění NEZÁVISÍ na tom, jak jsou tříděná čísla velká, závisí na tom, KOLIK jich na vstupu je. Zdvojnásobením počtu čísel se zdvojnásobí velikost vstupu (a 2*log(2) zpomalí výpočet).
* U tvého algoritmu závisí počet kroků na VELIKOSTI čísla, nikoli na jejich POČTU. Zdvojnásobení čísla se ale vstup prodlouží pouze o jeden bit. Tzn. jde o závislost na něčem jiném než na velikosti vstupu.
(že jsou na vstupu pak ještě data udávající počty ceny různě velkých balení je irelevantní - s jejich větším počtem rychlost poroste max lineárně, takže je můžeme zanedbat (stejně jako u třídění velikost tříděných čísel), jediné co hraje roli je požadovaný počet kusů).

Vůbec tady nejde o složitost porovnání či sčítání, ty mají lineární složitost. Jde o to, jak ovlivní nárůst délky vstupu počet operací. Ta je u třídění daná jako nlog(n), kde n je počet tříděných prvků a u tvého algoritmu exp(n)^2, kde n je počet bitů, kterým je zapsán
chtěný počet kusů.

999

Windows a jiné systémy / Re: SW pro zálohování

« kdy: 01. 10. 2010, 17:28:17 »

Ne tak úplně... RAID taky není zálohování

Ano, RAID není zálohování, protože
a) není možnost se vrátit k úmyslně smazanému sourboru (chrání pouze proti chybě hardwaru, nikoli uživatele).
b) existuje tam single point of failure (řadič, OS se může poblbnout a zrušit MFT apod.)

Naopak synchronizace (s nelokálním úložištěm) a odkládáním přepsaných kopií splňuje vše, co je po zálohování požadováno. Proto to je zálohování. Pokud s tím nesouhlasíš, tak napiš, co zálohování dělá a synchronizace se vzdáleným úložištěm a odkládáním starých souborů nikoli.

1000

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

« kdy: 30. 09. 2010, 18:22:42 »

Přestaňte už konečně vymejšlet kolo. :-)
Lineární programování??? Parciální derivace???
Ufff. Tam vám jaksi kupodivu vždycky vyjde, že máte vzít 0.35467 kusů balení s nejnižší cenou za kus. Na to nemusim derivovat, abych todle určil, ani si dělat ty úžasný mentální tabulky na linprog.

Slowthinker postnul nejlepší řešení  (a pár lidí před ním odkaz na něj), nic lepšího se vymyslet nedá, je to prostě NP úplnej problém v trochu jinym ošacení.
Když už chcete nějaký přibližný řešení, tak se nabízí hladovej algoritmus, ale ten tady v podstatě taky zazněl (beru vždy nejlevnější balení, který se mi ještě vejde).

1001

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

« kdy: 30. 09. 2010, 13:49:17 »

slowthinker: samozřejmě chtěnej počet kusů, je to jen jiná formulace problému batohu, tak sem se upsal.

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

Složitost algoritmu se vždy udává vzhledem k velikosti vstupu, nikoli k užitým hodnotám. Takže i když vymyslíš algoritmus, kterej je polynomiální, ale na něčem jinym než na velikosti vstupu, tak to nic neříká o náležitosti do NP. Btw. vymýšlíme tady opravdu kolo, tomudle algoritmu se říká pseudopolynomiální, patří mezi takzvané dynamické programování a učí se o nich asi v každym v základním kursu složitosti a NP úplnosti a už tu padly i linky na preciznější formulace. Zkus pohledat po netu, je tam hafo online skript.

PS:
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 (přesněji čas porovnání dvou čísel roste s logaritmem jejich hodnoty respektive lineárně vzhledem k velikosti vstupu, takže tam je opravdu "nejdražší" samotné třídění: na porovnání dvou čísel lze hledět jako na atomickou operaci, protože je dražší zdvojnásobit počet čísel než zdvojnásobit možnou velikost tříděných čísel).

1002

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

« kdy: 29. 09. 2010, 22:37:18 »

Máš a nemáš pravdu. To tvoje řešení je kvadratický a funguje, ale není kvadratický vzhledem k velikosti zadání - je to něco jako kdybys tvrdil, že řadit lze rychlejc než nlogn, protože radix sort.
Problém je v tom, že je to kvadratický vzhledem k chtěný ceně, tak je ale exponenciální vzhledem k velikosti vstupu (chtěný počet n se zapíše pomocí log n cifer).
Nicméně máš pravdu, že je to asi nejrozumější možný řešení. :-)

Více viz pseudopolinomiální algoritmy.

1003

Vývoj / Re: Rozdíl mezi SQL a MySQL

« kdy: 29. 09. 2010, 21:16:27 »

Mysql možná ne. Ale postgresql (pokud není potřeba replikace, jak je to ve verzi 9.0 popř. postgresql cluster) nabízí v podstatě skoro stejný možnosti jako Oracle.
Navíc - webhosting s postgresql je všude, na oracle potřebuješ VPS.

Prostě je tu oracle a je tu postgresql, oba maj jiný náklady a jiný přednosti. Preferovat pouze oracle je postoj vhodnej tak do státní správy.

1004

Vývoj / Re: Rozdíl mezi SQL a MySQL

« kdy: 29. 09. 2010, 11:48:52 »

Přenositelné? Už např. takovej autoincrement/serial se dle databáze liší - a to je naprosto základní věc. Stejně tak interní fce, který např. může chtít použít v check constraint nebo velmi často užívanej fulltext.

Nehledě na to, že taková věc jako trigger imho není pokročilá věc, ale pro spoustu věcí v podstatě nutnost.

Souhlasim s tím, že je dobré použít nějakou db knihovnu ale zásadně nesouhlasím s tím, že by se měli psát aplikace přenositelně. Samozřejmě že se má co to jde dodržet SQL standard a nepoužívat zbytečně proprietální syntax, ale nevyužívat zbytečně možnosti databáze je blbina....  To se pak rovnou může použít rychlejší key-value nosql databáze...

1005

Vývoj / Re: Rozdílná odpověď při stejném HTTP požadavku

« kdy: 28. 09. 2010, 21:36:21 »

Neni problém v tom, že to posíláš pomocí HTTP, zatímco firefox používá HTTPS? (aspoň pokud používá certifikát, tak to asi HTTPS bude...).
Pokud jo, tak studuj tady:
https://awebproxyprd.ins.state.ny.us/docs/eassec/eassecp25.htm