Użytkownik "notb" napisał w wiadomości grup
dyskusyjnych:s...@n...notb-home.
..

>Tak działa nauka. Ludzie tworzą jakieś twierdzenia, dowodzą ich i
>publikują. Potem każdy może ich używać i pisze się formułki takie jak

Ale rozumiesz różnicę pomiędzy cytowaniem a plagiatem?

>znane). Studenci matematyki / zmatematyzowanej infy (np. MIMu) są
>do tego przyzwyczajeni. Studenci politechnik raczej nie.

Studenci rżną wszystko co nie jest przybite gwoździkami. Niektórym to nawet
gwoździki nie przeszkadzają.

>Wbrew pozorom istnieją inne systemy operacyjne niż Linux.

Wbrew pozorom można to zrobić z MS Windows (Google ci się zacięło? Manpagez
i die.net zdechło?)

A samo qsort() ma deklarację gdzieś w stdlib.h, czyli raczej nowość to nie
jest i od rodzaju systemu nie zależy.


--- news://freenews.netfront.net/ - complaints: n...@n...net ---

do góry

Dnia 16.10.2012 M.M. <m...@g...com> napisał/a:
> W dniu wtorek, 16 października 2012 20:39:53 UTC+2 użytkownik notb napisał:
>> Aby sortowanie miało sens (teoretyczny) musi istnieć jakaś metoda
>> porównywania, czyli na zbiorze musi istnieć jakiś porządek liniowy.
>
> No wlasnie jak to bylo? Na pewno nie wystarczy ze istnieje metoda
> porownywania. Typowy przyklad z programow szachowych: program A
> wygrywa z programem B, B wygrywa z C, a C wygrywa z A - da sie
> porownac, ale jak to sensownie posortowac (bez dodatkowych
> zabiegow)?
>

Musi być tzw. dobry porządek liniowy. Porządek liniowy to zbiór z
relacją R, która spełnia 3 własności:
1) zwrotność: aRa (a jest w relacji z a)
2) przechodniość: aRb i bRc => aRc
3) antysymetryczność: jeśli aRb to not(bRa) (jeśli a jest w relacji z
b, to b nie jest w relacji z a)
"Dobry porządek" to porządek liniowy, w którym każdy niepusty podzbiór
danego zbioru ma element najmniejszy (w sensie relacji R).

W podanym przez Ciebie przykładzie szachowym z relacją "lepszy niż"
nie ma elementu "najmniejszego" więc nie jest to dobry porządek
liniowy czyli nie da się posortować zbioru relacją "lepszy niż" :D

do góry

W dniu 2012-10-16 21:49, Baranosiu pisze:
> Dnia 16.10.2012 M.M. <m...@g...com> napisał/a:
>> W dniu wtorek, 16 października 2012 20:39:53 UTC+2 użytkownik notb napisał:
>>> Aby sortowanie miało sens (teoretyczny) musi istnieć jakaś metoda
>>> porównywania, czyli na zbiorze musi istnieć jakiś porządek liniowy.
>>
>> No wlasnie jak to bylo? Na pewno nie wystarczy ze istnieje metoda
>> porownywania. Typowy przyklad z programow szachowych: program A
>> wygrywa z programem B, B wygrywa z C, a C wygrywa z A - da sie
>> porownac, ale jak to sensownie posortowac (bez dodatkowych
>> zabiegow)?
>>
>
> Musi być tzw. dobry porządek liniowy. Porządek liniowy to zbiór z

Nieprawda.

To, że porządek jest dobry nie ma nic wspólnego
z możliwością posortowania. Liczby rzeczywiste z "naturalną"
relacją > - to nie jest dobry porządek (zbiór (0,1) choćby:) )
A posortować się je da (na osi liczbowej leżą posortowane:)

Do posortowania wystarczy samo to, ze porządek jest liniowy.

> "Dobry porządek" to porządek liniowy, w którym każdy niepusty podzbiór
> danego zbioru ma element najmniejszy (w sensie relacji R).


pzdr
bartekltg

do góry

Dnia 16.10.2012 bartekltg <b...@g...com> napisał/a:
> W dniu 2012-10-16 21:49, Baranosiu pisze:
>> Dnia 16.10.2012 M.M. <m...@g...com> napisał/a:
>>> W dniu wtorek, 16 października 2012 20:39:53 UTC+2 użytkownik notb napisał:
>>>> Aby sortowanie miało sens (teoretyczny) musi istnieć jakaś metoda
>>>> porównywania, czyli na zbiorze musi istnieć jakiś porządek liniowy.
>>>
>>> No wlasnie jak to bylo? Na pewno nie wystarczy ze istnieje metoda
>>> porownywania. Typowy przyklad z programow szachowych: program A
>>> wygrywa z programem B, B wygrywa z C, a C wygrywa z A - da sie
>>> porownac, ale jak to sensownie posortowac (bez dodatkowych
>>> zabiegow)?
>>>
>>
>> Musi być tzw. dobry porządek liniowy. Porządek liniowy to zbiór z
>
> Nieprawda.
>
> To, że porządek jest dobry nie ma nic wspólnego
> z możliwością posortowania. Liczby rzeczywiste z "naturalną"
> relacją > - to nie jest dobry porządek (zbiór (0,1) choćby:) )
> A posortować się je da (na osi liczbowej leżą posortowane:)
>
> Do posortowania wystarczy samo to, ze porządek jest liniowy.

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
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

>
> > "Dobry porządek" to porządek liniowy, w którym każdy niepusty podzbiór
> > danego zbioru ma element najmniejszy (w sensie relacji R).
>
>
> pzdr
> bartekltg
>
>
>
>

do góry

W dniu wtorek, 16 października 2012 21:18:55 UTC+2 użytkownik bartekltg napisał:
> Bardzo się z tego cieszę;)
> A co do szybkości rand - nieraz do 'pierdółek'
> przydałby się szybszy:)
Nie tak dawno szukalem jeszcze szybszego od standardowego
randa z c++. Problem na tyle prosty, ze waskim gardlem
byla wlasnie stanardowa funkcja rand.
Pozdrawiam

do góry

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;-)

> 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.

Chodziło mi tylko o mieszanie w to pojęcia dobrego porządku
zbioru. Nie ma ono tu, nieżależnie od wybranej definicji,
żadnego znaczenia.

Każdy porządek liniowy w zbiorach skończonych jest dobry.
I skończone zbiory z liniowym porządkiem ortujemy algorytmem.

Zbór przeliczalny: wszystkie liczby wymierne >0
nie jest dobrze uporządkowany (przy 'naturalnym porządkiem').
Cały zbiór nie ma elementu najmniejszego.

Z drugiej strony, w zbiorze dowolnej mocy istnieje dobry
porządek (twierdzenie z nazwiskiem). Więc możesz mieć
pewną zmodyfikowaną relację <, taką, że porządek jest
dobry. Ale sprawy sortowania to nie zmienia,
potencjalnie możesz je uporządkować, ale ciągom
i algorytmom nie zrobi to różnicy.

pzdr
bartekltg

do góry

On 2012-10-16, bartekltg <b...@g...com> wrote:
> http://www.cplusplus.com/reference/std/random/
>
> Bardzo się z tego cieszę;)

No ja też, ale bez przesady. Przez te 10 lat zdążyłem napisać
lub znaleźć biblioteki robiące to samo, ale fajnie, że się wreszcie
ogarnęli. Nie skróci mi to czasu kodowania, ale skróci tłumaczenie innym
/ pisanie dokumentacji.

> A co do szybkości rand - nieraz do 'pierdółek'
> przydałby się szybszy:)

Jak Ci zależy na szybkości, to zrób to, co ludzie robią od dziesiątek
(no... setek) lat. Przygotuj sobie randomy wcześniej :).

Kiedyś trzeba było je kupić i przesyłać (początkowo w kopercie ;P).

Teraz wystarczy puścić na kilka godzin jakiś bardzo dobry generator
(albo zły, ale odpowiadający Twoim potrzebom) i masz spokój.
Do testów i jakichś prostych zastosowań ideał, bo zazwyczaj i tak używa
się stałego seed'a, a wszystko przyspiesza kilkukrotnie.

Jeśli Twoje programy robią jakieś skomplikowane obliczenia między
losowaniami, to można puścić oddzielny proces z RNG (i np. bufor
na RAMdisk'u). Wtedy to randomy czekają na program, a nie odwrotnie :).

Poza tym sprzętowe generatory są już na tyle tanie i małe, że pewnie
niedługo po prostu trafią do kompów jako kolejny "ficzer" na płycie
głównej albo doklejone do CPU/GPU.

pozdrawiam,
PK

do góry

On 2012-10-16, M.M. <m...@g...com> wrote:
> No wlasnie jak to bylo? Na pewno nie wystarczy ze istnieje metoda
> porownywania. Typowy przyklad z programow szachowych: program A
> wygrywa z programem B, B wygrywa z C, a C wygrywa z A - da sie
> porownac, ale jak to sensownie posortowac (bez dodatkowych
> zabiegow)?

To nie jest porządek liniowy. Wikipedię ukradli? :]
Porządek liniowy jest porządkiem częściowym. Porządek częściowy
jest m.in. przechodni.

> to byla relacja czesciowego porzadku?

Za mało. Częściowy porządek wyznacza np. inkluzja. Dorzucenie słowa
"liniowy" oznacza, że porównywalne są każde 2 elementy zbioru. Czyli
możesz ten zbiór ułożyć w łańcuch.

Nie znaczy to oczywiście, że nie istnieją problemy z takim "sortowaniem"
na płaszczyźnie (np. ze wspomniają inkluzją). Nie mniej powszechnie
przez sortowanie rozumie się właśnie testowanie porządku liniowego,
czyli to co robimy dla liczb rzeczywistych.

pozdrawiam,
PK

do góry

On 2012-10-16, Baranosiu <r...@w...pl> wrote:
> To zależy jak się rozumie pojęcie "posortować", bo w CIĄG rosnący to

Da się na kompie, bo pracujesz w skończonej pamięci.
Problem matematyczny "ustawianie liczb w ciąg rosnący" wymaga dobrego
porządku, ale to nie ta sytuacja.

pozdrawiam,
PK

do góry

W dniu wtorek, 16 października 2012 22:41:57 UTC+2 użytkownik PK napisał:
> To nie jest porządek liniowy.
To wiem.

> Porządek liniowy jest porządkiem częściowym.
Tak mi sie zdawalo.

> Porządek częściowy jest m.in. przechodni.
Tu nie rozumiem juz nic, jesli jest przechodni, to
nie wystarczy do posortowania?

Pozdrawiam

do góry