Archiv verlassen und diese Seite im Standarddesign anzeigen : Uni-Aufgabe wirkt unverständlich+mögliche Lösung inside
Hallo,
Ich muss eine Aufgabe lösen. Ich habe die vermeintliche Lösung. Ich wollte nur mal Rat bei euch einholen, ob ich denn die Aufgabe korrekt verstanden haben, denn dann stimmt auch meine Lösung dazu:
http://666kb.com/i/b96uyq2cr281ab73z.gif
Die Aufgabe ist ziemlich mathematisch theoretisch forumliert. Ich habe es mir dann mal praxisnah übersetzt. Das Magnetband ist ein Array mit n Feldern. Die Programmlängen sind als Elemente im Array gespeichert:
Bsp: 99 5 6 8 16 9; 6 Elemente, also 6 Programme
Ich sehe am Beispiel ja schon direkt, dass die Laufzeit entsprechend lang sein wird, bis ich endlich mal ein Programm und weitere gefunden habe, weil das erste Programm so lang ist (99).
Nun dachte ich mir, entwickle ich einfach einen "gierigen" Algorithmus, der einfach nach dem kleinsten Länge im Array sucht dieser mit der aktuellen Position (Feld Index) austauscht. Danach wird die aktuelle Position erhöht und das ganze geht genau wieder von vorne los. Nun ja, was soll ich sagen, dass ist nichts anderes als Selectionsort.
Wenn erstmal das Magnetband so umsortiert wurde, dann habe ich die mittlere Laufzeit wohl minimiert, da ich danach 5 6 8 9 16 99 habe. Gehe ich hier wieder sequentielle durchs Band, habe ich ja in weniger Zeit schon um 4 Programme gefunden.
Also Leute, ist das nun korrekt, oder habe ich die Aufgabe vercheckt?
die mittlere Zeit zum Auffinden eines Programmes hat sich aber nicht verändert
oh man noch viel zu früh :D - die Heuristik ist ok :)
nur als Hinweis: eine Heuristik findet nicht zwingendermaßen das Optimum, es ist nur eine Strategie
Wenn erstmal das Magnetband so umsortiert wurde, dann habe ich die mittlere Laufzeit wohl minimiert, da ich danach 5 6 8 9 16 99 habe. Gehe ich hier wieder sequentielle durchs Band, habe ich ja in weniger Zeit schon um 4 Programme gefunden.
ich würde es über den Erwartungswert begründen, also Minimierung von (Summe von j=1 bis n über Summe von k=1 bis j von (l_ik))/n
als Beispiel, angegeben sind die l_ik
8 5 1
mittlere Zeit zum Auffinden bei Annahme einer Gleichverteilung der Programme: (8+(8+5)+(8+5+1))/3=35/3
sortiert: 1 5 8
(1+(1+5)+(1+5+8))/3=21/3
WarSlash
2009-05-24, 18:05:54
So, ich war der Gast. Hatte Password für Mail-Account verschludert.
@Pest:
Meinst es auch legetim so zu begründen, wie ich das vorhatte, also mit der Laufzeit, die danach viel kürzer ist, weil man jetzt eine Mininumsortierung hat?
Aber Eigenwert beweist es ja schon recht gut! Icvh weiß halt nicht, wie es den Leute in der Uni recht machen soll.;D
Meinst es auch legetim so zu begründen, wie ich das vorhatte, also mit der Laufzeit, die danach viel kürzer ist, weil man jetzt eine Mininumsortierung hat?
ja klar, ich würde es nur ein wenig formaler machen
deine optimierungsaufgabe heißt ja (ich habe das /n weggelassen weil es die lösung nicht verändert)
http://www.abload.de/img/formel1azz7.png
und das ist genau dann der fall wenn die l_ik nach nicht fallenden werten sortiert sind
Aber Eigenwert beweist es ja schon recht gut!
erwartungswert ;) = mittlere zeit zum auffinden eines programmes
Pinoccio
2009-05-24, 21:00:04
Intuitiv ist ja irgendwie klar, daß eine Sortierung nach Programmlänge (kürzestes zuerst) das Ziel ist.
Eine saubere* Begründung scheint mir aber schwierig.
* I. S. v. komplizierter Sprache auf Niveau der Aufgabenstellung. Aber so werden Aufagbentexte wohl, wenn sich Generationen von Studenten an einfachen So-war-das-aber-nicht-gemeint-Lösungen versuchen.
mfg
Intuitiv...komplizierter Sprache auf Niveau der Aufgabenstellung.
mir fällt da jetzt auch nix gescheites mehr ein, btw. in meiner grafik steht ja alles
man kann jetzt anfangen das noch zu zerlegen und zum ausdruck bringen
das bei einer sortierung kleinere partialsummen entstehen...
Spasstiger
2009-05-24, 21:51:13
Eine Sortierung nach aufsteigender Programmlänge ist nicht unbedingt optimal. Man müsste eigentlich die Zugriffshäufigkeit für jedes Programm kennen.
Wenn man z.B. zwei Programme hat mit den Längen 1 und 10, aber auf das Programm der Länge 10 hundertmal so häufig zugegriffen wird, ist eine Sortierung (1 10) für die mittlere Zugriffszeit schlechter als eine Sortierung (10 1).
Bei der Sortierung (1 10) und einem hundertmal so häufigen Zugriff auf das lange Programm ergibt sich folgende mittlere Zeit für das Auffinden (und Lesen) des Programms:
(1*1 + 100*(1 + 10)) / 101 = 10,9
Bei der scheinbar ungünstigen Sortierung (10 1) sieht es so aus:
(100*10 + 1*(10 + 1)) / 101 = 10,0
Ohne eine Kenntnis der Zugriffsstatistik kann man also keine optimale Sortierung vornehmen. Man kann höchstens Annahmen treffen wie es pest getan hat (Normalverteilung Gleichverteilung).
Theoretisch müsste man die optimale Permutation in Abhängigkeit von der Verteilungsfunktion der Zugriffe aufschreiben können. Das gibt dann sicherlich ein Plus mit Sternchen in der Bewertung. ;)
Wenn ich ein Programm schreiben müsste, würde ich erstmal die Zugriffsstatistik heranziehen und bruteforcemäßig alle möglichen Permutationen durchspielen.
Eine Sortierung nach aufsteigender Programmlänge ist nicht unbedingt optimal.
danach hat auch niemand gefragt ;)
eine Heuristik findet nicht zwingendermaßen das Optimum, es ist nur eine Strategie
wie es pest getan hat (Normalverteilung).
ich habe eine gleichverteilung angenommen
Theoretisch müsste man die optimale Permutation in Abhängigkeit von der Verteilungsfunktion der Zugriffe aufschreiben können. Das gibt dann sicherlich ein Plus mit Sternchen in der Bewertung. ;)
du streber hättest das wieder gemacht ;) :D - das ist auch nicht schwer wenn man eine stichprobe der zugriffe kennt, dann sortiert man nicht nach programmlänge sondern nach programmlänge*zugriffsanzahl
Spasstiger
2009-05-24, 22:01:12
das ist auch nicht schwer wenn man eine stichprobe der zugriffe kennt, dann sortiert man nicht nach programmlänge sondern nach programmlänge*zugriffsanzahl
Hm, genial einfach. :eek:
Das erspart einem auch die Bruteforcerei. In einer Prüfung hätte ich aber nur den Bruteforce-Lösung aufgeschrieben, weil mir in der Schnelle nix Besseres eingefallen wäre.
/EDIT: Man muss aber nach Programmlänge/Zugriffsanzahl sortieren.
/EDIT: Man muss aber nach Programmlänge/Zugriffsanzahl sortieren.
jeder hat mal nen klaren moment :D
rofl
Pinoccio
2009-05-24, 22:07:01
ein Plus mit Sternchent_i könnte unendlich werden :P
oder:
Sei o. B. d. A. l_i=0 ...
Übrigens: Abgabe der Aufgabe: morgen! (http://www-ai.math.uni-wuppertal.de/SciComp/teaching/ss09/info2/exercises.html)
mfg
Sei o. B. d. A. l_i=0 ...
l_i kann nur von 1 bis n gehen
Übrigens: Abgabe der Aufgabe: morgen! (http://www-ai.math.uni-wuppertal.de/SciComp/teaching/ss09/info2/exercises.html)
das habe ich auch gesehen und fand es witzig
das witzige ist weiterhin, das ich heute beim ausflug da saß und eine ähnliche aufgabe lösen wollte
nehme ich selters oder himbeerwasser mit? selters wog ~1kg und himbeere ~1.5kg, aber himbeere schmeckt doppelt so gut wie selters
was mache ich...teile gewicht/geschmack und sortiere nach nicht steigenden werten...gehe mit der selters im arm los, doch dann fällt mir ein
das ich geschmack durch gewicht hätte teilen müssen :D...oder anders sortieren...ich habe mich so geärgert ;) :)
Pinoccio
2009-05-24, 22:23:47
l_i kann nur von 1 bis n gehenNein, i geht von 1 bis n, aber die Länge der Programme ist nicht vorgegeben. (Sinnvollerweise ;D ist ein Programm natürlich länger als 0 und endlich lang.)das habe ich auch gesehen und fand es witzigIch hab dazu auch eine Meinung, aber die ist von witzig weit entfernt. (eher: [ ] der gefährdet meinen Arbeitsplatz)das witzige ist weiterhin, das ich heute beim ausflug da saß und eine ähnliche aufgabe lösen wollte
nehme ich selters oder himbeerwasser mit? selters wog ~1kg und himbeere ~1.5kg, aber himbeere schmeckt doppelt so gut wie selters
was mache ich...teile gewicht/geschmack und sortiere nach nicht steigenden werten...gehe mit der selters im arm los, doch dann fällt mir ein
das ich geschmack durch gewicht hätte teilen müssen :D...oder anders sortieren...ich habe mich so geärgert ;) :)Glücklich ist, wer quantifizieren kann.
Hast du bei schmeckt doppelt so gut an das Weber-Fechner-Gesetz gedacht?
mfg
Nein, i geht von 1 bis n, aber die Länge der Programme ist nicht vorgegeben.
klar, was schreib ich denn...morgens müde, abends geschafft...
Hast du bei schmeckt doppelt so gut an das Weber-Fechner-Gesetz gedacht?
wieder was gelernt :)
WarSlash
2009-05-24, 22:52:56
Ich danke euch!
Im 3DCenter ist man immer echt gut aufgehoben um Rat zu suchen, wenn man selber nicht mehr weiter weiß :)
Das Studium wird nicht einfacher, aber ich wills durchziehen, weils ja denoch Spaß macht!
Das Blatt ist komplett gelöst, aber bei manchen Aufgaben muss man öfter nachdenken, bis man die gescheit kapiert hat!
hast du keine Kommilitonen oder Freunde mit denen du studierst?
Es gibt für jedes Studienfach entsprechende gute Foren, und du verläufst dich hier her ins 3dcenter. Kopfschütteln :-)
WarSlash
2009-05-25, 00:07:37
hast du keine Kommilitonen oder Freunde mit denen du studierst?
Es gibt für jedes Studienfach entsprechende gute Foren, und du verläufst dich hier her ins 3dcenter. Kopfschütteln :-)
Im 3dc sind bisher meist nette praxisnahe Spezialisten anzutreffen. :smile:
Auf diversen Matheboards find ich meist nur Theoretiker.
Ist halt zudem mein Lieblingsboard!
Leider ist es so, dass meine Freunde die Aufgaben garnicht gepeilt haben. Da ging dann erstmal nichts mehr.
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.