Je titul potřebný pro praxi?

hu

Re:Je titul potřebný pro praxi?
« Odpověď #420 kdy: 14. 05. 2015, 15:01:53 »
lineární diferenční rovnice nejsou triviální

Vyžaduji důkaz tohoto tvrzení.


Re:Je titul potřebný pro praxi?
« Odpověď #421 kdy: 14. 05. 2015, 15:10:36 »
lineární diferenční rovnice nejsou triviální
Vyžaduji důkaz tohoto tvrzení.
:D
Tak to spíš ty ukaž triviální vysvětlení všeho kolem lineárních diferenčních rovnic.

Dneska tu už nebudu, tak mě prosím zase nepohřběte.
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

Re:Je titul potřebný pro praxi?
« Odpověď #422 kdy: 14. 05. 2015, 15:59:53 »
Akorát tam je matice NxN, což když pro vzdálenost použiju double a N bude 500000 vyžaduje asi 1860 GB paměti a to nemám. Co ted? :)

Půl miliónu bodů? Co to máš za data? Pokud nebudeš ty vzdálenosti předpočítávat, tak už tam nic jiného tak moc náročného na paměť není, ne? Ale to jen pokud by ses chtěl držet toho maďarského algoritmu.

Trubicoid2

Re:Je titul potřebný pro praxi?
« Odpověď #423 kdy: 14. 05. 2015, 16:52:00 »
Paměť žere ta matice NxN, půl milionu je ještě málo, mám i deset miliónů. Vono když to nepředpočteš, tak to bude pomalý. Už teď je to o3-o4, chtělo by to něco blízko o1, jak v rychlosti tak v paměti. Data jsou tajný souřadnice atomů v textovém souboru.

gamer

Re:Je titul potřebný pro praxi?
« Odpověď #424 kdy: 14. 05. 2015, 17:12:59 »
Paměť žere ta matice NxN, půl milionu je ještě málo, mám i deset miliónů. Vono když to nepředpočteš, tak to bude pomalý. Už teď je to o3-o4, chtělo by to něco blízko o1, jak v rychlosti tak v paměti. Data jsou tajný souřadnice atomů v textovém souboru.
Obávám se, že optimální řešení na tak velkých datech v ruzumném čase nespočítáš. Pokud by stačilo suboptimální, tak nacpat data do nějakého stromu (kd-tree), náhodně vybrat bod, range search rozumného počtu okolních bodů na kterých poběží ten Hungarian algorithm, potom je vyhodit ze stromu a tak pořád dokola, dokud zbývají nějaké body.


Trubicoid2

Re:Je titul potřebný pro praxi?
« Odpověď #425 kdy: 14. 05. 2015, 17:24:16 »
Tak nějak jsem uvažoval, vybrat M kandidátů, co jsou nejblíž. Pak bude matice jen NxM, M asi stačí řádově 10...

Re:Je titul potřebný pro praxi?
« Odpověď #426 kdy: 14. 05. 2015, 17:34:12 »
A co tak se podívat po nějakých aproximačních algoritmech? Tady http://people.orie.cornell.edu/dpw/GW92.ps by něco užitečného nebylo?

Re:Je titul potřebný pro praxi?
« Odpověď #427 kdy: 14. 05. 2015, 18:16:44 »
Tak nějak jsem uvažoval, vybrat M kandidátů, co jsou nejblíž. Pak bude matice jen NxM, M asi stačí řádově 10...

Pozor, aby sis tím nenaběhl. Pokud bude někde existovat K bodů (K>M), které všechny budou mít stejnou množinu těch M kandidátů, tak ta úloha nebude mít řešení.

Mr. Fox s knírem

Chci zpět můj život před tím, než mi ho tenhle thread zruinoval
« Odpověď #428 kdy: 15. 05. 2015, 22:45:17 »
Gratuluji vám, pánové!

Tohle je zatím ten nejretardovanější thread, jaký jsem kdy četl, což je s podivem, protože už jsem četl věci, které svou debilitou vytvářely pukliny v samotném předivu reality. Nic však nevykazovalo takovou sofistikovanou míru retardace jako právě tahle diskuze.

Ač začala nadějně, tak po desáté stránce se vám podařilo vytvořit ve mě rakovinu, která mi nedovolila jít se zabít a donutila mě dočíst. U osmnácté stránky jsem ztratil veškerou naději v lidstvo a zemřela ve mě nevinnost. Na dvacáté straně se mi levé oko obrátilo čočkou dovnitř hlavy. Během čtení třiadvacáté strany jsem začal blábolit v cizích jazycích a pomohl až kněz, i když jen na chvíli. Na pětadvacáté straně jsem konečně přijal šílenství, podíval se mu do rozšklebené tváře, a strhl poslední hráze příčetnosti. Od té doby mé zbývající oko získalo fialový nádech, nejde zavřít a z tváře nemůžu dostat škleb.

Teď když jsem dorazil na konec se cítím v duši prázdný. Nezbylo z ní nic, než popel, zima a prach. Jdu se zkroutit do kouta a zemřít.

jj

Re:Chci zpět můj život před tím, než mi ho tenhle thread zruinoval
« Odpověď #429 kdy: 15. 05. 2015, 22:54:41 »
Teď když jsem dorazil na konec se cítím v duši prázdný. Nezbylo z ní nic, než popel, zima a prach. Jdu se zkroutit do kouta a zemřít.

A to jsi ještě ani nepotkal SAP. Ta dnešní mládež nic nevydrží.

v

Re:Chci zpět můj život před tím, než mi ho tenhle thread zruinoval
« Odpověď #430 kdy: 15. 05. 2015, 23:02:51 »
fialový nádech, nejde zavřít a z tváře nemůžu dostat škleb

to bude špatné zažívání, zkuste jíst víc vlákniny a jogurt

Re:Je titul potřebný pro praxi?
« Odpověď #431 kdy: 17. 05. 2015, 18:07:48 »
Konkrétní využití převodu soustavy lin. rekurentních vztahů na nekonečnou matici
(Budu psát stručně, ale co není jasné, dodatečně vysvětlím)

Jsme v situaci "Výchozí situace" (#387)

Máme tedy soustavu lineárních diferenčních rovnic (1)
a(n) = c(1,j)a(n-1) + c(2,j)a(n-2) + ... c(k,j)a(n-k)

soustavu převedeme na nekonečnou matici C = ( c(i,j) )
("c" v matici neodpovídají těm ve vztahu (1) )
Matice je celá nulová kromě pruhu nad diagonálou.

Nyní se položme na otázku: v konečné dimenzi matice M definuje vztahem f(x)=Mx homomorfismus. Platí to i pro naši nekonečnou matici?
Platí, a to především díky tomu, že v každém řádku matice C je pouze konečný počet nenulových členů.
Můžeme tedy směle prohlásit, že množina všech řešení soustavy (1) odpovídá množině vektorů x, pro které Cx=0.
Nalézt všechna řešení soustavy (1) tedy znamená nalézt jádro homomorfismu f(x)=Cx
(V tomto odstavci jsem jenom trochu přesněji zopakoval #393 , ale nyní ukážu, že analogie vyjádřená v minulém řádku má i přímé uplatnění:

Úloha 1: řešení soustavy (1) tvoří vektorový prostor. Jaká je jeho dimenze?

Hledáme dimenzi jádra homomorfismu Cx.
Když se na matici C podíváme zkušeným okem, vypadá to, že
její "hodnost" je "nekonečno - (k-1)" a
její defekt (dimenze jádra) je k-1.
Ale nyní musíme tuto úvahu formalizovat:
Vezmeme homomorfismus, který odpovídá konečné submatici C' matice C, kterou tvoří počátek nejhornějšího (nultého) řádku matice C:
C'= ( c(0,0) c(1,0) .................. c(k,0))   
( c(k,0) je nenulové )
Aparát, který známe z konečných homomorfismů a jejich matic nám říká, že
- hodnost matice C' je 1.
- a proto dimenze jádra homomorfismu C'x je k-1.
Nyní stačí ukázat, že dimenze jádra Cx = dimenze jádra C'x : k tomu nám stačí nalézt izomorfismus mezi oběma jádry: zobrazení získáme tak, že z každé posloupnosti, která leží v jádru Cx, odstraníme vše až na prvních k-1 členů; pak ukážeme, že toto zobrazení je izomorfismem.


Úloha 2: Jak vypadá množina řešení soustavy s pravou stranou? (tj. lineární soustava rekurentních vzorců (1) má navíc konstatní členy)

aparát o homomorfismech nám okamžitě dává:
je-li {z(n)} řešení soustavy s pravou stranou, je množinou všech řešení
{z(n)} + <jádro příslušné homogenní soustavy>
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

Re:Je titul potřebný pro praxi?
« Odpověď #432 kdy: 17. 05. 2015, 21:33:49 »
Moc jsem nad tím ještě nedumal, ale není trochu "zvláštní", že určuješ hodnost matice, u které neznáš koeficienty? Pokud by dané rovnice určovaly posloupnost jednoznačně, tak je dimenze prostoru řešení nulová, ne?

Re:Je titul potřebný pro praxi?
« Odpověď #433 kdy: 17. 05. 2015, 21:59:08 »
Koeficienty do jisté míry znám: vím, že ten poslední koeficient v každém řádku je nenulový
Rovnice neurčují posloupnost jednoznačně.
Filip Jirsák: "Úplně stejně se ale jedná o podvod, když uživatel zamlčí provozovateli webu, že blokuje reklamu."

Re:Je titul potřebný pro praxi?
« Odpověď #434 kdy: 17. 05. 2015, 22:02:34 »
Máme tedy soustavu lineárních diferenčních rovnic (1)
a(n) = c(1,j)a(n-1) + c(2,j)a(n-2) + ... c(k,j)a(n-k)

soustavu převedeme na nekonečnou matici C = ( c(i,j) )
("c" v matici neodpovídají těm ve vztahu (1) )
Matice je celá nulová kromě pruhu nad diagonálou.

No tak nulová kromě pruhu nad diagonálou rozhodně není, leda tak pro j=1.