'K zit met een logica probleem

[Verwijderd]

Ik moet voor school (ja het is huiswerk maar lees effe door voordat je begint te schelden) met een groep mensen een softwaresysteem ontwerpen voor een corveesysteem in een studentenhuis.

Nu zit ik al 3 of 4 dagen met een logica probleem. nl.:
Je hebt studenten in het corveesysteem, deze studenten moeten taken uitvoeren per 2 weken moeten ze bijv. 10 verschillende taken doen. [taak 1 tm/10] [aantal studenten is variabel]

Nu had ik bedacht dat de studenten ook een voorkeur kunnen opgeven in het systeem voor een taak (was optioneel maar zag er simpel uit).

Ik dacht dat ik dat voorkeur gedoe wel kon programmeren door een simpele formule te gebruiken: Cijfer_voor_taak[N]/Totaal_aantal_cijfers_voor_taak[N]*100= het percentage kans dat een student op een taak heeft in de week.

Dit klopt allemaal wel maar als ik dan de student erbij betrek en de dagenplannig snap ik er nix meer van.

Ik zit nu alleen met een vette programmeurs-block, ik kan er niet eens een PSD van maken laat staan implementeren.

effe in het kort: Ik zoek dus een manier om taken te verdelen onder studenten over een bepaalde periode waar de studenten een cijfer(voorkeur) mogen geven voor alle taken(cijfer ligt tussen 1 en 10).

Ik vraag dit niet voor niets, mijn groep is namelijk ook voor een gedeelte afhankelijk van mijn resultaten.

Als iemand me kan helpen......

[mbravenboer]

Dit lijkt mij meer een Wiskunde A - kansverdeling/statistiek /permutaties probleem dan logica...

[Verwijderd]

Op woensdag 26 september 2001 21:02 schreef mbravenboer het volgende:
Dit lijkt mij meer een Wiskunde A - kansverdeling/statistiek /permutaties probleem dan logica...

ok my mistake maar kun je me helpen???

[mbravenboer]

Het heeft eigenlijk meer weg van een optimaliserings probleem:

1. hoe zorg ik dat zoveel mogelijk studenten hun voorkeurstaak kunnen uitvoeren?

2. hoe zorg ik ervoor dat alle taken worden uitgevoerd.

Je moet hierbij dus elke uitgevoerd taak in een mogelijke werkverdeling een score geven aan de hand van de voorkeur van de uitvoerder. Alle scores bij elkaar moeten maximaal zijn.

Daar kan je allerlei leuke algoritmes voor toepassen... Probeer het eerst eens met een greedy aanpak: probeer zoveel mogelijk studenten hun zin te geven. Als dat conflicteerd ga je varianten toevoegen... Je komt zo niet op de optimale oplossing, maar ik begrijp uit je uitleg dat dat ook niet strikt noodzakelijk is.

[Verwijderd]

Jah, use lingo

[Seraphin]

Ik ben zeker geen expert in programmeren, maar misschien kan ik je helpen.....

Wat mij opvalt is dat je vanuit de student redeneert. Probeer het eens van de andere kant; de taak.

Je weet dat je een vaste hoeveelheid taken hebt.

Verder neem ik aan dat je aan het begin van je programma het aantal studenten in moet voeren, en eventueel bijzondere informatie (bijvoorbeeld de studenten die nog nooit corvee / altijd corvee hebben gehad).

Je kan er nu voor kiezen om d.m.v. een kansberekeningformule of wat dan ook de studenten te selecteren die moeten corveën.

Als je dat hebt gedaan, heb je de volgende zaken bepaald:

-uit te voeren taken
-studenten die taken uit moeten voeren
-voorkeuren van studenten (ik ga ervan uit dat je dat samen met het invoeren van aantallen studenten hebt aangegeven)

Nu kan je een simpel rekensommetje maken: De geselecteerde student die het hoogste voorkeurscijfer voor taak 1 heeft gegeven, krijgt die taak enz. enz.

Het vereist wel nog wat uitwerking (volgens mij krijgt op deze manier namelijk 1 student alleen maar rotklussen), maar misschien is dit voldoende om je een beetje op gang te helpen.

[Verwijderd]

.. uitwerking (volgens mij krijgt op deze manier namelijk 1 student alleen maar rotklussen), maar misschien is dit voldoende om je een beetje op gang te helpen.

Heb ik idd ook aan gedacht maar dan zit je met dat gedoe dat 1 ventje altijd de leuke dingen te doen krijgt en 1 ventje constant de wc staat te schrobben.

ik ben niet zo geweldig met algoritmes, dus als jullie denken dat ik hier nog een nacht of 3 over moet denken dan kies ik ervoor om dit hele gedoe maar niet te automatiseren en de taken laten verdelen door de huismeester ofzo...

[Mart!]

Je kan studenten natuurlijk ook credits geven wanneer ze een rottaak hebben uitgevoerd. Als dit zo is, dan wordt er bij de volgende taakverdeling (volgende periode) meer rekening gehouden met hun voorkeurstaak (Zou wel kick-ass zijn tenminste)

Mijn idee:
Geef elke taak een weging (10=k*twerk, 1=supertof)
Laat iedere persoon voorkeuren aangeven (1=liever niet, 10=dit doe ik het liefste)
Door middel van een formule (beetje met parameters klooien) kun je dan de taakkeuze maken.

Ik doe al 10x kutwerk: 10x10 = 100 punten
Ik doe het liefste de afwas: 10
Ik haat was ophangen: 1
Ik krijg dan voor afwas: 100 x 10 = 1000 punten
Ik krijg dan voor was ophangen 100 x 1 = 100 punten

(De kans dat een ander voor was ophangen hogere punten scoort is waarschijnlijk groter)
Idee is niet perfect uitgewerkt, maar het concept is 'heel redelijk'
De weging (gespaarde punten) zou ik dan trouwens wel over een langere periode berekenen...

[Verwijderd]

Op woensdag 26 september 2001 21:22 schreef Mart! het volgende:
Je kan studenten natuurlijk ook credits geven wanneer ze ...Idee is niet perfect uitgewerkt, maar het concept is 'heel redelijk'

idd daar had ik nog niet aan gedacht en dan door de huismeester laten bepalen hoe tof die taak is of gewoon aan het begin van het systeem de gemiddelde punten van de studenten bekijken dan kom je er ook achter hoe vet dingen zijn.. right???

[Mart!]

Ik zou eerst gaan voor een vaste puntenverdeling per taak, later zou je dit nog dynamisch kunnen maken.
Moet nu weg (overwerk zit erop ). Succes. Kijk morgen nog wel ff weer hoe ver je er mee bent.

[tomato]

Als je dit wat verder uit gaat werken en je wilt een algoritme om de beste verdeling te vinden heb je grote kans dat je in theorie over grafen (Hammiltonpaden) terecht gaat komen. Jammergenoeg kan dit zeer complex worden, dus wellicht vind je geen 'perfect' (altijd werkend) algoritme, maar alleen enkele 'vuistregels' om altijd tot redelijke verdelingen te komen. Zulke vuistregels waar je ook een algoritme aan kan ophangen zijn voor een deel waarschijnlijk wel betrekkelijk makkelijk te vinden.

[Mart!]

[Schop]
Hey, Zoepnek, ben je er nog een beetje uit gekomen? Wel benieuwd naar je uiteindelijke oplossing! Let us know

[Zoijar]

Dit is een typisch "koppelings probleem". Komt veel grafen theorie bij kijken, is nog veel meer onderzoek naar gedaan, en is nog altijd een "lastig" probleem. Moet maar is iets over de stelling van Hall zoeken, of een boek over discrete wiskunde.

[tomato]

Ik vond hier wel een leuke link

Qua studieboek lijkt me deze wel relevant en in de universiteitsbieb vind je wellicht nog dit boek:

Reingold, Nievergelt, Narsingh Deo - Combinatorial Algorithms
Prentice Hall, 1977


Maar ik denk niet dat je hier zo diep in wilt duiken, dus als ik jou was zou ik gewoon proberen wat simpele 'guidelines' te bedenken om die 'meestal' een redelijke verdeling geven en het daar maar bij laten.

[Verwijderd]

Bedankt voor jullie replies mensen maar ik moet iets simpels hebben, dat simpel werkt(ook al is dat niet t meest ideaal)
Ik ga dus voor de oplossing van Mart!

Nu zit ik toch nog met een probleem hoe krijg ik dat systeem geprogrammeerd Mart!???

Ik moet alle studenten een taak geven verdeeld over 2 weken en sommige taken 2 maal. Met jou berekening krijg ik wel een mooie uitkomst maar ik krijg er geen psd van gemaakt (iets dat helaas wel gevraagd word). Ik moet een lus maken die dus telt van student naar student en vervolgens van taak naar taak maar dan heb ik de dagen er nog niet bij betrokken.

Dus als je nog eens moet overwerken..
Of als iemand anders me kan helpen....

[Verwijderd]

Bij the way dit is de Logische gegevens structuur van het systeem (die gedeelten die je gebruikt bij het opmaken van t rooster:

STUDENT (stdnr, achternaam, voornaam, straatnaam, huisnr, postcode, woonplaats, privé-tel, Kamernr, sthnr, passwoord, geslacht, hm)
FK kamernummer-->KAMER(kamernr)
FK sthnr-->STUDENTENHUIS(sthnr)

VOORKEUR (stdnr, actnr,cijfer)
FK stdnr-->STUDENT(stdnr)
FK actnr-->ACTIVITEIT(actnr)

ACTIVITEIT (actnr, naam, beschrijving)

ROOSTER (actnr, R-datum, stdnr)
FK actnr-->ACTIVITEIT(actnr)
FK stdnr-->STUDENT(stdnr)
[/LGS]

[Tsjipmanz]

Hee dit doet me wel een beetje denken aan het "Stable Marriage Problem".

Hierij is er een groep mannen en een groep vrouwen die met elkaar moeten trouwen, en ze hebben elk een lijstje met voorkeuren.

dus bv de voorkeurslijst van
man 1 = (vrouw 3, vrouw 1, vrouw 2)
man 2 = (vrouw 3, vrouw 2, vrouw 1)
man 3 = (vrouw 1, vrouw 2, vrouw 3)

Op een soortgelijke manier hebben ook de vrouwen een voorkeurslijst en de bedoeling is om de ongelukkigheid minimaal te houden.

Op http://www.sandelman.ottawa.on.ca/People/Michael_Richardson/thesis/subsubsection1.2.0.4.2.2.html staat een algoritme hiervoor en bovendien is er op internet veel over te vinden.

Misschien kan je je probleem definieren als een variant op het SMP.

Hoop dat je er wat aan hebt, succes!

[Verwijderd]

Op vrijdag 28 september 2001 15:28 schreef Tsjipmanz het volgende:
Hee dit doet me wel een beetje denken aan het "Stable Marriage Problem".

Hierij is er een groep mannen en een groep vrouwen die met elkaar moeten trouwen, en ze hebben elk een lijstje met voorkeuren.

dus bv de voorkeurslijst van
man 1 = (vrouw 3, vrouw 1, vrouw 2)
man 2 = (vrouw 3, vrouw 2, vrouw 1)
man 3 = (vrouw 1, vrouw 2, vrouw 3)

Op een soortgelijke manier hebben ook de vrouwen een voorkeurslijst en de bedoeling is om de ongelukkigheid minimaal te houden.

Op http://www.sandelman.ottawa.on.ca/People/Michael_Richardson/thesis/subsubsection1.2.0.4.2.2.html staat een algoritme hiervoor en bovendien is er op internet veel over te vinden.

Misschien kan je je probleem definieren als een variant op het SMP.

Hoop dat je er wat aan hebt, succes!

k heb er es naar gekeken maar zoals ik al zei t moet simpel zijn en er onder staat ook nog iets :
This algorithm has been implemented, and it works as advertised. Unfortunately, it does not solve the right problem.
het moet gewoon een beetje simpel zijn...

of je moet een beetje ziek in je hoofd zijn en een moeilijke oplossing programmeren in Delphi, Pascal of C en die naar me mailen, je zou me er een groot plezier mee doen maar jezelf waarschijnlijk niet.

[curry684]

Op vrijdag 28 september 2001 15:37 schreef Zoepnek het volgende:
of je moet een beetje ziek in je hoofd zijn en een moeilijke oplossing programmeren in Delphi, Pascal of C en die naar me mailen, je zou me er een groot plezier mee doen maar jezelf waarschijnlijk niet.

Als je dit topic als 'roep om hulp' repost met een C++ subject zou je nog best kans hebben dat die zieke geesten hier rondlopen

(nee niet doen )

[disjfa]

logica is voor dummies, en ik weet dat

[wasigh]

Op vrijdag 28 september 2001 15:28 schreef Tsjipmanz het volgende:
Hee dit doet me wel een beetje denken aan het "Stable Marriage Problem".

Dat is precies waar ik aan dacht..
en op zich is dat wel een leerzaam iets om te implementeren.

[Tim Schuhmacher]

misschien niet de slimste manier, maar kan je het probleem niet opsplitsen door eerst eens gewoon alle mogelijke verdeelcombinaties te laten genereren (recursie). Kan je daarna je helemaal richten op de meest gunstige uit die mogelijkheden te halen.

[Zoijar]

hmm stel dat je 30 studenten hebt, en 10 taken, dan kan je al op 1,0903*10^14 manieren die studenten over de taken verdelen. En dat is dan dus per 2 weken van wat ik er van begrijp. Als je dan ook nog voorkeuren etc er bij betrekt, dan is "alle mogelijke verdeel combinaties berekenen" niet meer haalbaar.

[Tim Schuhmacher]

Op zaterdag 29 september 2001 13:27 schreef Zoijar het volgende:
hmm stel dat je 30 studenten hebt, en 10 taken, dan kan je al op 1,0903*10^14 manieren die studenten over de taken verdelen.

hoe kom jij aan al die getallen??

Ik dacht dat Zoepnek het zo bedoelde:
x aantal studenten moeten samen in totaal in 2 weken 10 taken doen.

[Verwijderd]

Op zaterdag 29 september 2001 13:55 schreef Tim Schuhmacher het volgende:

[..]

hoe kom jij aan al die getallen??

Ik dacht dat Zoepnek het zo bedoelde:
x aantal studenten moeten samen in totaal in 2 weken 10 taken doen.

klopt dat bedoel ik ook.. het heeft iig geen zin om iedere dag door een andere student de wc te laten poetsen

[Zoijar]

Dat getal is op hoeveel manieren je 30 studenten over 10 taken kan verdelen. ie. 30*29*28*...*21 ofwel 30!/(30-10)!

[jopiek]

eeen goede programmeertaal hiervoor is Prolog... je hebt een versie die ook met c++/Delphi etc. kan samenwerken (AxtiveX geloof ik) da's Amzi Prolog...

[Verwijderd]

Is er dan niemand die me kan helpen??

[Tsjipmanz]

Aan de ene kant klaag je dat niemand je wil helpen, maar aan de andere kant:

Als iemand probeert je te helpen met de oplossing zeg je dat het te moeilijk is en dat het makkelijker moet. Ga dan klagen bij je docent dat de opdracht te moeilijk is, in plaats van hier mensen na te laten denken over jou probleem en dan achteraf zeggen "ja, maar dat is te moeilijk". Bovendien doe je 2 dingen die niet mogen, namelijk:

1) Steeds je eigen topic omhoog schoppen. Dit wordt als irritant gezien door de meeste mensen, als iemand het antwoord weer post ie t wel

2) Vragen of iemand het complete programma voor je wil maken. Mensen kunnen je best op weg helpen maar om nou alles door iemand anders te laten doen leer je zelf ook niks van

Sorry, dat wou ik ff kwijt.

[Verwijderd]

Op maandag 01 oktober 2001 11:56 schreef Tsjipmanz het volgende:
Aan de ene kant klaag je dat niemand je wil helpen, maar aan de andere kant:

Als iemand probeert je te helpen met de oplossing zeg je dat het te moeilijk is en dat het makkelijker moet. Ga dan klagen bij je docent dat de opdracht te moeilijk is, in plaats van hier mensen na te laten denken over jou probleem en dan achteraf zeggen "ja, maar dat is te moeilijk". Bovendien doe je 2 dingen die niet mogen, namelijk:

1) Steeds je eigen topic omhoog schoppen. Dit wordt als irritant gezien door de meeste mensen, als iemand het antwoord weer post ie t wel

2) Vragen of iemand het complete programma voor je wil maken. Mensen kunnen je best op weg helpen maar om nou alles door iemand anders te laten doen leer je zelf ook niks van

Sorry, dat wou ik ff kwijt.

1) Het topic is door mij maar 1x omhoog geschopt

2) Ik vraag niet voor het complete programma maar voor een tip die me opweg helpt naar de oplossing de simpele variant van Mart!.
Ik klaag niet dat de andere oplossingen te moeilijk zijn maar ik zeg dat ik voor deze oplossingen mezelf moet verdiepen in algoritmen, iets waar ik vrij weinig vanaf weet

Sorry dat WILDE ik ff kwijt

[Janoz]

Op maandag 01 oktober 2001 21:15 schreef Zoepnek het volgende:
2) Ik vraag niet voor het complete programma maar voor een tip die me opweg helpt naar de oplossing de simpele variant van Mart!.
Ik klaag niet dat de andere oplossingen te moeilijk zijn maar ik zeg dat ik voor deze oplossingen mezelf moet verdiepen in algoritmen, iets waar ik vrij weinig vanaf weet

Tjongejonge, je wilt een algoritme bedenken, maar wil je niet in algoritmes verdiepen.. Lekkere ben jij zeg!

[The - DDD]

Denk toch dat je aan een credit systeem moet werken..

Elke taak heeft voor elke student een bepaalde zwaarte.

Vervolgens levert een klote taak punten op om een leuke taak te doen en levert een leuke taak minpunten op voor een leuke taak.

De studenten kunnen zodoende taken die ze leuk vinden kopen. Diegene met de meeste punten heeft de eerste koop. De student met de minste punten heeft de laatste koop.

Je krijgt te maken met het feit dat er meer taken dan studenten zijn. Dit houdt dus in dat niets doen ook als een taak gezien moet worden, als een taak die het meest kost dus.

Grootste probleem is dat je een balans moet zien te vinden.

Je hebt 10 taken, dus dat is 11 taken als je niet doen mee telt.

Als je nou is een schaal probeert te maken als deze: -5 -4 -3 -2 -1 0 1 2 3 4 5

Of iets wat er op lijkt. Vervolgens kun je daaraan wat tweaken zolang je maar zorgt dat de te halen minpunten in evenwicht staan met het aantal pluspunten.

Dus bij elkaar opgeteld moeten (alle pluspunten) + (alle minpunten) (zijn negatief he) uitkomen op 0.

Als er een gelijkheids situatie is dan moet je gewoon random toewijzen aan de meest waarschijnlijke kandidaten. In het begin heeft iedereen bijvoorbeeld 0, maar het zal ook voorkomen dat meer personen bijvoorbeeld 10 hebben.

Random kiezen is niet erg, want de leuke taak levert die persoon -punten op en zodoende is het allemaal goed verdeelt bij de volgende uitdeling van taken.

Moeilijkste is het bepalen van wat nou de punten voor de taken zijn. Het is mogelijk om per student een persoonlijke, dit vindt ik leuk schaal te maken.

Maar ja...

Wat nu overblijft is de vraag: WAT IS HET NUT VAN EEN DERGELIJK SYSTEEM????

Het eerlijskte is gewoon als iedereen elke taak even vaak doet over een bepaalde tijdsperiode. Dus waarom zou je een dergelijk systeem bouwen? Grote kans dat je leraar het ook zal zeggen: Leuk dat je het gebouwt hebt, maar wat is het echte nut er nou van? Nou die is er niet. Dus bespaar je de moeite.

[Verwijderd]

Heeft Joop dit probleem bedacht? Als jij in Breda studeert zal dat wel het geval zijn lol

[kareltje21]

dit is een perfect probleem om op te lossen met operations research, bijv. met lineair programmeren,

wat je doet is een maximaliserings functie opstellen (bv dat elke jongen zijn maximale score haalt qua wensen)
daarna ga je randvoorwaarden opstellen, dit kun je redelijk uitgebreid maken.

elke taak moet 1 of minimaal 2 keer uitgevoerd worden kun
je door een stelsel van ranvoorwaarden bewerkstelligen.
daarna kun je de voorkeuren van de jongeren in randvoorwaarden verwerken.

de ideale dag waarop zou of met randvoorwaarden of in de waarderingsfunctie kunnen verwerken.

hou je stelsel van tig vergelijkingen over waar je een lp (lineair programmerings algoritme) op los kunt laten (zijn diverse.

zo'n stelsel en algoritme om op te lossen moeten redelijk makelijk te programmeren zijn.

kijk hier eens onder operations research en met name lineair programmeren voor literatuur.

http://www.library.tudelft.nl/gids/nl/wiskun/wiskun-b.htm

[Verwijderd]

Ik heb straks toch OR, en heb al ff een beetje een algoritme bedacht.

Nu zo nog ff in Lingo spelen, en kijken of die idd werkt.

[Verwijderd]

Op maandag 01 oktober 2001 23:29 schreef IEEE802.5 het volgende:
Heeft Joop dit probleem bedacht? Als jij in Breda studeert zal dat wel het geval zijn lol

joop?????

[tomato]

Op dinsdag 02 oktober 2001 10:24 schreef Zoepnek het volgende:

[..]

joop?????

Tsja, dan krijg je nog replies, maar dan reageer je alsnog alleen maar op de meest onzinnige...