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 ... 32 33 [34] 35 36
496
Odkladiště / Re:Podivné diskuse na Zdroják.cz
« kdy: 26. 01. 2014, 01:33:07 »
:) proboha, neřešte tu kdo koho má v internetových fórech zdravit.

Pro mě osobně je pozdrav implicitní, ale chápu že pro někoho to tak není.
Ometat někomu že pozdravil/nepozdravil je ale nanejvýš zvrhlé.

497
Studium a uplatnění / Re: Oplatí sa ísť študovať?
« kdy: 30. 10. 2010, 01:13:19 »
Druhá vec, je ta matika naozaj taká neuveriteľne ťažká, ako sa o nej hovorí alebo je to len "hoax" pochádzajúci od študentov, ktorý strávili viac času v krčme než učením?
Pro někoho je matematika těžká, pro někoho lehká.
Nejlepší bude, když si to sám zkusíš: Nauč se sám základy lineární algebry. A snaž se je naučit tak, abys měl pocit že do věci perfektně vidíš.
K lineární algebře nepotřebuješ nic ze středoškolské matematiky, a je to jakýsi základ VŠ matematiky, v žádném případě pro tebe nebude ztracený čas, ať studovat nakonec půjdeš nebo ne.
Sežeň si nějakou přednášku/učebnici, ale žádné populární čtení: potřebuješ takovou, kde jsou všechny věty detailně dokázány. "Důkaz" je takový honosný název, vlastně jde o "vysvětlení" věty; teprve když rozumíš důkazu, tak do věci vidíš.

498
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 29. 10. 2010, 17:16:30 »
Ano? Jenže jaksi v analýze existují pouze menší čísla, nic jiného, zatímco v TEMNU je těch podmnožin trochu více (např. {{0}}). Takže při tvrzení o podmnožinách množiny musíš udělat více práce, než při tvrzení o číslech menších než n.
Já už nevím, jak to jinak říct.
Při důkazech nemusíš stále používat axiomy dané teorie, to by byl vopruz, jak si říkal. Pomáháš si definicemi a větami. Jakmile definuješ pojem "2" a věty, které popisují potřebné vlastnosti přirozených čísel, můžeš klidně zapomenout jak bylo "2" zkonstruováno a jaké jsou její prvky a podmnožiny. V dalších úvahách si vystačíš s informací, že 2 je objekt, který má takové a takové vlastnosti.
Stejně tak se dopracuješ k větě o transfinitní indukci (posílal jsi na ni odkaz), která pojem podmnožina nebo prvek vůbec nezná, a mluví jenom o uspořádání.

Citace
Citace
Rád se nechám poučit. Jaké vlastní axiomy má MA?
Mimo axiomy predikátové logiky s rovností axiomy definující vlastnosti tělesa reálných čísel a operací nad nimi (doufám, že si to pamatuju +- přesně).

Citace
A zajímal by mě příklad tvrzení, které nelze dokázat v analýze, ale v teorii množin ano.
http://cs.wikipedia.org/wiki/Goodsteinova_v%C4%9Bta
Pamatuješ si to špatně, splývají ti matematické pojmy.

Ano, Goodsteinovu větu nelze dokázat v Peanově aritmetice, a lze ji dokázat v teorii množin. Jenomže
matematická analýza <> Peanova aritmetika.
Peanova aritmetika je něco diametrálně odlišného od MA: PA zkoumá pouze konečně velké objekty.

Stejně tak
matematická analýza <> teorie reálných čísel.
Pokud by ses spokojil s teorií založenou na axiomech tělesa, nemohl bys definovat pojmy jako posloupnost, funkce, míra.

Matematická analýza nejen že potřebuje teorii množin, ale dokonce i teorii množin s axiomem výběru.

Citace
Citace
f(n)=min (f(i)+ f(j) ....)=min (P(i)+ P(j) ....)=P(n)
funguje i pro počátek, tedy pro n=1. Je zbytečné dokazovat zvlášť, že P(1)=f(1)
Pokud neukážeš, že existuje bod, tzn. n_0, pro které tvrzení platí nezávisle na platnosti tvrzení pro jiné n, je důkaz nekorektní. Protože takovej důkaz prostě nerozlišíš od důkazu, že a+1=a.
Že to ukážeš  (skoro) stejným tvrzením jako indukční krok je druhá věc, ale ukázat to prostě musíš.
Pro jedničku tvrzení platí nezávisle na předchůdcích.
Ukazuješ to nikoli "skoro stejným tvrzením jako indukčním krokem", ale přímo indukčním krokem.
Pokud se mnou nesouhlasíš, řekni, které místo ve tvém důkazu indukčního kroku s jedničkou nefunguje.

499
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 29. 10. 2010, 02:54:57 »
Nekonečně mnoho tvrzení a nekonečně mnoho implikací se špatně zapisuje na papír. Takže místo
T(1)&T(2)&T(3)&...
se radši napíše
(pro každé n) (T(n))
a jsme úplně někde jinde.

No ale pokud bychom uvažovali konečnou indukci...
T(1)&T(2)&T(3)&...&T(z)
tak bychom skutečně mohli pomocí modus ponens dokazovat indukci:

pro slabou indukci bychom museli dokázat
T(1)
T(1)=>T(2)
T(2)=>T(3)
...
T(z-1)=>T(z)
a pak opakovaně aplikovat modus ponens

ale my máme silnou indukci, takže
T(1)
T(1)=>T(2)
T(1)&T(2)=>T(3)
...
T(1)&T(2)&...&T(z-1)=>T(z)

V minulém odstavci napíšu místo
T(1)
raději
tautologie=>T(1)

T(1) se odvodí pomocí modus ponens také:
z formulí
* tautologie
* tautologie=>T(1)
odvodím
* T(1)

obecně to pak vypadá tak, že
z formulí
* (pro každého předchůdce n) (T(n))
* (pro každého předchůdce n) (T(n)) => T(n)
odvodím
* T(n)

Potřebuji tedy dokázat pouze
* (pro každého předchůdce n) (T(n)) => T(n)

a nemusím tedy "věnovat extra pozornost pevnému bodu".

500
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 28. 10. 2010, 14:39:04 »
Indukce

A sme doma. A že takové bod (tvrzení) existuje musíš ukázat, jinak není důkaz korektní. jinými slovy - musíš věnovat extra pozornost existenci pevného bodu.
Právě že obecně nemusíš
Např. tvůj důkaz
f(n)=min (f(i)+ f(j) ....)=min (P(i)+ P(j) ....)=P(n)
funguje i pro počátek, tedy pro n=1. Je zbytečné dokazovat zvlášť, že P(1)=f(1)

Matematické teorie

Citace
Která teorie množin? ZFC? Vopěnkova alternativní? Goldstein-bernsteinova? A s jakým modelem?
...
A už je to tady - tak používáme ZFC nebo GB? A co axiom výběru? Ano nebo ne? To všechno musíš říct, aby byl tvůj důkaz  korektní a vůbec srozumitelnej...
Myslím tu teorii množin, kterou vám přednášeli na mff v prvním ročníku, a o kterou se opírá většina přednášek na mff, včetně MA. To znamená ZFC nebo GB, které jsou ekvivalentní.
Na úroveň axiomů jsme se tu v debatě nedostali, takže je jedno, z které z těch dvou teorií vycházíme, a axiom výběru jsme nepotřebovali, takže nemusíme řešit, jestli jej povolujeme nebo ne.

Citace
Jo, ale furt sou to objekty TEMNA. Tzn. např. věta o MI pracuje s podmnožinou. Tzn. abys byl korektní, tak to musíš dokázat pro všechny ordinální konečné podmnožiny dané množiny.
...
Atd. postě přirozený číslo v ZFC není až tak "jednoduchá věc" jako v analýze.
Indukci v teorii množin lze zapsat jak pomocí podmnožin, tak pomocí relace < (sám jsi uváděl odkaz na takovou definici), a pořád je to indukce a teorie množin.
Relaci < musím nejprve definovat, ale jakmile to udělám, je to stejné < jako v analýze.
(Mimochodem i relaci podmnožina musím nejprve definovat)
Jakmile odvodím příslušné vlastnosti přirozených čísel a definuji 2 = {0,{0}}, je dvojka stejná dvojka jako v analýze.

Citace
MA je postavená na svejch axiomech o číslech, takže něco jako relace náležení ordinálů a z ní vyplývající princip indukce se tam prostě nepoužívá, má vlastní princip indukce a nějaká množina n, pro který platí daný tvrzení se tam prostě nekonstruuje.
...
Nikoli. Např. analýza má svoje vlastní axiomy a pracuje pozue s nimi. ...
V TEMNU často jdou dokázat tvrzení, která v analýze nejdou - a v každém temnu a v každém modelu jiná tvrzení!
(aby nedošlo znovu k nedorozumění, mluvím o stále o GB/ZFC:)

Rád se nechám poučit. Jaké vlastní axiomy má MA? (Vím, že termín "axiom" se občas používá v rámci definic, ale to nejsou skutečné axiomy.)
Já chápu analýzu jako čistou nadstavbu nad teorií množin, to znamená pouze jako definice a věty. (A upřímně řečeno o některých definicích/větách ani nevím, jestli ještě spadají do teorie množin nebo jinam. Např. definici reálných čísel jsem viděl jak v teorii množin tak v analýze.)

A zajímal by mě příklad tvrzení, které nelze dokázat v analýze, ale v teorii množin ano.

Důkazy

Citace
Takže f nemůžu ani definovat, protože k její definici musím prostě použít musím?
Nebo jsou povolené a nepovolené užití f? Zase báťuška?
Říkají to základní matematické principy. f jsi definoval tak, že nevíš, zda existuje.
V důkazu můžeš pracovat pouze s existujícími objekty. Pokud nevíš jestli objekt existuje, musíš si pomoci předpokladem jeho existence.

Když řešíš rovnici, tak vyjdeš z předpokladu, že existuje řešení x a odvodíš, že pak x=a. Tím jsi ukázal, že a je jediným řešením, které připadá v úvahu, ale ne že je řešením, to musíš ještě ověřit.

Jestli si myslíš, že se někde v důkazu věty o konstrukci rekurzí používá f, aniž by se vědělo, zda existuje, tak mi to místo ukaž.

501
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 27. 10. 2010, 01:08:35 »
S tímhle souhlasím. Ale platí-li to pro 0 bez jakýchkoliv předpokladů, dělá to z nuly to, co je v této diskuzi označováno jako pevný bod (nejsem si jistý, jestli korektně, zatím jsem se s touto terminologií nesetkal, ale možná jde jen o mou neznalost).
Ano, to jsem říkal. Pevný bod je tam vždy, jde jen o to, jestli je třeba pro nulu/počátek/pevný bod dělat zvlášť důkaz.
Pokud indukční krok funguje od počátku (nic=>0), tak to není třeba, pokud až od počátku+1 (0=>1), je třeba udělat zvlášť důkaz pro počátek.
Jinak terminologii si tu asi děláme vlastní...

502
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 26. 10. 2010, 22:27:45 »
Dokazuju tvrzení: a = a+1
Indukční krok, tj. (a = a + 1) =>  ((a+1) = (a+1) + 1), je triviální dokázat, přesto je snad zřejmé, že uvedené tvrzení neplatí.
To je ale to samé v bledě modrém. Matyáš napsal indukční krok pro a, tohle je stejný indukční krok, jenom zapsaný pro a+1. Pro a+1=0 nelze  důkaz použít, protože a neexistuje.

Důkaz indukcí "bez pevného bodu" vyžaduje abys ukázal
platí-li tvrzení pro všechny předchůdce a, platí i pro a.
Pro a=0 to znamená, že důkaz musí fungovat, aniž by bylo možné se opřít o jakéhokoli předchůdce.

IMHO v teorii množin se o matematické indukci v podstatě nemluví. Přirozený čísla jako objekt v TEMNU je vcelku nezajímavej objekt
O přirozených číslech a MI se mluvit musí, jinak by teorie množin nemohla sloužit jako základ ostatních matematických oborů.
Mimochodem, někdy někde jsem viděl Godel-Bernaysovu teorii množin, včetně pasáže o přirozených číslech a definice MI (včetně "Fin(x)",  na které jsem o pár příspěvků výše zapomněl).

Citace
Navíc MI (z věty o slabém principu) je definovaná pro n ze Z, takže jsou dvě možnosti:
a) buďto MI v analýze je něco jinýho než MI v temnu (což je zjevně blbost)
b) nebo MI v temnu vyžaduje pevný bod.
MI definovaná pro celá čísla? Tomu nerozumím.
a) souhlasím, nevidím žádný rozdíl, kromě toho, že v analýze se zřejmě vždy pracuje s konstrukcí M ={n z N; tvrzení T(n) platí}
a indukce "s pevným bodem"-"bez pevného bodu" jsou jak v MA tak v TeMnu, navíc jsou obě indukce v podstatě jedno a to samé
b) chceš snad říct, že ta věta nefunguje, ani po opravách?

Citace
Co to znamená a použijeme MI. To znamená ověřit předpoklady. Předpoklad pak je, že je-li x podmnožinou a ordinálem (tos tam taky zapoměl, bez toho to imho nejde), pak je i prvkem. To celé bys měl ověřit prostředky TEMNA (axiomy, množiny, ne žádný čísla a podobný "výdobytky civilizace"). Vopruz.
Máš pravdu, zapomněl jsem, že x má být ordinál.

Číslo 2 nebo pojmy "funkce", "matematická indukce" jsou nějak teorií množin definované. Jakmile je definuji, mohu je pak normálně používat, bez axiomů.
Teorie množin není žádná uzavřená exotická část matematiky, naopak se "spojitě" rozvětvuje do ostatních disciplín matematiky.

A v každém matematickém odvětví, ať je to teorie množin nebo analýza nebo cokoli jiného, mohu dělat důkazy čistě formální jen jako posloupnost formulí na základě výrokové a predikátové logiky (vopruz), nebo jako mix přirozeného jazyka a matematických symbolů (což je nejběžnější), ale i zcela bez matematických symbolů.
Takže když řeknu
matematická indukce říká: platí-li, že (jsou-li v podmnožině přirozených čísel všichni předchůdci n (ve smyslu uspořádání relací náležení), je tam také n), jsou v této podmnožině všechna přirozená čísla
tak je to taky teorie množin, i když pouze neformální.

Citace
Citace
To bys ale nesměl začít psát důkaz rovností
f(n) = min (f(i)+ f(j) ....)
Musel bys začít z druhé strany P(n)=...
Proč ne? Indukcí mám přeci zajištěnou existenci f(i) a f(j). Ten důkaz zároveň dokazuje existenci i rovnost.
Nikde nepoužívám nic, co by předem nebylo dobře definovaný - vždyť sáms psal, že v podstatě trochu kopíruju větu o konstrukci rekurzí.
Napsal jsem hloupost, je jedno z které strany začneš. V každém případě f nemůžeš používat, pokud nevíš, jestli existuje jako celek: existence f(i), f(j) nestačí.

To znamená, že formálně je to takhle: rovnicí
f(n)=min (f(i)+ f(j) ....)=min (P(i)+ P(j) ....)=P(n)
nedokazuješ
P=f
nýbrž
jestliže f existuje, pak P=f.
(pozn. důkaz tohoto tvrzení odpovídá důkazu jednoznačnosti funkce definované rekurzí)

K tomu musíš dokázat, že f existuje, ale to je jasné, stačí do předpisu dosadit P.
(
pozn. naopak u rekurze je důkaz existence funkce složitější. Takže není tak úplně pravda, jak jsem říkal, že kopíruješ důkaz věty o definici rekurzí.

Jenomže tvůj důkaz se rekurzi (resp. existenční části důkazu věty o definici rekurzí) stejně nevyhne:
Máš funkci definovanou předpisem na základě svých vlastních hodnot v jiných bodech. Víš sice, že existuje právě jedna funkce daná předpisem, ale nevíš, jestli lze na základě toho předpisu sestavit algoritmus, který funkci vyčíslí.
Zřejmě platí následující tvrzení:
jestliže je předpis rekurzivní, tj. jestliže pro každé n je hodnota funkce určena na základě hodnot předchůdců, lze na základě tohoto předpisu algoritmus sestavit.
Důkaz tohoto tvrzení bude zřejmě analogický s existenční částí důkazu věty o definici rekurzí.

Takže i když se zkusíš vyhnout rekurzi, použiješ myšlenky jak existenční tak jednoznačnostní části důkazu věty o rekurzi.
)

503
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 24. 10. 2010, 21:50:31 »
Mě se zdá, že v každym postu používáš něco jinýho. Nejdřív si tvrdil, že používáš  matematickou indukci bez pevnýho bodu, pak zas že indukci nepoužíváš vůbec, pak užíváš omezenou transfinitní indukci, potom zas větu o definici funkce rekurzí.
Říkal jsem, že na důkaz Lemmatu nepotřebuješ indukci. A ty tři ostatní věci jsou plus minus jedno a to samé.

Citace
A co když to tvrdím na celých číslech? Tam každé číslo předchůdce má...
Tvrdit to můžeš, ale nemůžeš to dokazovat žádnou indukcí, protože ta funguje pouze pro dobře uspořádané množiny.
Dobře uspořádané množiny samozřejmě počátek (=pevný bod) vždy mají. Jiná věc je, že pro tento počátek není vždy nutné provádět separátní důkaz.

Citace
TI říká pouze něco o vlastnostech přirozených čísel, MI rozvnou o tvrzeních, aplikovaných na ně. Takže pokud chceš užít TI (respektive navíc omezenou na přirozená čísla, což si vyžádá další práci navíc)
Ale já nepoužívám TI, používám MI. Jenom jsem mimochodem konstatoval, že
MI = TI omezená na přirozená čísla

Jinak TI a MI říká to samé, jenom to říká o jiné množině. "Říkat něco o tvrzeních, aplikovaných na přirozená čísla" to není součást indukce, to je jenom přílepek:
MI indukce (ve smyslu teorie množin) říká, že má-li M, která je podmnožinou N, nějakou vlastnost, je pak rovna celému N. Nic víc.
Při řešení problému pak definujeme M ={n z N; tvrzení T(n) platí}. a použijeme MI.
(a přijde mi odvážné říkat minulému řádku "práce navíc")

Citace
PS: Jinak existenci f ověřovat nemusím, protože P existuje, dokážu-li tedy ekvivalenci P a f, musí existovat i f.
To bys ale nesměl začít psát důkaz rovností
f(n) = min (f(i)+ f(j) ....)
Musel bys začít z druhé strany P(n)=...

504
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 23. 10. 2010, 15:45:53 »
 ::) Je vidět, že jsi 8 stránek jen běžně proskákal, a tudíž nevíš o čem mluvíš. Optimální řešení je mnohem jednodušší než suboptimální.
(a aby bylo jasno: akademické debaty nejsou o tom, co je nejlepší řešení, ale jak formálně dokázat správnost tohoto nejlepšího řešení)

505
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 23. 10. 2010, 01:38:45 »
Indukce

co popisuješ je co vím modifikované tvrzení o
transfinitní indukci a nikoli o MI. Takže
1) to co popisuješ IMHO není matematická indukce
2) M podle předpokladu obsahuje sama sebe a tedy obsahuje prvek: množinu všech přirozených čísel. Množina všech přirozených čísel je první nekonečno. Takže prvkem M je nekonečno a tedy M není podmnožina N_0. Spor.
1) matematická indukce není nic jiného než transfinitní indukce oříznutá na přirozená čísla.
2) to jsi mě dostal. Zapomněl jsem omezit implikaci na konečné množiny. Správně má ve větě být "pro každé konečné x platí:"

Citace
Btw. i v Tvém důkazu je vlastně pevný bod. Tvrdíš, že pro P(1) nepotřebuješ předpoklady. Jenže to je třeba taky dokázat (byť je to taky vcelku trivoš). Tím ale přistupuješ k P(1) jinak než ke všem ostatním. Takže také používáš pevný bod. A navíc protože nedokazuješ explicitně P(n_0) nemůžeš použít větu o MI, takže asi používáš nějakou svojí indukci. a tu bys měl dokázat.
Mluvíš o důkazu Lemmatu? V tom důkazu je pevný bod, ale nevyžaduje speciální důkaz. Důkaz Lemmatu funguje stejně pro jedničku jako pro libovolné n.
Používám tu větu o MI, na které jsi mě nachytal a kterou jsem opravil.

Citace
Ono to totiž bez pevného bodu to nejde! Např platí   (a = a - 1) =>  ((a+1) = (a+1) - 1). To ale neznamená, že a = a - 1. Proto je pevný bod pro MI nutnost. Ona i ta věta o transfinitní indukci se pak musí užít s pevným bodem:
http://mathworld.wolfram.com/TransfiniteInduction.html
Ta věta v odkazu není dobře zapsaná: není řečeno, pro jaká a má platit indukční krok 2.=>3.
Pokud pro a>=1, pak je pevný bod 1. potřeba (označím takovou indukci "verze s pevným bodem").
Pokud pro a>=0, pak není bod 1. potřeba (resp. je obsažený v indukčním kroku) (ozn. "verze bez pevného bodu").

Při důkazu verzí bez pevného bodu implikace "(a = a - 1) =>  ((a+1) = (a+1) - 1)" pro a=0 nefunguje, protože a nemá předchůdce. Takže žádný problém.

Mnou uvedená definice (transfinitní) indukce pro přirozená čísla/ordinály odpovídá verzi bez pevného bodu.

Mimochodem, věta v odkazu je věta o transfinitní indukci pro dobře uspořádané množiny, nikoli pro ordinály. Dobře uspořádaná množina nemusí být uspořádaná právě relací náležení, takže ten jednoduchý zápis věty o indukci pomocí relace náležení není pro dobře usp. množiny možný.

Tvůj/můj důkaz

Citace
Citace
tak vidím, že v důkazu nemá P co dělat (P je takto použito v Lemmatu a sám jsi uznal, že pro Lemma indukce není třeba), na jeho místě má být f.
Ach jo. Tak znova.
"Znova"? Až doteď jsem se vyjadřoval k tvému indukčnímu kroku v příspěvku #104. A tam nebylo po f ani památky.
Teprve následující důkaz je formálně (téměř) v pořádku...
Citace
Dokazuji, že P(a) = f(a).
...
Abych T(n) dokázal, tak
1) použiji indukční předpoklad, že f(k) = P(k) pro všechna f(k) v definici f(n) a tedy
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...)
2) použiju Lemma, že min (P(i)+ P(j)...) = P(n)
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...) = P(n)
... až na to, že zapomínáš na jeden detail:

Nemužeš dokazovat, že
P(a) = f(a)
jestliže nevíš, zda f(a) existuje.
Ve skutečnosti dokazuješ
f(a) existuje a P(a) = f(a)

a pro rovnost
f(n) = min (f(i)+ f(j) ....)
musíš využít indukční předpoklad taky.
(ovšem pokud se na f nedíváš jako na funkci definovanou rekurzí, ale jako na funkci definovanou algoritmem, čeká tě ještě práce navíc.)
Citace
Nesouhlasím s tím, že pokud
f(n) = min (f(i)+ f(j) ....)
pak tvrzení
P(n) = f(n) plyne okamžitě Lematu, aniž bys použil MI (popř. postup MI podobný). Pokud nesouhlasíš, tak to formálně dokaž.
Důkaz: Z Lemmatu plyne, že P splňuje náš rekurzivní předpis P(n) = min (P(i)+ P(j) ....). Ale věta o definici rekurzí říká, že taková funkce je jen jedna, tedy P=f.
(Jak už jsem zmiňoval, rekurze je založena na indukci, takže s tou potřebou indukce máš pravdu.)

Edit:
Rozdíl mezi našimi dvěma důkazy:
Já používám větu o definici rekurzí, a ty dokazuješ větu o definici rekurzí pro náš specifický případ.
(:P jako bys zapomínal na úchylku matematiků převádět problémy na dříve vyřešené)



[off-topic]
  • Napsal jsi: "PS: Co se týče mojeho matematického vzdělání, doporučil bych Ti se krotit, by ses neztrapnil.... :-) Ale to jen tak na okraj.... :-)"

    Dost jsem se divil, když jsem četl vedlejší vlákno. Tipoval jsem tě na fel nebo něco podobného, v žádném případě mff. Taky bych  předpokládal, že informatici mají v prvním ročníku semestr teorie množin (takhle to aspoň (prý :) ) bylo dřív).
    (No a o tvou matematiku jsem se otíral jenom proto, protože sis začal :P )
[/off-topic]

506
Vývoj / Re: Definice časové složitosti
« kdy: 20. 10. 2010, 11:34:57 »
Panove, mohl bych vas o neco poprosit? Zajimalo by me vase vzdelani (kde, co a rocnik/dosazeny titul) :). Od vsech... :)
Já mám základní školu. Titul mi tam bohužel nedali.
A tvoje vzdělání? Ptám se proto, že jsem slyšel, že dneska má titul každý blbec, ale protože jsem sám na vysoké škole nestudoval, nemohl jsem si to na místě ověřit. Možná, že bys mi to mohl osvětlit?

(výše uvedeným odstavcem jsem chtěl říct: proč tě to vůbec zajímá?)

507
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 20. 10. 2010, 10:57:48 »
[slovíčkaření]
[/slovíčkaření]

Citace
f(n) není definována korektně nebo nekorektně. f(n) je definována algoritmem.

f(0) = 0
f(n) = min( i(n), f(a) + f(b): a+b = n), a,b,n je z N, i(n) = nejnižší cena balení s i prvky,
Matematickou teorii, ve které se definuje algoritmem, bohužel neznám. Já používám teorii množin, kde se může definovat rekurzí, kterážto je úzce spojena s principem indukce. (pokud bys nevěděl o čem mluvím, podívej se do článku, který jsi už 5x postnul).
Připadá mi ale, že moje definice rekurzí bude odpovídat tvé definici algoritmem, takže v tom asi nebude žádná potíž.

Potíž je v tom, že definice rekurzí/algoritmem nemusí být definována korektně - zaměn v definici třeba "a+b" za "a-b", a máš zásadní problém.
Korektnost dokážeš právě indukcí.

Pokud se podívám na tvůj indukční krok pro 0 (tak jak je na začátku #104)

"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é }"


tak vidím, že v důkazu nemá P co dělat (P je takto použito v Lemmatu a sám jsi uznal, že pro Lemma indukce není třeba), na jeho místě má být f.
Osobně odhaduji, že intuitivně důkaz asi chápeš, jenom ho nedokážeš zformalizovat, protože máš zřejmě zkušenosti jenom s intuitivní matematikou a s formální matematikou ne. Odhaduji, že jsi asi chtěl vyjádřit toto:

"Je-li f(0) definováno, pak je definováno i f(1). Důkaz: f(1) je minimum množiny vzniklé sjednocením množin A, B, A= ..."

Potom by důkaz byl formálně v pořádku.

Citace
Já preferuju, že si udělám byť nepotřebný pevný bod, který mám dokázán hned a použiju již existující větu. To je taková úchylka matematiků, že když vyřešej jeden příklad, tak ostatní na něj převáděj.
Zapomněl jsi na drobný detail: Matematici převádějí, pokud je převádět skutečně třeba.
Tohle je tvůj způsob uvažování:

Máš dokázat, že pro každé n z N platí sqrt(n^2)=abs(n).
Znáš matematickou indukci.
Víš o úchylce matematiků, převádět problémy na dříve vyřešené věci.
Pro důkaz proto použiješ matematickou indukci.
Dokážeš nejprve pevný bod sqrt(1^2)=abs(1).
To, že pevný bod dále nepoužiješ, tě netrápí: naučil ses, že indukce vyžaduje pevný bod.
Pak dokážeš indukční krok. To, že že indukční předpoklad nepotřebuješ, tě netrápí: naučil ses, že indukce vyžaduje indukční krok.

Citace
Prosím, přestaň psát nějaké dojmy a používej matematicku. Jak je definovaná věta o MI? Platí-li P(n_0) a P(n_0) ... P(n) => P(n+1), pak....
Tak jaktože není pevný bod potřeba? K tomu, abys použil větu, musíš splnit všechny předpoklady.
:) Neměl by se tolik ohánět matematikou, pokud neznáš matematické základy a teorii množin.
Budeš se možná divit, ale "čistá" věta o indukci (a obecněji  transfinitní indukci) v teorii množin pevný bod nepotřebuje: nejjednodušší verze věty o indukci zní takto:
Je-li M podmnožina N_0 taková, že
pro každé x platí: x je podmn. M => x je prvkem M
(toto je "indukční krok")
pak M = N_0.

Pevný bod (neboli "0 je prvkem M") tam samozřejmě je schovaný, plyne však z "indukčního kroku", a není třeba jej samostatně uvádět.

Podobně je tomu u "slowthinkerova důkazu" (nebo jak mu říkáš): pevný bod tam je, ale protože je zabudován v indukčním kroku, není třeba jej zvlášť dokazovat.

Citace
Ano, můžeš si jestli chceš zopakovat důkaz věty o MI aplikovanej na tento konkrétní příklad, tím si dokázat slowthinkerovu větu o matematické indukci problému batohu a tu pak aplikovat bez pevného bodu. Pravda, bude diskutabilní, jestli vůbec jde o indukci (ta v sobě inherentně nese potřebu pevného bodu, viz schéma axiomu o induxi) a bude to asi desetkrát složitější a daleko méně čitelné, ale jde to.
To, že něcomu nerozumíš, neznamená, že je to 10x složitější, než to co chápeš.
"slowthinkerův důkaz" je v podstatě tvůj důkaz, správně naformulovaný a ořezaný o všechny zbytečnosti.



Shrnutí:
Shrnutí chyb ve tvém důkazu (první chyba je fatální, druhá důkaz zbytečně komplikuje):
- v indukčním kroku používáš P na místě f
- zcela zbytečně do důkazu přidáváš krok 0->1

Pokud máš nějaké konkrétní výhrady k mému důkazu (kromě toho, že si pletu dojmy s pojmy), sem s nimi. (pokud se v něm neorientuješ, protože je rozesetý po vlákně, můžu ti ho znovu zformulovat)

508
Vývoj / Re: Definice časové složitosti
« kdy: 18. 10. 2010, 22:50:30 »
Já se vrátím.
(nemám teď moc času a Matyáš mě plně vytěžuje ve vlákně "Optimální algoritmus výpočtu".)

509
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 18. 10. 2010, 22:45:31 »
[slovíčkaření]
  • V tom slovíčkaření si protiřečíš:

    Ty jsi mě napadal, že nemůžu použít tudle indukci a musím použít jinou.
    (pozn. na upřesnění: já říkal "tohle je jiná indukce", ne co musíš použít. Pro mě za mě si použij třeba pouze axiomy teorie množin s Hilbertovskou logikou a nic víc.)
    Jestliže místo jakékoli silné indukce můžeš použít slabou (což je pravda), tak taky místo jakéhokoli důkazu slabou indukcí můžeš použít důkaz, který se bez indukce obejde úplně. A neměl bys tvrdit toto:
    Citace
    K tomu, abys toto tvrzení dokázal tu indukci potřebuješ.
  • Citace
    Pokud nevěříš mě, tak si přečti to, co jsem už asi pěštrát postoval:
    http://math.feld.cvut.cz/habala/teaching/dma/dmknih03.pdf
    ;) Habala v tom článku taky říká, že silná indukce existuje, a ty mu to popíráš.
[/slovíčkaření]



Aby nedošlo k omylu, označím
Lemma:
Nejnižší cena košíku s n prvky je minimum množiny vzniklé sjednocením množin A, B.
A = { Nejnižší cena balení s n prvky }
B = { P(i) + P(n-i), kde i a n - i jsou přirozené }


Lemma+ bude tvoje původní tvrzení s předpokladem
"Je-li P(n) nejnižší cena košíku s n prvky"



Citace
Formálněji: Máš funkci danou předpisem:
f(0) = 0
f(n) = min( i(n), f(a) + f(b): a+b = n), a,b,n je z N, i(n) = nejnižší cena balení s n prvky,
existuje-li, jinak nekonečno.
...
 Chceš dokázat, že pro každé n z N platí tvrzení T(n).
P(n) = f(n)
K tomu, abys toto tvrzení dokázal tu indukci potřebuješ. Protože pro každé n potřebuješ aplikovat ono lema + indukční předpoklad, že f(a) a f(b) jsou minimální košíky pro a/b prvků.
Přesněji:
Pokud je f(n) definována korektně, P(n) = f(n) plyne okamžitě z Lemmatu, na to indukci nepotřebuješ.
Indukcí dokazuješ to, že f(n) je definována pro každé n z N (tj. že f(a) a f(b) jsou "v pravý čas" k dispozici).

Citace
A pokud jde o to, že nikde dál nepoužiješ předpoklad pro nulu, tak to je MI úplnej šumák.
Pro MI je prostě potřeba mít nějakej pevnej bod, z kterýho začneš. Jelikož se bod pro nulu sestrojí nejjednodušeji a zároveň nezesložití indukční krok, je velmi vhodné začít z něho. Je úplně jedno, jestli ho pak někdy použiješ nebo ne.
Obecně pro jakoukoli úvahu platí, že je nesmyslné vytvářet pevný bod, od kterého se stejně nebudu nikdy odrážet. Navíc není pravda, že pro MI je třeba mít pevný bod (vysvětlím dále).

A teď k naší konkrétní úloze:
Indukční krok (odpovídá bodu (b) dále) zní:
Pro každé n z N: jestliže je f(k) definováno pro každé k, 1<=k<n, je definováno i f(n).
Indukcí dokazuješ korektnost rekurzivní části definice funkce f, tj. od jedničky nahoru; jak je definováno f(0) nebo f(-55), nebo jestli je vůbec definováno, nemá na důkaz vůbec žádný vliv.

Možná, že tě plete, že většinou indukce pevný bod vyžaduje, a ty se do pozice pevného bodu snažíš vmanévrovat nulu. V našem případě ale pevný bod není u indukce vůbec potřeba:

Silná indukce s pevným bodem vypadá takto:
(a) T(1) platí
(b) pro každé n>=2 jestliže T(k) platí pro k=1..n-1, pak platí i T(n)

(a) bývá většinou potřeba proto, že (b) nefunguje pro n=1. Ale v našem případě (b) funguje i pro n=1, takže pevný bod (a) není třeba.



Citace
A proto klidně můžu MI užít. Ale tady je jednodušší to tvrzení dokázat jinak, takže užití MI není nejvhodnější, byť možné.
Souhlasím. Do důkazu pro sqrt(n^2)=abs(n) je možné přicpat indukční kroky pro každé n, a nepoužívat je. Důkaz se tím ale bezdůvodně zkomplikuje.
Stejně tak ale uměle přicpáváš každý druhý indukční krok u důkazu pro a_2i=2*a_(2i-2): normální by bylo použít slabou indukci a skákat po sudých číslech. Jestliže chceš mermomocí skákat po jedničkách, musíš použít silnou indukci, a rozlišovat jestli jsi na sudém nebo lichém čísle, a indukční krok používat jenom u sudých. Důkaz se tím bezdůvodně komplikuje.
No a v našem případě naší úlohy s baleními je to podobné. Můžeš uměle přidat indukční krok pro 0 nebo i pro -55, ale důkaz se jenom bezdůvodně zkomplikuje.



Citace
...co je to košík. Definujeme ho tedy jako n-rozměrný vektorový prostor nad pologrupou jejíž hodnoty jsou počet balení, kde bázi tvoří jednotlivá balení.
Technická poznámka: Formálně vektorový prostor nad pologrupou (která není současně tělesem) nesestavíš. Množina košíků tedy není podprostorem vektorového prostoru, ale jde o část podprostoru - lineární kombinace s koeficienty z N_0.

Citace
Není-li možný záporný počet balení, pak je danou grupou grupa N_0 a obor hodnot v(k) a tedy definiční obor f(n) je taktéž N_0.
Technická poznámka: Pokud úloha zní, že chci v košíku "přesně" x ks zboží a ne "alespoň" x ks, nemusí být obor hodnot v(k) celé N_0.  Představ si "bázi" tvořenou jediným balením s 2 ks zboží.
Ale to neznamená problém, v definici f to řešíš pomocí nekonečna.

Citace
v T(-55) je užito f(-55), ta je však definovaná taktéž pouze nad N_0. Tvrzení tedy nemá smysl. (stejně jako nemá smysl tvrzení, ve kterém je dělení nulou.
(Pozn.: Přesněji bys měl říct "je užito P(-55)": Funkci f pro Lemma+ nepotřebuješ.)

Předpoklad Lemmatu+ by měl být správně zapsán takto: "Je-li P(n) definováno, ...". Pak je tvrzení T(-55) v pořádku.
Formálně nelze Lemma+ napsat pomocí "Je-li P(n) nejnižší cena košíku s n prvky,...": Formálně je totiž Lemma+ zapsáno ve tvaru "pro každé n platí T(n)", a formule by takto nebyla korektně sestavená, jak jsi zrovna vysvětlil.

edit: typo: označení Lemma' místo Lemma+

510
Vývoj / Re: Optimální algoritmus výpočtu
« kdy: 15. 10. 2010, 16:24:57 »
Druhou věc, kterou jsem tvrdil bylo, že neexistuje jiná indukce. Pokud je slabý a silný princip indukce EKVIVALENTNÍ, nemůže být JINÝ. protože kdyby byl jiný, nemohl by být ekvivalentní.
To, že jsou dvě věci ekvivalentní přece neznamená, že nemohou být jiné. To bys mohl úplně stejně tvrdit, že neexistuje žádná matematická indukce, protože ji lze odvodit ze základních důkazních metod. Ano, každý důkaz indukcí můžeš přepsat tak, že formálně půjde o důkaz bez použití indukce, jenomže ten princip indukce tam bude pořád vidět.

Podobně i silná indukce je od slabé dobře rozlišitelná:
Jestliže máš silnou indukci
T(1)+T(2) ...+T(n-1) => T(n)
můžeš ji sice převést na slabou tak, že definuješ
U(n)=T(1)+T(2) ...+T(n) a získáš indukční krok U(n-1)=>U(n).
Jenomže na tom tvrzení U bude dobře vidět, že je v onom speciálním tvaru.

Citace
Citace
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...
Nevidíš důvod u takhle triviální věci a poučuješ tady lidi o (vzhledem k tomu) poměrně složitejch věcech jako je korektnost MI a teorie složitosti a NP-úplnosti?
Pokud povolíš košík se záporným počtem kusů, tak můžeš např. udělat košík s jedním kusem jako 1x3kusy + (-1)x2kusy.
Máš pravdu, moje chyba. Nechápu takovou triviální věc a opovažuju se tady poučovat.
 :P Ale trvám na tom, že není pravdivé tvoje tvrzení, že moje tvrzení není pravdivé. A také není pravdivé tvoje tvrzení, že by bylo nutné povolovat nějaké záporné počty balení.

Citace
Co třeba důkaz MI že pro posloupnost
a0=1
a_2i=2*a_(2i-2)
a_2i-1=1
Platí:Je-li i je sudé pak a_i=2^(i/2) jinak a_i=1

Tam dokonce nejen A(1), ale dokonce každej druhej indukční krok nebude potřebovat indukční premisu. Vadí to snad nějak tomu důkazu? Nebo jako nesmím použít MI, když v některejch krocích nepoužiju premisu?
U důkazu matematickou indukcí, kterým budu dokazovat, že pro každé přirozené n platí sqrt(n^2)=abs(n), dokonce žádný "indukční krok" nebude potřebovat indukční premisu, a důkazu to taky nijak nevadí...

Citace
nějakej první krok udělat musím a P(1) je složitější než P(0)
...
Ano, v prvním kroku indukce je tento předpoklad zbytečný
Tak já ti prozradím pointu:
První krok udělat nemusíš. A tvůj indukční předpoklad je zbytečný ve všech krocích, a zbytečné jsou i samotné kroky:
Snažíš se nacpat indukci tam, kde žádná není potřeba. Následující tvrzení přece platí i bez jakýchkoli premis:

Nejnižší cena košíku s n prvky je minimum množiny vzniklé sjednocením množin A, B.
A = { Nejnižší cena balení s n prvky }
B = { P(i) + P(n-i), kde i a n - i jsou přirozené }

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