A.L. <a...@z...com> napisał(a):

> On Wed, 18 Feb 2009 00:25:26 +0100, "qweer" <cisrudlow[wytni]@o2.pl>
> wrote:
>
> >Witam,
> >Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
> >Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
> >koncowego.
>
> No i co ten graf nam mowi?...

Troche malo zrozumiale sie wyrazilem. Chodzilo mi o to, ze mamy sami wyznaczyc
element (elemety, jezeli to jest grupa) poczatowy. Zakladam, ze graf nie jest
cykliczny.


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

A.L. <a...@z...com> napisał(a):

> On Tue, 17 Feb 2009 23:12:49 -0800 (PST), Wit Jakuczun
> <w...@g...com> wrote:
>
> >On 18 Lut, 00:25, "qweer" <cisrudlow[wytni]@o2.pl> wrote:
> >
> >> Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
> >> optymalny dla takiego problemu.
> >
> >Jak A.L. powiedział, nie ma najbardziej optymalnego algorytmu. Wg
> >jakiego
> >kryterium masz ułożyć te zadania?
>
> Ja powiedzialem dwie rzeczy:
>
> 1. Jak ktos mowi "najbardziej oprtymalny" to ma klopoty z jezykiem
> polskim,,

Mysle, ze takie fora sluza do tego, zeby pomoc, a nie wdawac sie bezsensowna
dyskuje.
Jezeli czepiasz sie stopniowania, to moze wstawic "najoptymalniejszy".
"Naj..." tutaj oznacza, ze algorytm jest najbardziej skuteczny (lub
najskuteczniejszy) w rozwiazaniu okreslonego problemu.

> 2. Algorytmy szeregowania zadan sa NP-complete, wiec trudno mowic o
> "optymalnym" algorytmie

---> patrz akapit wyzej


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

A.L. <a...@z...com> napisał(a):

> On Wed, 18 Feb 2009 10:15:31 +0100, Adam K?obukowski
> <a...@k...pl> wrote:
>
> >
> >Polecam książkę pt. "Badania operacyjne dla informatyków", niestety
> >autora czy wydawnictwa nie pomnę, ale tam są całe stada algorytmów
> >szeregowania zadań opisane.
> >
> >Adam Kłobukowski
>
> Blazewicz, Cellary, Slowinski, Weglarz, "Badania operacyjne dla
> informatykow", WNT, 1983
>
> G. Coffman, "Teoria szeregowania zadan", WNT, 1980.
>
> Z nowszych:
>
> Smutnicki, "Algorytmy szeregowania" Akademicka Oficyna Wydawnicza
> EXIT, 2002
>
> Grabowski, Nowicki, Smutnicki, "Metoda blokowa w zagadnieniach
> szeregowanai zadan". EXIT, 2003
>
> A.L.

Mozesz jeszcze dorzucic publikacje Pawlaka. Prawda sa to podstawowe publikacje
do nauki na studencki egzamin z SPP (czy jakis odpowiednik tego przedmiotu), o
ktorym juz dawno z wielka ulga zapomnialem. Mi chodzilo o dokladniejsze
naprowadzenie na przynajmniej kilka konkretnych (mowie tutaj o nazwach, a nie
o ich przedstawianie) algorytmow. Urywam temat. Pozdrawiam

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

On Wed, 18 Feb 2009 13:42:09 +0000 (UTC), " qweer"
<c...@g...pl> wrote:

>Mysle, ze takie fora sluza do tego, zeby pomoc, a nie wdawac sie bezsensowna
>dyskuje.
>Jezeli czepiasz sie stopniowania, to moze wstawic "najoptymalniejszy".
>"Naj..." tutaj oznacza, ze algorytm jest najbardziej skuteczny (lub
>najskuteczniejszy) w rozwiazaniu okreslonego problemu.

"optymalny, optymalniejszy, najoptymalniejszy", Jezyka polska trudna
byc. Slownik polecam lub encyklopedie

A.L.

do góry

On Wed, 18 Feb 2009 13:38:16 +0000 (UTC), " qweer"
<c...@g...pl> wrote:

>A.L. <a...@z...com> napisał(a):
>
>> On Wed, 18 Feb 2009 00:25:26 +0100, "qweer" <cisrudlow[wytni]@o2.pl>
>> wrote:
>>
>> >Witam,
>> >Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
>> >Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
>> >koncowego.
>>
>> No i co ten graf nam mowi?...
>
>Troche malo zrozumiale sie wyrazilem. Chodzilo mi o to, ze mamy sami wyznaczyc
>element (elemety, jezeli to jest grupa) poczatowy. Zakladam, ze graf nie jest
>cykliczny.

No dobra, ale CO TEN GRAF OPISUJE?...

A.L.

do góry

epsilon$ while read LINE; do echo \>"$LINE"; done < " qweer"
>Mysle, ze takie fora sluza do tego, zeby pomoc, a nie wdawac sie bezsensowna
>dyskuje.

I A.L. stara ci się pomóc mówić (pisać) prawidłowo po polsku.

>Jezeli czepiasz sie stopniowania, to moze wstawic "najoptymalniejszy".

To jest równie głupie. "Optymalny" oznacza "najlepszy". Niezależnie od
tego czy rozumiemy to poprzez pryzmat teorii optymalizacji, czy
w znaczeniu potocznym. W obu przypadkach jest to jedno, najlepsze,
rozwiązanie. Dlatego "najoptymalniejszy" to bzdura.

>"Naj..." tutaj oznacza, ze algorytm jest najbardziej skuteczny (lub
>najskuteczniejszy) w rozwiazaniu okreslonego problemu.

I to właśnie oznacza "optymalny".

--
d'`'`'`'`'`'`'`'`'`'`'`'`'Yb Microsoft Office 2000: Wszystko ci wolno
`b K...@e...eu.org d'
d' http://epsilon.eu.org/ Yb
`b,-,.,-,.,-,.,-,.,-,.,-,.d'

do góry

qweer pisze:
>> Najprostsze, choć może lekko nieoptymalne pamięciowo(przyjmuję założenie
>> o jednostkowym rozmiarze zadania): Robisz graf skierowany w którym w
>> węzłach masz licznik - na ile zadań dane zadanie czeka bezpośrednio oraz
>> listę zadań które czekają na nie (odwrotnie niż w danych wejściowych).
>> Przeglądasz dane 1 raz i do listy wrzucasz wszystkie zadania z
>> licznikiem=0 - to jest 1 grupa. ->Dopóki są jakieś zadania na tej
>> liście. Wypisz grupę, odejmij 1 od liczników każdego zadania na które
>> wskazują te z listy dodając do drugiej listy te którym licznik się
>> wyzerował. Wywal pierwszą listę. Aktualną listą jest 2 lista. Powtórz
>> ->. Jeżeli w grafie zostały zadania z niezerowym licznikiem to znaczy,
>> że był cykl.
>
> Tak, tak, ale nie mam tutaj ograniczen czasowych.
Hm? nie zrozumiałem... Jeżeli nie masz ograniczeń czasowych (czyli każde
zadanie ma jednostkowy czas i nie ma linii krytycznych(one akurat nie
mają sensu przy nieskończonej ilości procesorów)) to to co napisałem
jest ok.

co: na co czeka
1:2,3
2:
3:4,2
4:

dostajesz 3 sestawy:
2,4
3
1
> Jezeli byloby tak, to bym mogl tutaj wykorzystac
> lekko zmodyfikowany algorytm wyznaczania sceizki krytycznej (juz nie pamietam
> kogo to byl wynalazek)
Jeżeli masz określone różne długości zadań to zamieniasz listę na listę
posortowaną wg długości (set) i zawsze zdejmujesz (wszystkie)
najkrótsze, uaktualniasz wskazywane przez nie, jeżeli wyjdzie jakieś 0
to dorzucasz do seta. Pracujesz póki set jest niepusty. A kolejny zestaw
się pojawia zawsze gdy jakieś zadanie z seta wywaliłeś.

(długość)
1(1):2,3
2(4):
3(2):4,2
4(1):
5(2):4
dostajesz (ile się grupa wykonuje):
2,4 (1)
2,5 (2)
2 (1)
3 (2)
1 (1)

--
Pozdrawiam
Michoo

do góry

On Wed, 18 Feb 2009 13:46:38 +0000 (UTC), " qweer"
<c...@g...pl> wrote:

>
>Mozesz jeszcze dorzucic publikacje Pawlaka.

Ktora? O "rough sets"?...

>Prawda sa to podstawowe publikacje
>do nauki na studencki egzamin z SPP (czy jakis odpowiednik tego przedmiotu), o
>ktorym juz dawno z wielka ulga zapomnialem. Mi chodzilo o dokladniejsze
>naprowadzenie na przynajmniej kilka konkretnych (mowie tutaj o nazwach, a nie
>o ich przedstawianie) algorytmow. Urywam temat. Pozdrawiam

Rzeczywiscie, chyba zapomniales.

Jak sie o cos pytasz, to SFORMULUJ SWOJE PYTANEI TAK ABY DAC KOMUS
SZANSE NA ODPOWIEDZ.

Z lektury twoich postow nei mam zielonego pojacia jaki problem chcesz
rozwiazac. Po co jest ten graf? Co on opisuje? Jakie sa atrybuty
zadan? Jakie maja byc wlasciwosci rozwiazania? I tak dalej.

W przypadku problemow NP-zupelnych istotny jest rozmair problemu,
albowiem mozliwe sa tylko algorytmy przyblizone,. Co innego bedzie gdy
mamy 5 zadan, co innego jak 50 czy 500.

A.L.

do góry

> Mozesz jeszcze dorzucic publikacje Pawlaka. Prawda sa to podstawowe publikacje
> do nauki na studencki egzamin z SPP (czy jakis odpowiednik tego przedmiotu), o
> ktorym juz dawno z wielka ulga zapomnialem. Mi chodzilo o dokladniejsze
> naprowadzenie na przynajmniej kilka konkretnych (mowie tutaj o nazwach, a nie
> o ich przedstawianie) algorytmow. Urywam temat. Pozdrawiam

Publikacje i rozwiazania Coffmana sa tutaj najbardziej pomcne


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

On Wed, 18 Feb 2009 14:52:27 +0100, Michoo <m...@v...pl> wrote:

>
>Jeżeli masz określone różne długości zadań to zamieniasz listę na listę
>posortowaną wg długości (set) i zawsze zdejmujesz (wszystkie)
>najkrótsze, uaktualniasz wskazywane przez nie, jeżeli wyjdzie jakieś 0
>to dorzucasz do seta. Pracujesz póki set jest niepusty. A kolejny zestaw
>się pojawia zawsze gdy jakieś zadanie z seta wywaliłeś.

Jak na moj rozum to on niespecjalnei wie co chce rozwiazac...

A.L.

do góry