[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

pl.comp.programming

Algorytm przydzialu prac do studentów

Kasia R

12/20/2006 9:14:00 PM

Mam takie zadanie dotyczace przydzialu prac dyplomowych - studenci
wybierajac prace dyplomowe tworza rankigi, które prace by chcieli
najbardziej, a które najmniej (1-najbardziej, 5-najmniej)
Np.
StudentA
1. praca1
2. praca4
3. praca 3
StudentB
1. praca3
2. praca1
3. praca5
StudentC
1. praca4
2. praca2
5. praca1

Nastepnie promotorzy sposród studentów, którzy zadeklarowali
chec pisania prac u nich prac (umiescili w rankingu prace) tworza
wlasne rankingi - kogo by chcieli najbardziej, a kogo najmniej.
Np.
Praca-promotor1
1.studentC
2.studentB
3.studentA
itd..

Zastanawiam sie jak przydzielac prace do studentów. Chce, zeby jak
najwiecej prac zostalo przydzielonych, ale w sensowny sposób. Na
pewno, jesli student wybierze prace na pierwszym miejscu i promotor
studenta na pierwszym miejscu, to musi nastapic przydzial pracy do
studenta. Wszyscy promotorzy sa tak samo uprzywilejowani, studenci
równiez. Promotorzy maja troche "wyzszy priorytet" od studentów.
Czy znacie jakis algorytm rozwiazujacy ten problem?
10 Answers

BobyX

12/20/2006 10:53:00 PM

0

"Kasia R" <rafalska.katarzyna@gmail.com> wrote:
>Mam takie zadanie dotycz?ce przydzia3u prac dyplomowych - studenci
>wybieraj?c prace dyplomowe tworz? rankigi, które prace by chcieli
>najbardziej, a które najmniej (1-najbardziej, 5-najmniej)

Szukaj pod has3em "perfect match" i w okolicach, AFAIR problem mo?na
rozwi?zaa przy pomocy algorytmu Khuna-Munkresa albo te? sprowadzaj?c do
minimalizacji przep3ywu w grafie i stosujaa Forda-Fulkersona.

Pozdrawiam,
BX

pdemb

12/20/2006 10:58:00 PM

0

"Kasia R" <rafalska.katarzyna@gmail.com> writes:

[...]

> Czy znacie jaki? algorytm rozwi?zuj?cy ten problem?

Mo?e relacja dominacji pomiedzy parami student-promotor.

pdemb

12/20/2006 11:21:00 PM

0

"BobyX" <bobyx@NOSPAMgazeta.pl> writes:

> "Kasia R" <rafalska.katarzyna@gmail.com> wrote:
>>Mam takie zadanie dotycz?ce przydzia3u prac dyplomowych - studenci
>>wybieraj?c prace dyplomowe tworz? rankigi, które prace by chcieli
>>najbardziej, a które najmniej (1-najbardziej, 5-najmniej)
>
> Szukaj pod has3em "perfect match" i w okolicach, AFAIR problem mo?na
> rozwi?zaa przy pomocy algorytmu Khuna-Munkresa albo te? sprowadzaj?c
> do minimalizacji przep3ywu w grafie i stosujaa Forda-Fulkersona.

A gdyby skomplikowaa problem w taki sposób, ?e promotor mo?e albo
okre?lia konkretnego studenta albo -- zamiast tego -- okre?lia jedynie
wymagania co do ocen studenta z poszczególnych przedmiotów?

--
http://www.piotr.dembin...

Tomek

12/21/2006 7:18:00 AM

0

Kasia R napisa3(a):
> Mam takie zadanie dotycz?ce przydzia3u prac dyplomowych - studenci
> wybieraj?c prace dyplomowe tworz? rankigi, które prace by chcieli
> najbardziej, a które najmniej (1-najbardziej, 5-najmniej)
> Np.
> StudentA
> 1. praca1
> 2. praca4
> 3. praca 3
> StudentB
> 1. praca3
> 2. praca1
> 3. praca5
> StudentC
> 1. praca4
> 2. praca2
> 5. praca1
>
> Nastepnie promotorzy spo?ród studentów, którzy zadeklarowali
> chea pisania prac u nich prac (umie?cili w rankingu prace) tworz?
> w3asne rankingi - kogo by chcieli najbardziej, a kogo najmniej.
> Np.
> Praca-promotor1
> 1.studentC
> 2.studentB
> 3.studentA
> itd..
>
> Zastanawiam sie jak przydzielaa prace do studentów. Chce, ?eby jak
> najwiecej prac zosta3o przydzielonych, ale w sensowny sposób. Na
> pewno, je?li student wybierze prace na pierwszym miejscu i promotor
> studenta na pierwszym miejscu, to musi nast?pia przydzia3 pracy do
> studenta. Wszyscy promotorzy s? tak samo uprzywilejowani, studenci
> równie?. Promotorzy maj? troche "wy?szy priorytet" od studentów.
> Czy znacie jaki? algorytm rozwi?zuj?cy ten problem?
>

Tak chyba najpro?ciej to by by3o dodaa rankingi studenta i promotora
tylko ranking promotora nale?a3o by najpierw pomno?ya/podzielia przez
jak?? wage ( ile bardziej wa?ny jest ranking promotora ). maj?c sume
rankingów dla danej pracy wybieramy studenta dla której suma rankingów
jest najmniejsza/najwieksza. Je?eli dany student ma juz przydzielon?
jak?? prace to bierzemy nastepnego w kolejce. W przypadku równych sum
rankingów o przydziale mo?e decydowaa ?rednia ocen b?d? losowanie.

BobyX

12/21/2006 7:22:00 AM

0


""Piotr Dembinski"" <pdemb@gazeta.pl> wrote in message
news:87slfacfxv.fsf@hector.domek...
> "BobyX" <bobyx@NOSPAMgazeta.pl> writes:
>
>> "Kasia R" <rafalska.katarzyna@gmail.com> wrote:
>>>Mam takie zadanie dotycz?ce przydzia3u prac dyplomowych - studenci
>>>wybieraj?c prace dyplomowe tworz? rankigi, które prace by chcieli
>>>najbardziej, a które najmniej (1-najbardziej, 5-najmniej)
>>
>> Szukaj pod has3em "perfect match" i w okolicach, AFAIR problem mo?na
>> rozwi?zaa przy pomocy algorytmu Khuna-Munkresa albo te? sprowadzaj?c
>> do minimalizacji przep3ywu w grafie i stosujaa Forda-Fulkersona.
>
> A gdyby skomplikowaa problem w taki sposób, ?e promotor mo?e albo
> okre?lia konkretnego studenta albo -- zamiast tego -- okre?lia jedynie
> wymagania co do ocen studenta z poszczególnych przedmiotów?

My?le, ?e mo?na to uwzglednia dobieraj?c odpowiednio wagi w grafie,
promotorowi mo?na przypodrz?dkowaa wtedy wszystkich studentów z wagami
zale?nymi od ?redniej : )

Pozdrawiam,
BX

Kasia R

12/21/2006 9:30:00 AM

0


Tomek napisal(a):
> Kasia R napisal(a):
> > Mam takie zadanie dotyczace przydzialu prac dyplomowych - studenci
> > wybierajac prace dyplomowe tworza rankigi, które prace by chcieli
> > najbardziej, a które najmniej (1-najbardziej, 5-najmniej)
> > Np.
> > StudentA
> > 1. praca1
> > 2. praca4
> > 3. praca 3
> > StudentB
> > 1. praca3
> > 2. praca1
> > 3. praca5
> > StudentC
> > 1. praca4
> > 2. praca2
> > 5. praca1
> >
> > Nastepnie promotorzy sposród studentów, którzy zadeklarowali
> > chec pisania prac u nich prac (umiescili w rankingu prace) tworza
> > wlasne rankingi - kogo by chcieli najbardziej, a kogo najmniej.
> > Np.
> > Praca-promotor1
> > 1.studentC
> > 2.studentB
> > 3.studentA
> > itd..
> >
> > Zastanawiam sie jak przydzielac prace do studentów. Chce, zeby jak
> > najwiecej prac zostalo przydzielonych, ale w sensowny sposób. Na
> > pewno, jesli student wybierze prace na pierwszym miejscu i promotor
> > studenta na pierwszym miejscu, to musi nastapic przydzial pracy do
> > studenta. Wszyscy promotorzy sa tak samo uprzywilejowani, studenci
> > równiez. Promotorzy maja troche "wyzszy priorytet" od studentów.
> > Czy znacie jakis algorytm rozwiazujacy ten problem?
> >
>
> Tak chyba najprosciej to by bylo dodac rankingi studenta i promotora
> tylko ranking promotora nalezalo by najpierw pomnozyc/podzielic przez
> jakas wage ( ile bardziej wazny jest ranking promotora ).

Tak, mysle, ze to dodawanie rankingów promotorów i prac z
uwzglednieniem jakis wag jest dobrym pomyslem. Wtedy zamiast 2
macierzy mam jedna i juz jest latwiej.

> majac sume
> rankingów dla danej pracy wybieramy studenta dla której suma rankingów
> jest najmniejsza/najwieksza. Jezeli dany student ma juz przydzielona
> jakas prace to bierzemy nastepnego w kolejce. W przypadku równych sum
> rankingów o przydziale moze decydowac srednia ocen badz losowanie.

Tylko problem jest taki, ze wszystkie prace sa jednakowo wazne i nie
wiadomo którym pracom najpierw przydzielic studentów, a którym
pózniej. Ewentualnie moglabym zrobic odwrotnie czyli sortuje
studentów wg. sredniej. Biore pierwszego studenta i przydziem mu
prace, która ma najmniejsza sume, potem z kolejnymi to samo, o ile
praca nie jest juz zajeta. Tylko jeszczee nie jestem pewna, czy
sortowac tak studentów, moze lepiej bedzie to rozwiazac "metoda
wegierska" albo czyms podobnym.

Kasia R

12/21/2006 9:36:00 AM

0

BobyX napisal(a):
> ""Piotr Dembinski"" <pdemb@gazeta.pl> wrote in message
> news:87slfacfxv.fsf@hector.domek...
> > "BobyX" <bobyx@NOSPAMgazeta.pl> writes:
> >
> >
> > A gdyby skomplikowac problem w taki sposób, ze promotor moze albo
> > okreslic konkretnego studenta albo -- zamiast tego -- okreslic jedynie
> > wymagania co do ocen studenta z poszczególnych przedmiotów?
>
> Mysle, ze mozna to uwzglednic dobierajac odpowiednio wagi w grafie,
> promotorowi mozna przypodrzadkowac wtedy wszystkich studentów z wagami
> zaleznymi od sredniej : )
>
> Pozdrawiam,
> BX

To sa pomysly na wyeliminowanie rankingu promotora, ale tak sie nie
da. Protorzy maja bardzo rózne preferencje - jeden bierze pod uwage
srednia studentów, ale inny porozmawia ze studentami i wybierze
pasjonatów. Jeszcze ktos inny bedzie bral pod uwage konkursy i
osiagniecia.

BobyX

12/21/2006 6:51:00 PM

0

"Kasia R" <rafalska.katarzyna@gmail.com> wrote:

>Tylko problem jest taki, ?e wszystkie prace s? jednakowo wa?ne i nie
>wiadomo którym pracom najpierw przydzielia studentów, a którym
>pó?niej. Ewentualnie mog3abym zrobia odwrotnie czyli sortuje
>studentów wg. ?redniej. Biore pierwszego studenta i przydziem mu
>prace, która ma najmniejsz? sume, potem z kolejnymi to samo, o ile
>praca nie jest ju? zajeta. Tylko jeszczee nie jestem pewna, czy

Najlepiej najpierw doprecyzowaa problem na tyle ?eby da3o sie wyznaczya
jedno ktyterium optymalizacji, wtedy mo?na bedzie (lub nie) wybraa sensowny
algorytm.
IMHO najpro?ciej przedstawia zagadnienie w formie pe3nego, nieskierowanego
grafu dwudzielnego, w którym niektóre wagi mog? bya zerowe (wzglednie
nieskonczone). To zagwarantuje rozwi?zywalno?a w ka?dym przypadku. Dobór wag
ju? zale?y od podej?cia.

>sortowaa tak studentów, mo?e lepiej bedzie to rozwi?zaa "metod?
>wegiersk?" albo czym? podobnym.

O ile pamietam z3o?ono?a O(n^3), wiec nawet dla du?ej specjalno?ci da sie
wyliczya.

Pozdrawiam,
BX

pdemb

12/22/2006 12:40:00 PM

0

"BobyX" <bobyx@NOSPAMgazeta.pl> writes:

> "Kasia R" <rafalska.katarzyna@gmail.com> wrote:
>
>>Tylko problem jest taki, ?e wszystkie prace s? jednakowo wa?ne
>>i nie wiadomo którym pracom najpierw przydzielia studentów,
>>a którym pó?niej. Ewentualnie mog3abym zrobia odwrotnie czyli
>>sortuje studentów wg. ?redniej. Biore pierwszego studenta
>>i przydziem mu prace, która ma najmniejsz? sume, potem z kolejnymi
>>to samo, o ile praca nie jest ju? zajeta. Tylko jeszczee nie jestem
>>pewna, czy
>
> Najlepiej najpierw doprecyzowaa problem na tyle ?eby da3o sie
> wyznaczya jedno ktyterium optymalizacji, wtedy mo?na bedzie (lub
> nie) wybraa sensowny algorytm.

W postaci, w której zosta3 przedstawiony, to ten problem mo?na
rozwi?zaa algorytmem o z3o?ono?ci czasowej O(M^2), gdzie M jest
liczb? studentów / tematów prac. Tylko takie postawienie sprawy
(?eby promotor musia3 dla ka?dego tematu pracy okre?laa ca3y
ranking studentów) jest ma3o wygodne dla promotorów.

Inne przypadki (promotor okre?laj?cy swój globalny model preferencji
w taki sposób, jaki jest dla niego najwygodniejszy) jest o wiele
bardziej interesuj?cy i mo?na by wówczas zastosowaa bardzo fajne,
z3o?one czasowo algorytmy wspomagania decyzji 8-)

--
http://www.piotr.dembin...

pdemb

12/22/2006 1:01:00 PM

0

pdemb@gazeta.pl (Piotr Dembinski) writes:

[...]

> liczb? studentów / tematów prac

To oczywi?cie jest 'liczba studentów lub liczba tematów prac'.