abonnement Unibet Coolblue Bitvavo
  zaterdag 19 december 2009 @ 14:12:17 #44
75592 GlowMouse
l'état, c'est moi
pi_75803313
Iblis heeft het over een a priori bekende bound, bedenk maar eens waarom het dan makkelijk wordt

Jouw 'oplossing' is niet goed, je ziet zelf dat het al fout gaat bij een groot getal.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75803499
quote:
Op zaterdag 19 december 2009 14:12 schreef GlowMouse het volgende:
Iblis heeft het over een a priori bekende bound, bedenk maar eens waarom het dan makkelijk wordt

Jouw 'oplossing' is niet goed, je ziet zelf dat het al fout gaat bij een groot getal.
Er zullen vast wel meer bounds zijn waardoor het makkelijk wordt om een lineaire oplossing te bedenken. Als je weet dat de getallen natuurlijke getallen zijn (zoals in dit geval) ook, dus ksnap niet precies wat je bedoelt.

Het kan veel geheugen kosten maar in theorie gaat dit goed hoor, en er werd volgens mij niet gevraagd om rekening te houden met het geheugen. Kan je iets concreter vertellen wat er volgens jou dan mis gaat -.-
  zaterdag 19 december 2009 @ 14:22:46 #46
75592 GlowMouse
l'état, c'est moi
pi_75803541
Je moet kijken naar de verwerkingstijd als functie van je input. In jouw functie is die exponentieel, want om een groot getal K in te voeren kost dat mij log(K) stapjes terwijl de geheugenallokatie K stapjes kost.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
  zaterdag 19 december 2009 @ 14:26:22 #47
147503 Iblis
aequat omnis cinis
pi_75803623
De bound komt dan sowieso niet te liggen bij de lengte van de input maar bij de maximale waarde van de getallen in de input. Of je nu rijen van 2 of rijen van 10.000 wil vergelijken, je hoofdprobleem zal waarschijnlijk zijn – op een 64-bits machine b.v. – een array van 264 booleans te alloceren.

Overigens, wat Optimistic1 doet, is simpelweg de input hashen. En in feite kan dat algemener. En dan kun je – met random data – wel een in de praktijk lineaire oplossing krijgen. Maar de vraag is dus even of je worst-case wilt gaan zitten analyseren of niet.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
pi_75806029
quote:
Op zaterdag 19 december 2009 14:22 schreef GlowMouse het volgende:
Je moet kijken naar de verwerkingstijd als functie van je input. In jouw functie is die exponentieel, want om een groot getal K in te voeren kost dat mij log(K) stapjes terwijl de geheugenallokatie K stapjes kost.
In de praktijk kan je hierop letten, maar om de orde van n te bepalen hoef je niet te letten op maximumgetal K en kdenk dat Optimistic bedoelde dat hij de laagste orde n wou. De oplossing die ik in mn post noemde is overigens ook geaccepteerd als oplossing (als n dichtbij K zit), alleen wordt hij nauwelijks gebruikt -.-

Wat Iblis zegt kan mis gaan (ook al kom je in de praktijk niet altijd tegen dat je getallen groter dan 2^64 moet verwerken) waar ingewikkelde oplossingen voor zijn (met nog meer trees en arrays), dus daar gaan we niet aan beginnen -.- Daarom kan Optimistic maar beter zoiets zeggen (wat in de vorige posts al beetje gezegd is, maar het algoritme is nog niet echt gegeven):
- Beide lijsten sorteren (via merge-sort heb je uiteindelijk de laagste orde, namelijk O(n log(n)), maar quick-sort is in de praktijk sneller maar heeft worst-case O(n^2)).
- Neem telkens het minimum van de twee gesorteerde lijsten en kijk of hij overeenkomt met het minimum van de andere lijst. Zo niet, streep die weg en herhaal.
pi_75812623
De getallen die ik heb komen doordat ik een algoritme gebruik om het aantal punten op een elliptische kromme E gedefinieerd over een lichaam Fp uit te rekenen. Het algortime heeft complexiteit O(p1/4+e) en gaat als volgt:

*Kies een random punt P op de kromme E.
*Bereken de eerste s veelvouden van P, namelijk P, 2P, 3P,...,sP, waarbij s=p^(1/4) (bij mij is s ongeveer 100) en sla deze op in een lijst.
*Bereken Q:=(2*s+1)P en R=(p+1)P door binaire expansie van p+1 te gebruiken.
*Schrijf t=[sqrt(p)/(2*s+1)] (dit is een getal ongeveer gelijk aan s) en bereken
R +/-P, R+/- 2P,R+/-3P,....,R+/-tP en dit zijn 2s+1 punten. Deze sla ik weer op in een lijst.

Er is een stelling die zegt dat er een i en j bestaan met R+iQ=jP, dus er is een punt zowel in de 1e als in de 2e lijst en dat punt wil ik vinden... want als ik die vind en dus ook i en j weet..
dan kan ik weten wat het aantal punten is op mijn kromme E. Over het vinden van dit punt staat;
"It is important that one can efficiently search among the points in the
list of baby steps; one should sort this list or use some kind of hash coding.
It is not difficult to see that the running time of this algorithm is O(p1/4+e)"
http://www.mat.uniroma2.it/~schoof/ctg.pdf

Mijn idee was om dus om gebruik te maken van de x-coordinaat van de punten en die gaan onthouden.
pi_75896014
ok, ik heb alleen mn telefoont en moment tot mijn beschikkng, dus alle informatie kan ik niet geven, maar het schijnt dat je hieraan genoeg hebt:

a= 0,5(0,84a+0,4c) + 0,8c
a = 1,72

waarom wordt dit 1,72c ?
  maandag 21 december 2009 @ 20:59:55 #51
147503 Iblis
aequat omnis cinis
pi_75896439
quote:
Op maandag 21 december 2009 20:51 schreef EddyAlbena het volgende:
ok, ik heb alleen mn telefoont en moment tot mijn beschikkng, dus alle informatie kan ik niet geven, maar het schijnt dat je hieraan genoeg hebt:

a= 0,5(0,84a+0,4c) + 0,8c
a = 1,72

waarom wordt dit 1,72c ?
Als je a invult krijg je:

1,72 = 0,5(0,84·1,72 + 0,4·c) + 0,8c

Vermenigvuldig met 2:

3,44 = 0,84·1,72 + 0,4c + 1,6c
3,44 = 1,44 + 2,0c
2,00 = 2,0c
c = 1,00
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
pi_75896942
Allereerst bedankt voor je reactie.
Excuus, maar ik gaf het niet goed aan.
Uit de berekening achter A, moet 1,72C uitkomen.
Dus A=0,5(0,84a+0,4c)+0,8c

Ik hoop dat ik het zo duidelijk heb kunnen maken, zag dat ik net de c vergeten was, nog al een belangrijk verschil he :p
  maandag 21 december 2009 @ 21:16:46 #53
147503 Iblis
aequat omnis cinis
pi_75897529
Ah, ik snap wat je wilt, maar je schrijft het raar op. Wat je wilt is:

a= 0,5(0,84a+0,4c) + 0,8c

oplossen naar c. Om dat de doen, begin met vermenigvuldigen met 2:

2a= 0,84a + 0,4c + 1,6c

0,84a naar de andere kant, termen met c samenvoegen:

1,16a = 2,0c

Deel links en rechts door 1,16:

a = 1,72c
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
pi_75898318
quote:
Op maandag 21 december 2009 21:16 schreef Iblis het volgende:
Ah, ik snap wat je wilt, maar je schrijft het raar op. Wat je wilt is:

a= 0,5(0,84a+0,4c) + 0,8c

oplossen naar c. Om dat de doen, begin met vermenigvuldigen met 2:

2a= 0,84a + 0,4c + 1,6c

0,84a naar de andere kant, termen met c samenvoegen:

1,16a = 2,0c

Deel links en rechts door 1,16:

a = 1,72c
Haha yeah! Mijn dank is groot, ik snap 'm! Dit brengt mij weer een stuk verder.
Super!
pi_75906897
Er werd in een bewijs van mijn dictaat gebruik gemaakt van det(A^-1) = det(A)^-1, maar dit is nergens bewezen. Zelf heb ik geen idee hoe ik dit kan aanpakken. Hints worden op prijs gesteld .

Oh nevermind, heb het al
  dinsdag 22 december 2009 @ 00:09:35 #56
75592 GlowMouse
l'état, c'est moi
pi_75906968
gebruik det(AB)=det(A)det(B) en I=A*A^-1.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75907022
quote:
Op dinsdag 22 december 2009 00:09 schreef GlowMouse het volgende:
gebruik det(AB)=det(A)det(B) en I=A*A^-1.
Inderdaad, zag het direct nadat ik het postte
pi_75907314
Nog ééntje:

Zij T: R2 ->R2 een lineaire afbeelding met als eigenschap |Tx|=|x| voor alle x in R2. Laat zien dat T ofwel een rotatie is, of een loodrechte spiegeling.

Het lijkt zo triviaal, maar ik heb geen idee hoe ik dit zou kunnen laten zien.
  dinsdag 22 december 2009 @ 00:18:58 #59
75592 GlowMouse
l'état, c'est moi
pi_75907385
Wat doe je normaalgesproken als je absoluuttekens weg wilt hebben?
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75907442
|x|=sqrt[x12+x22]
  dinsdag 22 december 2009 @ 00:21:49 #61
75592 GlowMouse
l'état, c'est moi
pi_75907510
- nvm -

[ Bericht 80% gewijzigd door GlowMouse op 22-12-2009 00:28:46 ]
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75907742
Ik intepreteer |x| altijd als "de lengte van vector x", en wist niet dat het ook "de absolute waarde van" kon betekenen in dit verband. (ik dacht dus eigenlijk dat ik moest laten zien dat als de lengte van een vector niet veranderd na een lineaire transformatie, dat we ofwel te maken hebben met loodrechte spiegeling, of met rotatie)

Maar stel dat bedoeld word dat de absolute waarde van x behouden blijft, dan impliceert dat dat T ofwel de identiteitsmatrix is, of minus de identiteitsmatrix. In het geval dat T de identiteitsmatrix is kan je het opvatten als een rotatie van 2pi, en als het minus de identiteitsmatrix is als spiegeling of rotatie van pi (is dat hetzelfde?).

Kan me haast niet voorstellen dat dit bedoeld wordt
  dinsdag 22 december 2009 @ 00:29:08 #63
75592 GlowMouse
l'état, c'est moi
pi_75907837
Hebben we het over ||Tx|| of over |Tx| (component-wise absolute waarde)?
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75907951
quote:
Op dinsdag 22 december 2009 00:29 schreef GlowMouse het volgende:
Hebben we het over ||Tx|| of over |Tx| (component-wise absolute waarde)?
Bij lineaire algebra wordt |x| opgevat als 'de lengte van x' . ||x|| wordt daar nooit gebruikt...

Het is me nooit uitgelegd wat het verschil is tussen die twee. Ik dacht dat het een kwestie van verschillende notatie maar zelfde betekenis was.

[ Bericht 8% gewijzigd door BasementDweller op 22-12-2009 00:40:17 ]
  dinsdag 22 december 2009 @ 00:38:35 #65
75592 GlowMouse
l'état, c'est moi
pi_75908189
heb je algebraïsche eigenschappen geleerd van rotatiematrices/spiegelmatrices?
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75908294
quote:
Op dinsdag 22 december 2009 00:38 schreef GlowMouse het volgende:
heb je algebraïsche eigenschappen geleerd van rotatiematrices/spiegelmatrices?
Ik vermoed van niet.

Er is trouwens een hint:
Laat zien dat Te2 loodrecht staat op Te1

(was misschien handig geweest als ik die er direct had bij gezet, maar ik dacht misschien weet jij een andere manier, want hiermee kwam ik niet verder)
  dinsdag 22 december 2009 @ 00:46:15 #67
75592 GlowMouse
l'état, c'est moi
pi_75908450

hier heb je al dat T tranpose zijn inverse is, een van de eigenschappen van een rotatiematrix (zie http://en.wikipedia.org/wiki/Rotation_matrix ).
quote:
Op dinsdag 22 december 2009 00:41 schreef BasementDweller het volgende:

[..]

Ik vermoed van niet.

Er is trouwens een hint:
Laat zien dat Te2 loodrecht staat op Te1
Dat aantonen gaat op dezelfde manier als wat ik juist deed. Hiermee ben je klaar

[ Bericht 50% gewijzigd door motorbloempje op 01-09-2013 21:33:59 ]
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75908757
Ik snap niet wat daar gebeurt en ook niet waarom je het daarmee aantoont... in dit hoofdstuk (waar de vraag bij hoort) worden dit soort dingen niet behandeld. In een volgend hoofdstuk vind ik wel dingen die er een beetje op lijken, maar dat heb ik nog niet bestudeerd. Misschien moet ik dat eerst maar eens gaan doen....
  dinsdag 22 december 2009 @ 01:03:27 #69
75592 GlowMouse
l'état, c'est moi
pi_75909038
misschien dat morgen iemand komt die het sneller/anders ziet
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75909148
Ja.. in ieder geval bedankt voor de hulp!
pi_75909348
Ik zie nu in dat volgende hoofdstuk een stelling staan:

|Ax|=|x| => A(x) dot A(y)= x dot y

Dus omdat e1 dot e2 =0, Te1 dot Te2 = 0. Met behulp van die stelling is het dus erg eenvoudig om te laten zien dat Te2 loodrecht staat op Te1, maar heb ik daarmee dan aangetoond dat T een rotatie of een loodrechte spiegeling is? Zo ja, waarom?

[ Bericht 1% gewijzigd door BasementDweller op 22-12-2009 01:25:12 ]
  dinsdag 22 december 2009 @ 01:19:22 #72
75592 GlowMouse
l'état, c'est moi
pi_75909487
intuïtief: alles blijft even lang en er vervormt niks
Je kunt ook zeggen x=x(1)e1 + x(2)e2, dus Tx = x(1) Te1 + x(2) Te2, dus je hebt dezelfde vector maar dan tov een andere orthogonale basis.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75909679
quote:
Op dinsdag 22 december 2009 01:19 schreef GlowMouse het volgende:
intuïtief: alles blijft even lang en er vervormt niks
Je kunt ook zeggen x=x(1)e1 + x(2)e2, dus Tx = x(1) Te1 + x(2) Te2, dus je hebt dezelfde vector maar dan tov een andere orthogonale basis.
Ja, intuïtief snap ik het wel. Maar wat het loodrecht staan van de afbeeldingen van e1 en e2 te maken heeft met rotatie/loodrechte spiegeling, is me een raadsel.

Ah, ik snap het al. Als de basis loodrecht blijft na afbeelden, betekent dat dat er geen vervorming is en dan kan je alleen maar roteren of spiegelen. Niet echt een prachtig bewijs, maar ze vragen eigenlijk ook alleen maar 'laat zien' .

Oke bedankt, ik ben eruit !

(Wat ik wel slecht vind aan die opgave is dat het met die hint niet hard bewezen is, maar eigenlijk nog steeds vrij intuïtief. En dat terwijl ik het zonder die hint intuïtief ook al prima begrijp. Bovendien had ik er een stelling uit een ander hoofdstuk bij nodig... )

[ Bericht 8% gewijzigd door BasementDweller op 22-12-2009 01:36:36 ]
pi_75997823
Opnieuw een lineaire algebra vraag:

Zij A: R² -> R² een lineaire afbeelding ongelijk aan O, de nul-afbeelding. Stel M²=O.
(a) Bewijs dat dim(ker(M))=1 (dus de dimensie van de kern van M is gelijk aan 1)

Om dit te bewijzen wou ik gebruik maken van twee matrices. Matrix A heeft één getal in de rechterbovenhoek. Matrix B heeft één getal in de linkerbenedenhoek. Voor die matrices geldt A²=B²=0. Dan is het makkelijk om te te laten zien dat ker(A)= { x¤R² | x =t(1,0), voor alle t¤R} en ker(B)= { x¤R² | x= t (0,1), voor alle t¤R}. Omdat ker(A) en ker(B) één vrijheidsgraad hebben geldt: dim(ker(A))=dim(ker(B))=1.

Echter, bij vraag (c) wordt pas een voorbeeld gevraagd van een dergelijke afbeelding M. Mijn conclusie is dus dat (a) ook in het algemeen bewezen kan worden zonder gebruik te maken van Matrix A en B.

Heeft iemand enig idee hoe?
  donderdag 24 december 2009 @ 00:42:45 #75
75592 GlowMouse
l'état, c'est moi
pi_75998078
Je weet dat dim(ker(M)) 0,1 of 2 kan zijn, en 0 en 2 kun je vrij makkelijk wegstrepen (0 omdat de kolommen van m in de nulruimte zitten, 2 omdat het niet de nulmatrix is).

Maar het is ook makkelijk in te zien dat M een lineaire combinatie moet zijn van A en B, en vervolgens dat niet beide gewichten ongelijk aan 0 kunnen zijn.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75998459
quote:
Op donderdag 24 december 2009 00:42 schreef GlowMouse het volgende:
Je weet dat dim(ker(M)) 0,1 of 2 kan zijn, en 0 en 2 kun je vrij makkelijk wegstrepen (0 omdat de kolommen van m in de nulruimte zitten, 2 omdat het niet de nulmatrix is).

Maar het is ook makkelijk in te zien dat M een lineaire combinatie moet zijn van A en B, en vervolgens dat niet beide gewichten ongelijk aan 0 kunnen zijn.
Wat bedoel je er precies mee dat de kolommen van M in de nulruimte zitten?
  donderdag 24 december 2009 @ 00:55:07 #77
75592 GlowMouse
l'état, c'est moi
pi_75998601
M*[eerste kolom van M] = 0. Volgt uit M*M=O.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75999035
En omdat die kolom in de nulruimte zit is de dimensie niet 0? Ik heb erover nagedacht maar zie het verband niet
  donderdag 24 december 2009 @ 01:11:06 #79
75592 GlowMouse
l'état, c'est moi
pi_75999213
We hebben tenminste één niet-nulvector (de linker- of rechterkolom van M) die in de nulruimte(=kern) zit.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_75999381
Hehe, het kwartje is gevallen
pi_76019736
Oke, nog een lineaire algebra vraag.

Gegeven: Zij A: Rn -> Rn een lineaire afbeelding met de eigenschap A² = A.
Te bewijzen: Zij V een lineaire deelruimte van Rn. De doorsnede van ker(A) en A(V) is de verzameling bestaande uit slechts de nulvector.

Heb een hint nodig.. ik blijf dit soort opgaves lastig vinden
  donderdag 24 december 2009 @ 16:26:41 #82
75592 GlowMouse
l'état, c'est moi
pi_76020001
-

[ Bericht 100% gewijzigd door GlowMouse op 24-12-2009 16:30:18 ]
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_76020025
Neem een element v van Rn dat zowel in ker(A) als A(V) zit. Te bewijzen: v=0. Je weet: Av = 0 en er is een w met v = Aw. Nu jij weer.
pi_76020394
quote:
Op donderdag 24 december 2009 16:27 schreef thabit het volgende:
Neem een element v van Rn dat zowel in ker(A) als A(V) zit. Te bewijzen: v=0. Je weet: Av = 0 en er is een w met v = Aw. Nu jij weer.
Waarom weet ik dat Av=0 ?

Bedoel je dat je Av gelijk kan stellen aan nul omdat A een lineaire afb is?
  donderdag 24 december 2009 @ 16:38:19 #85
75592 GlowMouse
l'état, c'est moi
pi_76020511
Ligt het aan mij of heb je ook genoeg aan 'A is vierkant'?
quote:
Waarom weet ik dat Av=0 ?
je neemt aan dat hij zit in de doorsnede van ker(A) en A(V).
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
pi_76020638
quote:
Op donderdag 24 december 2009 16:38 schreef GlowMouse het volgende:
Ligt het aan mij of heb je ook genoeg aan 'A is vierkant'?
Lineaire afbeeldingen zijn niet vierkant. Maar als je n=2 neemt en A de lineaire afbeelding (x,y) -> (y,0) dan heb je een tegenvoorbeeld want (1,0) zit in zowel kern als beeld.
abonnement Unibet Coolblue Bitvavo
Forum Opties
Forumhop:
Hop naar:
(afkorting, bv 'KLB')