Dnia 16.10.2012 bartekltg <b...@g...com> napisał/a:
> 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 ;)

Owszem, to może rozwiązać pewną klasę problemów, ale jak mi się
"zachce" zmienić relację porządku i posortować "od nowa" to może być
problem - oczywiście problem teoretyczny, bo w praktyce na komputerach
operujemy zbiorami skończonymi.


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

Zgoda.


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

Nie wiem co przyniesie przyszłość, ale komputery analogowe na potęgę
były wykorzystywane przez Japończyków w latach 90-tych do zadań czasu
rzeczywistego (liczenie równań różniczkowych, teoretycznie przy
symulowaniu zderzeń galaktyk, a w praktyce wiadomo do czego :D).
Tak jak obecnie w układach FPGA programuje się połączenia między
bramkami logicznymi, tak tam program ustanawiał połączenia między
blokami realizującymi operacje w sposób analogowy :D