SES School, Studie en Onderwijs
Wiskunde in de brugklas, Frans voor het examen of een studie Personeel en Arbeid? Moeilijke formulieren van DUO? Iets weten over studiefinanciering of studentenverenigingen? Dit is het forum voor leerkrachten, scholieren en studenten, van brugklas tot uni
k had 8,6 voor me herkansing visual basic en een 8,5 voor mijn opdracht (spelletje).. he he bedankt allemaal..vooral : glowmouse.
verlegen :)
Welke studie doe je eigenlijk?quote:Op dinsdag 11 juli 2006 19:36 schreef teletubbies het volgende:
k had 8,6 voor me herkansing visual basic en een 8,5 voor mijn opdracht (spelletje).. he he bedankt allemaal..vooral : glowmouse.
Welke studie doe je eigenlijk?
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
Ik heb ook een vraag met betrekking tot mijn afstuderen. Kent iemand een website oid waarbij je postcodes in Nederland kunt vullen en waarbij het programma een optimale route genereert? Ik heb alleen nog sites gevonden waar je afstanden van het ene naar het andere punt kan berekenen, maar geen complete routes.
Alvast bedankt!
Alvast bedankt!
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.
Nee, want dat is alleen voor 2 punten en niet zeg voor 10 punten waar je dan een optimale route van maakt.
Oh, dat is het handelsreizigerprobleem, dat is helemaal niet eenvoudig (NP-moeilijk), en ik zou verbaasd zijn dat dat te vinden is op het net (dat kost veel rekenkracht namelijk, zelfs in het Euclidische geval).
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.
Ja dat bedoel ik...er zijn wel programmatjes op internet te vinden hoor: zoiets bijvoorbeeld: http://www.math.uu.nl/people/beukers/anneal/anneal.html
maar zoek eigenlijk iets waar je op een systematische manier zelf locaties kan invullen.
maar zoek eigenlijk iets waar je op een systematische manier zelf locaties kan invullen.
De vraag is hier: wat is systematisch? Wil je alle mogelijkheden afgaan (wat bij meer dan een handvol steden erg lastig wordt), kun je het beste eerst een afstandstabel maken. Ook wanneer je van een algoritme gebruik maakt, zul je zo'n afstandstabel nodig hebben. Ik denk eigenlijk niet dat websites erop zitten te wachten zo'n tabel te genereren bij erg veel plaatsen. Je zou dan kunnen kijken of je een bestaande routeplanner hiervoor in kunt zetten.
Ik denk overigens niet dat er een website is die jou zelf de TSP tour geeft aan de hand van een aantal plaatsen. De benodigde rekencapaciteit daarvoor zou te groot zijn om zo'n site rendabel in de lucht te houden.
leesvoer
Ik denk overigens niet dat er een website is die jou zelf de TSP tour geeft aan de hand van een aantal plaatsen. De benodigde rekencapaciteit daarvoor zou te groot zijn om zo'n site rendabel in de lucht te houden.
leesvoer
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
dit jaar me propedeuse (hbo) bedrijfswiskunde behaald.. nu ga ik wisk. studeren op univ.quote:
verlegen :)
ergens staat er een afstudeerscriptie over dit soort optimale oplossingen...
trefwoorden: het algoritme van Dijkstra..
een programma..ken ik echt niet
trefwoorden: het algoritme van Dijkstra..
een programma..ken ik echt niet
verlegen :)
Dijkstra werkt niet zo. Dijkstra vindt het korste pad tussen twee punten. Niet het kortste pad dat een willekeurig groot aantal punten aandoet. Dat is wat anders. Stel, je weet al wat de volgorde van de punten is, b.v. ABCD, dan kun je Dijkstra doen van A naar B, van B naar C, en van C naar D. Dat is allemaal te doen.quote:Op dinsdag 11 juli 2006 22:01 schreef teletubbies het volgende:
ergens staat er een afstudeerscriptie over dit soort optimale oplossingen...
trefwoorden: het algoritme van Dijkstra..
een programma..ken ik echt niet
Als je die volgorde niet weet, dan moet je een voor een proberen: ABCD, en dan 3x korste pad doen, of wellicht ACBD, of wellicht ACDB, of, en zo voort. Nu zijn daar wel heuristieken voor, maar het is wel verdomd rekenintensief voor veel plaatsen.
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.
een vraagje waarom zit 3/4 in cantor-verzameling?
er geldt wel dat 3/4=2/3(1+1/9+1/81+..) (trouwens valt ditmatie ook te bewijzen?
k heb gestopt bij:
sommatie (n=1 tot oneindig) 1/3^n=1 (why?)
en als de som is 1,
3/4 zit wel in [2/3, 1] dat is logisch....
er geldt wel dat 3/4=2/3(1+1/9+1/81+..) (trouwens valt ditmatie ook te bewijzen?
k heb gestopt bij:
sommatie (n=1 tot oneindig) 1/3^n=1 (why?)
en als de som is 1,
3/4 zit wel in [2/3, 1] dat is logisch....
verlegen :)
3/4 = 9/12, dus het punt 3/4 ligt op 1/4 deel van het laatste interval [2/3, 1]=[8/12,12/12]. Evenzo ligt 1/4 op 3/4 van het interval [0,1/3]. Bij elke iteratie ligt het punt dus in een interval dat overblijft. Het zit dus in de Cantor verzameling.quote:Op donderdag 13 juli 2006 21:19 schreef teletubbies het volgende:
een vraagje waarom zit 3/4 in cantor-verzameling?
er geldt wel dat 3/4=2/3(1+1/9+1/81+..) (trouwens valt ditmatie ook te bewijzen?
k heb gestopt bij:
sommatie (n=1 tot oneindig) 1/3^n=1 (why?)
en als de som is 1,
3/4 zit wel in [2/3, 1] dat is logisch....
1 + x + x2 + ... + xn = (1-xn+1)/(1-x), vervolgens neem je n naar oneindig.quote:Op donderdag 13 juli 2006 21:19 schreef teletubbies het volgende:
een vraagje waarom zit 3/4 in cantor-verzameling?
er geldt wel dat 3/4=2/3(1+1/9+1/81+..) (trouwens valt ditmatie ook te bewijzen?
k heb gestopt bij:
sommatie (n=1 tot oneindig) 1/3^n=1 (why?)
en als de som is 1,
3/4 zit wel in [2/3, 1] dat is logisch....
voor dat getal was het inderdaad niet zo moeilijk, voor andere getallen moest ik ze blijkbaar schrijven in een ander getalstelsel ( met basis 3)
eigenlijk was het de som van 1/9^n (n=1 tot oneindig)
eigenlijk was het de som van 1/9^n (n=1 tot oneindig)
verlegen :)
Je kunt aan de schrijfwijze van een getal in het 3-tallig stelsel zien of het in de cantorverzameling zit. Grofweg komt het erop neer dat de getallen in de cantor verzameling de getallen zijn die geen enen hebben in de drietallige schrijfwijze.quote:Op vrijdag 14 juli 2006 15:57 schreef teletubbies het volgende:
voor dat getal was het inderdaad niet zo moeilijk, voor andere getallen moest ik ze blijkbaar schrijven in een ander getalstelsel ( met basis 3)
eigenlijk was het de som van 1/9^n (n=1 tot oneindig)
Je moet hierbij wel even goed kijken wat er op de randpunten van de intervallen gebeurt en dus even de precieze definitie van de cantorverzameling erbij pakken: zit 1/3=0.1 er wel of niet in? Bovendien moet je even oppassen dat de schrijfwijze niet altijd uniek is: 0.2=0.1222222222222... . Als je met die details rekening houdt kun je wel een goede formulering vinden.
Ik loop tegen de volgende situatie aan. Ik heb een deel van een cirkel de volgende gegevens.
x,y van A beginpunt (ergens op de cirkel)
x,y van B eindpunt (ergens op de cirkel)
hoogte van de cirkelboog t.o.v. de lijn tussen A en B
Kan ik op basis van deze gegevens de coordinaten van het middelpunt bepalen?
excuses voor eigen topic openen ipv hierin posten
x,y van A beginpunt (ergens op de cirkel)
x,y van B eindpunt (ergens op de cirkel)
hoogte van de cirkelboog t.o.v. de lijn tussen A en B
Kan ik op basis van deze gegevens de coordinaten van het middelpunt bepalen?
excuses voor eigen topic openen ipv hierin posten
Ja, als C het snijpunt is van de cirkel met de middelloodlijn van A en B, dan gaan de middelloodlijnen van AB, BC en CA door 1 punt en dat punt is het middelpunt van de cirkel.
Hey ja! Ik heb het even uitgetekend en het klopt ja Best simpel dus! Bedankt!quote:Op woensdag 19 juli 2006 16:33 schreef thabit het volgende:
Ja, als C het snijpunt is van de cirkel met de middelloodlijn van A en B, dan gaan de middelloodlijnen van AB, BC en CA door 1 punt en dat punt is het middelpunt van de cirkel.
Best simpel dus! Bedankt!
Ff snel een korte vraag:
10 knikkers, 9 wit en 1 rood.
Hoe reken je dan ook alweer de kans uit dat je met 10x pakken met terugleggen de rode te pakken krijgt? (Maakt niet uit of dat de eerste poging is of de achtste).
Tis iets met 1 boven tien enzo maar 4 jaar geen wiskunde na eindexamen helpt niet
10 knikkers, 9 wit en 1 rood.
Hoe reken je dan ook alweer de kans uit dat je met 10x pakken met terugleggen de rode te pakken krijgt? (Maakt niet uit of dat de eerste poging is of de achtste).
Tis iets met 1 boven tien enzo maar 4 jaar geen wiskunde na eindexamen helpt niet
Wees iets nauwkeuriger, gaat het om precies één keer de rode, of om minstens één keer?quote:Op donderdag 20 juli 2006 11:04 schreef DaFan het volgende:
Ff snel een korte vraag:
10 knikkers, 9 wit en 1 rood.
Hoe reken je dan ook alweer de kans uit dat je met 10x pakken met terugleggen de rode te pakken krijgt? (Maakt niet uit of dat de eerste poging is of de achtste).
Tis iets met 1 boven tien enzo maar 4 jaar geen wiskunde na eindexamen helpt 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.
Minstens Het gaat er gewoon om dat je in ieder geval een keer een rode pakt.quote:Op donderdag 20 juli 2006 11:32 schreef Iblis het volgende:
[..]
Wees iets nauwkeuriger, gaat het om precies één keer de rode, of om minstens één keer?
Het gaat er gewoon om dat je in ieder geval een keer een rode pakt.
((-1+i)t + (-1-i)t)/2 = 2t/2 * cos(3/4 * pi*t)
Het linkerlid heb ik, en ik wil naar het rechterlid toe. De machten heb ik omgeschreven naar een sommatie met een binomiaalcoefficient. De factor (-1)t-k kan ik dan buiten haakjes halen, zodat ik ik en (-i)k nog moet sommeren. Dit komt neer op ek*pi*i/2 + e-k*pi*i/2, wat via Euler gelijk en wat goniometrie om te schrijven is naar 2*cos(k*pi/2). Verder kom ik nog niet, en ik weet ook niet of deze weg naar het rechterlid leidt. Heeft iemand een hint?
Het linkerlid heb ik, en ik wil naar het rechterlid toe. De machten heb ik omgeschreven naar een sommatie met een binomiaalcoefficient. De factor (-1)t-k kan ik dan buiten haakjes halen, zodat ik ik en (-i)k nog moet sommeren. Dit komt neer op ek*pi*i/2 + e-k*pi*i/2, wat via Euler gelijk en wat goniometrie om te schrijven is naar 2*cos(k*pi/2). Verder kom ik nog niet, en ik weet ook niet of deze weg naar het rechterlid leidt. Heeft iemand een hint?
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
Als ik een set van N getallen heb, kan ik ze sorteren in O(n log n).
Dit is te bewijzen door naar de uitvoer te kijken. Het sorteeralgoritme kan zo kort mogelijk worden opgeschreven door een permutatie. Van elk element moet worden aangegeven naar welke positie het verschuift. Er zijn n mogelijke posities, die kan ik dus in 2log(n) weergeven. Doe dat n keer en je komt aan O(n log n).
Omdat elk sorteeralgoritme op z'n minst de uitvoer moet geven, hoe het algoritme ook tewerk gaat, is een sorteerprogramma minimaal O(n log n).
Omdat er een sorteeralgoritme van O(n log n) beschikbaar is, is de orde dus ook precies n log n.
Zo'n ondergrens is niet altijd makkelijk te geven. Een voorbeeld van zo'n probleem is het P=?NP-probleem.
Maar nu mijn vraag: stel ik heb een set van N getallen, en ik wil controleren of er dubbelen inzitten.
Er is een algoritme dat dit in O(n log n) stappen doet. Algoritme: sorteer eerst de verzameling en ga hem vervolgens lineair af. Dit is O(n log n)+O(n)=O(n log n) stappen. Het is eenvoudig om een snellere versie te krijgen, maar de orde verminderen valt vies tegen.
Hoe bewijs je dat een algoritme om dubbelen te zoeken minimaal O(n log n) is? Of is er stiekem toch nog een sneller algoritme dat ik over het hoofd zie?
Dit is te bewijzen door naar de uitvoer te kijken. Het sorteeralgoritme kan zo kort mogelijk worden opgeschreven door een permutatie. Van elk element moet worden aangegeven naar welke positie het verschuift. Er zijn n mogelijke posities, die kan ik dus in 2log(n) weergeven. Doe dat n keer en je komt aan O(n log n).
Omdat elk sorteeralgoritme op z'n minst de uitvoer moet geven, hoe het algoritme ook tewerk gaat, is een sorteerprogramma minimaal O(n log n).
Omdat er een sorteeralgoritme van O(n log n) beschikbaar is, is de orde dus ook precies n log n.
Zo'n ondergrens is niet altijd makkelijk te geven. Een voorbeeld van zo'n probleem is het P=?NP-probleem.
Maar nu mijn vraag: stel ik heb een set van N getallen, en ik wil controleren of er dubbelen inzitten.
Er is een algoritme dat dit in O(n log n) stappen doet. Algoritme: sorteer eerst de verzameling en ga hem vervolgens lineair af. Dit is O(n log n)+O(n)=O(n log n) stappen. Het is eenvoudig om een snellere versie te krijgen, maar de orde verminderen valt vies tegen.
Hoe bewijs je dat een algoritme om dubbelen te zoeken minimaal O(n log n) is? Of is er stiekem toch nog een sneller algoritme dat ik over het hoofd zie?
Dat hangt ook af van welke waarden je getallen aan kunnen nemen. Als het bijvoorbeeld om gehele getallen tussen 0 en 100 gaat, kun je makkelijk bij houden of je een getal al hebt gehad door middel van een array. De complexiteit van het algoritme wordt dan O(n) tijd.quote:Op maandag 31 juli 2006 15:37 schreef Pie.er het volgende:
Hoe bewijs je dat een algoritme om dubbelen te zoeken minimaal O(n log n) is? Of is er stiekem toch nog een sneller algoritme dat ik over het hoofd zie?
Het zou me op zich niet zo veel verbazen als er een algoritme bestaat dat, zonder gebruik te maken van een speciale data structuur, beter is dan O(n log n). Intuitief gezien is sorteren veel bewerkelijker dan het vinden van twee dezelfde getallen.
Het gaat om N elementen, dus zou je bijectie kunnen maken naar een reeks gehele getallen. Het probleem zit hem alleen in die array: ongesorteerd moet je het k-de element vergelijken met de k-1 elementen uit de array. Volgens mij zit je dan met een process van orde n².quote:Op maandag 31 juli 2006 19:11 schreef Wolfje het volgende:
[..]
Dat hangt ook af van welke waarden je getallen aan kunnen nemen. Als het bijvoorbeeld om gehele getallen tussen 0 en 100 gaat, kun je makkelijk bij houden of je een getal al hebt gehad door middel van een array. De complexiteit van het algoritme wordt dan O(n) tijd.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
Hmm.. nee, ik had een boolean array in gedachten. Als alle getallen tusen 0 en 100 (inclusief) liggen, krijg je iets als:quote:Op maandag 31 juli 2006 19:42 schreef GlowMouse het volgende:
[..]
Het gaat om N elementen, dus zou je bijectie kunnen maken naar een reeks gehele getallen. Het probleem zit hem alleen in die array: ongesorteerd moet je het k-de element vergelijken met de k-1 elementen uit de array. Volgens mij zit je dan met een process van orde n².
| 1 2 3 4 5 6 7 8 | boolean[] inVerzameling = new boolean[101]; for ( int i = 0; i < a.length; i++ ) { if ( inVerzameling[ a[ i ] ] ) return true; inVerzameling[ a[ i ] ] = true; } return false; } |
Hmm ja inderdaad. In mijn geval ging het om willekeurige integers, dus zou de opslag een oneindige array worden, maar dat is theoretisch geen enkel probleem.quote:Op maandag 31 juli 2006 20:13 schreef Wolfje het volgende:
[..]
Hmm.. nee, ik had een boolean array in gedachten. Als alle getallen tusen 0 en 100 (inclusief) liggen, krijg je iets als:
[ code verwijderd ]
Deze methode is O(n). Elke methode moet minimaal de invoer lezen, dat kost al O(n) bewerkingen, dus heeft deze methode minimale orde. Dank!
Meer geheugen dan tijd gebruiken lijkt me toch niet helemaal de bedoeling. Overigens zie ik ook niet hoe het sneller kan dan O(n log n), al zie ik ook niet direct hoe je dat kunt bewijzen.
Overigens is het ook een beetje raar om te stellen dat het in O(n log n) tijd wel kan, want de getallen kunnen heel groot zijn. Je kunt 2 getallen niet in O(1) tijd met elkaar vergelijken. De juiste manier om de grootte van de invoer te meten is dan ook niet het aantal getallen maar de functie max(1,log |x|) gesommeerd over alle getallen.
[ Bericht 0% gewijzigd door thabit op 01-08-2006 19:21:27 ]
[ Bericht 0% gewijzigd door thabit op 01-08-2006 19:21:27 ]
Niet de bedoeling nee. Maar omdat er een tegenvoorbeeld is dat sneller dan O(n log n) is, hoe idioot veel geheugen er ook gebruikt wordt, weet ik dat ik geen bewijs ga vinden voor O(n log n) als ondergrens als ik geen geheugenoverwegingen meeneem.quote:Op dinsdag 1 augustus 2006 11:20 schreef thabit het volgende:
Meer geheugen dan tijd gebruiken lijkt me toch niet helemaal de bedoeling. Overigens zie ik ook niet hoe het sneller kan dan O(n log n), al zie ik ook niet direct hoe je dat kunt bewijzen.
En ik ga uit van een programmeertaal waarin twee getallen in 1 operatie met elkaar vergeleken kunnen worden. Dat dit in werkelijkheid wellicht niet zo is maakt niet veel uit voor de theorie
Ik neem aan dat initialisatie van geheugen ook tijd kost? En al zou dat niet zo zijn, dat je in elk geval een eindige hoeveelheid geheugen gebruikt? Waarom enerzijds gebruiken dat natuurlijke getallen willekeurig groot kan zijn, zodat de 'tabelmethode' niet werkt en anderzijds gebruiken dat ze begrensd zijn zodat ze in constante tijd met elkaar vergeleken kunnen worden? Er zijn trouwens denk ik wel probabilistische methodes te bedenken die bij elke input in O(n) verwachte operaties het kunnen bepalen. Is dat een probleem of moet het per se deterministisch zijn?quote:Op donderdag 3 augustus 2006 09:44 schreef Pie.er het volgende:
[..]
Niet de bedoeling nee. Maar omdat er een tegenvoorbeeld is dat sneller dan O(n log n) is, hoe idioot veel geheugen er ook gebruikt wordt, weet ik dat ik geen bewijs ga vinden voor O(n log n) als ondergrens als ik geen geheugenoverwegingen meeneem.
En ik ga uit van een programmeertaal waarin twee getallen in 1 operatie met elkaar vergeleken kunnen worden. Dat dit in werkelijkheid wellicht niet zo is maakt niet veel uit voor de theorie
Ja die geheugeninitialisatie daar zat ik ook nog mee. Maar in Wolfjes code kwamquote:Op donderdag 3 augustus 2006 09:52 schreef thabit het volgende:
[..]
Ik neem aan dat initialisatie van geheugen ook tijd kost? En al zou dat niet zo zijn, dat je in elk geval een eindige hoeveelheid geheugen gebruikt? Waarom enerzijds gebruiken dat natuurlijke getallen willekeurig groot kan zijn, zodat de 'tabelmethode' niet werkt en anderzijds gebruiken dat ze begrensd zijn zodat ze in constante tijd met elkaar vergeleken kunnen worden? Er zijn trouwens denk ik wel probabilistische methodes te bedenken die bij elke input in O(n) verwachte operaties het kunnen bepalen. Is dat een probleem of moet het per se deterministisch zijn?
| 1 |
zo overtuigend over als dat het ook automatisch waarde false heeft (zoals blijkt uit de rest van de code) dat ik voorlopig aannam dat het, op een slimme manier die ik niet snap, wel kon.
Mijn doel was determinisme.
Maar zou je, zonder oneindig geheugen en met de aanname dat twee getallen in 1 operatie met elkaar te vergelijken zijn, een idee hebben voor een methode die sneller dan O(n log n) is?
Of een idee voor een bewijs dat zoiets niet mogelijk is?
Overigens heeft een Turing-machine een oneindig geheugen. Zet 'rechts' alle invoer, (neem aan dat alle getallen positief zijn of voeg anders een tekencodering toe), en gebruik 'links' als opslaggeheugen. Dan is het, met Wolfjes code vertaald naar Turing (een hels gedoe) mogelijk. Toch?
Nee, ik heb er wel even over nagedacht, maar zie het allebei toch niet echt direct. Al lijkt het me heel sterk dat het sneller zou kunnen dan O(n log n). Een andere manier dan sorteren, die ook O(n log n) is, is de lijst aflopen en opslaan in een gebalanceerde boom ipv een tabel. Maar helaas zijn de operaties in een gebalanceerde boom ook O(log n).quote:Op donderdag 3 augustus 2006 10:17 schreef Pie.er het volgende:
[..]
Maar zou je, zonder oneindig geheugen en met de aanname dat twee getallen in 1 operatie met elkaar te vergelijken zijn, een idee hebben voor een methode die sneller dan O(n log n) is?
Of een idee voor een bewijs dat zoiets niet mogelijk is?
Ik denk trouwens wel dat het probleem makkelijker wordt als je het meet in bitoperaties (dus rekening houdt met het feit dat vergelijken van grote getallen ook langer duurt). Het is immers de grootte van de getallen die het lastig maakt, en daar kun je op deze manier juist beter rekening mee houden. Bovendien krijg je hiermee ook een betere schatting van de werkelijke looptijd.
