On 2012-10-16, M.M. <m...@g...com> wrote:
> Tu nie rozumiem juz nic, jesli jest przechodni, to
> nie wystarczy do posortowania?

Do posortowania potrzebny jest zbiór z porządkiem liniowym, czyli
spełniający wszystkie jego własności. Sortowanie jest właśnie
"układaniem elementów zgodnie z porządkiem liniowym". To jest
w pewnym sensie z definicji oczywiste.
Przechodniość jest tylko jedną z nich. Wymieniłem ją, ponieważ
wymieniona przez Ciebie relacja była właśnie nieprzechodnia.

pozdrawiam,
PK

do góry

BTW:
Jakby się tak bardzo spiąć, to oczywiście to co piszesz nie jest
prawdą też z innego powodu. Każdy zbiór (nawet bez minimum) mogę
sobie ustawić w dwóch ciągach: malejącym i rosnącym od pierwszego
elementu. Problemem jest wyłącznie przeliczalność, tzn. słuszna
jest sugestia, że nie da się na kompie posortować nieskończonego
zbioru (no ale skończona pamięć, problem stopu i tak dalej... :)).

pozdrawiam,
PK

do góry

W dniu wtorek, 16 października 2012 20:55:00 UTC+2 użytkownik Stachu 'Dozzie' K.
napisał:
> A kto ci naklamal, ze taka relacja to relacja czesciowego porzadku,
> a tym bardziej porzadku liniowego?
A mozesz mi zacytowac gdzie napisalem ze to jest relacja czesciowego
porzadku albo porzadku liniowego?
Pozdrawiam

do góry

Dnia 16.10.2012 bartekltg <b...@g...com> napisał/a:
> W dniu 2012-10-16 22:06, Baranosiu pisze:
>
>>
>> To zależy jak się rozumie pojęcie "posortować", bo w CIĄG rosnący to
>> się ich ustawić nie da (choć zgoda, każde dwie da się porównać i tak
>
> Nieprzeliczalnego zbioru (jak choćby wspomniany (0,1)) w ogole
> nie da się ustawić w _jakikolwiek_ ciąg;-)

No właśnie, nie da się ustawić w ciąg, a więc nie da się za pomocą
"sekwencyjnie wykonywanych instrukcji" zbioru uporządkować, czyli nie
istnieje algorytm w takim pojęciu, w jakim rozważamy go w tym wątku,
mało tego, nie istnieje nawet algorytm "zapętlony na wieczność"
rozwiązujący ten problem w nieskończonym czasie :D

>
>> ustawić, że "każda po prawo jest większa od tej po lewej")
>> ale... jeśli nie da się ułożyć w ciąg, to też nie da się podać
>> algorytmu sortującego, więc... coś za coś, jeśli zluzujemy z definicją
>> "posortowany" (niekoniecznie w ciąg) to luzujemy z definicją
>> "algorytmu" (rezygnujemy z "sekwencja następujących po sobie
>> instrukcji") bo inaczej nie da się przedstawić algorytmu sortowania w
>> "nie-ciąg" :D
>
>
> Nie chodziło mi o to. Przez posortować rozumiałem potencajlną
> możliwość ustawianie w sposób posortowany. Nie algorytm.
> Ale niech będzie algorytm, jak zauważasz, to nieistotne.

Zgoda, mój błąd, zagalopowałem się :D Samo istnienie dobrego porządku
nie gwarantuje możliwości ustawienia elementów zbioru w
ciąg. Natomiast sama możliwość ustawienia elementów zbioru w ciąg
(przeliczalność) jest (o ile się nie mylę :D) warunkiem niezbędnym na
istnienie algorytmu sortującego (rozumianego jako "sekwencja
instrukcji" - niekoniecznie skończona, być może sortująca w sensie
granicznym).
Miałem na myśli to, że samo istnienie porządku liniowego (czy dobrego
porządku, masz rację, na jedno wychodzi) nie gwarantuje istnienia
algorytmu sortującego (w czasie skończonym bądź w sensie granicznym
przy liczbie kroków dążącej do nieskończoności).

do góry

W dniu wtorek, 16 października 2012 22:54:59 UTC+2 użytkownik PK napisał:
> Do posortowania potrzebny jest zbiór z porządkiem liniowym, czyli
> spełniający wszystkie jego własności. Sortowanie jest właśnie
> "układaniem elementów zgodnie z porządkiem liniowym". To jest
> w pewnym sensie z definicji oczywiste.
> Przechodniość jest tylko jedną z nich. Wymieniłem ją, ponieważ
> wymieniona przez Ciebie relacja była właśnie nieprzechodnia.
Jaki jest przyklad zbioru z czesciowym porzadkiem ktorego nie
da sie posortowac?
Pozdrawiam

do góry

Dnia Tue, 16 Oct 2012 11:25:20 -0700, kenobi napisal:

> (powinienem byc wnerwiony bo odkrylem ze
> zgubilem w sklepie telefon (niedobrze bo
> beda klopoty) - ale nawet na to nie mam
> sily - symboliczne zdarzenie bo wszystko
> sie u mnie ostatnio albo rozwala albo juz
> sie rozwaliło (poza samym kodem :U)

Posortuj sobie rzeczy w kieszeniach :)

--
Edek

do góry

W dniu 2012-10-16 23:02, Baranosiu pisze:

> ciąg. Natomiast sama możliwość ustawienia elementów zbioru w ciąg
> (przeliczalność) jest (o ile się nie mylę :D) warunkiem niezbędnym na
> istnienie algorytmu sortującego (rozumianego jako "sekwencja
> instrukcji" - niekoniecznie skończona, być może sortująca w sensie
> granicznym).

Jeśli przez sortowanie rozumiemy znalezienie odwzorowania
z liczb naturalnych z zbiór, które zachowuje porządek, to ok.
Ale możesz bez trudu zbudować strukture danych, która
przechowa potencjalnie nieskończony zbiór z pynktami
skupienia, np wszytkie liczby postaci 1/n i 0 ;)

> Miałem na myśli to, że samo istnienie porządku liniowego (czy dobrego
> porządku, masz rację, na jedno wychodzi) nie gwarantuje istnienia
> algorytmu sortującego (w czasie skończonym bądź w sensie granicznym
> przy liczbie kroków dążącej do nieskończoności).

I znów zahaczamy o nieskończoność w algorytmach.

Ujmę to tak: mając dowolnej mocy zbiór*),
aby posortować algorytmicznie jego dowolny skończony
podzbiór (ustawić go w ciąg) potrzeba/wystarczy porządek
liniowy.


*) Nie, żeby na komputerze mógł się pojawić kiedykolwiek
większy niż przeliczalny;)


pzdr
bartekltg

do góry

Dnia 16.10.2012 M.M. <m...@g...com> napisał/a:
> W dniu wtorek, 16 października 2012 22:54:59 UTC+2 użytkownik PK napisał:
>> Do posortowania potrzebny jest zbiór z porządkiem liniowym, czyli
>> spełniający wszystkie jego własności. Sortowanie jest właśnie
>> "układaniem elementów zgodnie z porządkiem liniowym". To jest
>> w pewnym sensie z definicji oczywiste.
>> Przechodniość jest tylko jedną z nich. Wymieniłem ją, ponieważ
>> wymieniona przez Ciebie relacja była właśnie nieprzechodnia.
> Jaki jest przyklad zbioru z czesciowym porzadkiem ktorego nie
> da sie posortowac?
> Pozdrawiam


A
/ \
B C
\ /
D

Elementy B i C nie są w relacji i nie da się ich "porównać".

do góry

W dniu 2012-10-16 23:07, M.M. pisze:

> Jaki jest przyklad zbioru z czesciowym porzadkiem ktorego nie
> da sie posortowac?

{a,b,c} z porządkiem
{a>b, c>b}

Za mały?
Zbiorem będą liczby zespolone |C.

porządek:
x > y <=> Real(x)-Real(y)>0 i Imag(x)-Imag(y)>0


Pzdr
bartekltg

do góry

W dniu wtorek, 16 października 2012 23:20:34 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-16 23:07, M.M. pisze:
> > Jaki jest przyklad zbioru z czesciowym porzadkiem ktorego nie
> > da sie posortowac?
> {a,b,c} z porządkiem
> {a>b, c>b}
Czyli relacja czesciowego porzadku nic nie mowi o tym, ze porownywanie
jest zdefiniowane dla kazdej pary elementow ze zbioru? Jesli tak, to
by wszystko mi wyjasnialo :)
Pozdrawiam

do góry