[Centraal] Bčta huiswerk en vragen topic

Ik zie hem, thx

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?

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?

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.

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.

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.

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

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

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

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.

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

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

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: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?

Ja die geheugeninitialisatie daar zat ik ook nog mee. Maar in Wolfjes code kwam

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?

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?

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

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.

Waarschijnlijk een hele makkelijke vraag, maar reken je met deze door mij zelf in elkaar geflanste formule nou echt goed de gemiddelde snelheid uit?

3600 gedeeld door (rijtijd in secondes gedeeld door kilometers)


* Zelva is een echte wiskunde-n00b en twijfelt maar en twijfelt maar.

Ja.

Een formule uit de natuurkunde luidt: s=v-streep * t (v-streep is v met een streepje erboven en stelt de gemiddelde snelheid voor, s is de afstand en t de tijd). Omschrijven levert v-streep = s/t.

Jouw formule uitgedrukt in de natuurkundige symbolen zegt: v-streep = 3600/(t/s). Door de teller en noemer met s te vermenigvuldigen krijg je v-streep = 3600*s/t. Als je dit vergelijkt met de bekende formule uit de natuurkunde zie je dat hij best kan kloppen.

Weer terug naar v-streep = s/t. Vul je s in kilometers t in seconden in, krijg je de snelheid in km/s. Door dit te vermenigvuldigen met 3600 krijg je de gemiddelde snelheid in km/h.

[ Bericht 12% gewijzigd door GlowMouse op 05-08-2006 21:44:36 (verkeerd herschreven :'() ]

Ik snap er nou echt helemaal niets meer van.

Klopt ie nou wel of niet?

Hij klopt, maar kan dus iets omgeschreven worden naar 3600 * kilometers / rijtijd.

hoi hoi
ik heb een site gemaakt en wil die publiceren op internet.
Het is niet moeilijk om een host tevinden.
maar de vraag is, ik wil dat als je een paar trefwoorden intypt op google ofzo dat je die site kunt vinden..

hoe zit het in elkaar?
thanx

Edit: laat maar.

quote:

Op maandag 7 augustus 2006 21:38 schreef teletubbies het volgende:
hoi hoi
ik heb een site gemaakt en wil die publiceren op internet.
Het is niet moeilijk om een host tevinden.
maar de vraag is, ik wil dat als je een paar trefwoorden intypt op google ofzo dat je die site kunt vinden..

hoe zit het in elkaar?
thanx

Nee, aan website optimaliseren doen wij hier niet sorry.

quote:

Op maandag 7 augustus 2006 21:38 schreef teletubbies het volgende:
hoi hoi
ik heb een site gemaakt en wil die publiceren op internet.
Het is niet moeilijk om een host tevinden.
maar de vraag is, ik wil dat als je een paar trefwoorden intypt op google ofzo dat je die site kunt vinden..

Het belangrijkste is dat je goede content hebt, en veel andere sites naar je linken. In dit Tweakers.net topic staan enkele tips genoemd. Door op SEO te googlen kom je waarschijnlijk meer tips tegen.

Denk dat dit een hele stomme vraag is maar kan t echt nergens vinden:

Om me voor te bereiden op mn universitaire studie ben ik mn wiskunde aan t ophalen.
Vroeger nooit iets met Grafische Rekenmachines moeten doen dus dat eerst maar eens aan t uitzoeken.

Mijn vraag is de volgende:

Hoe voer je breuken in op de Grafische rekenmachine? 1/3 enzo lukt me wel maar als t nou 1 2/3 is? Spaties worden volgens mij niet gebruikt? Ik heb de TI83.

Alvast heel erg bedankt, dan kan ik weer verder leren!

Je kan doen (als het 1 2/3 is):

1+2/3, en dan naar Math -> >Frac.
Dan krijg je als uitkomst 5/3.

Er is ook nog een andere methode meen ik me te herinneren. Ik kijk ff voor je verder nog (Tis voor mij ook al lang geleden).

Edit: Verder kom ik helaas niet.