Dnia 16.10.2012 notb <P...@n...com> napisał/a:
> On 2012-10-16, Baranosiu <r...@w...pl> wrote:
>> Dla zbiorów dyskretnych (a ściślej dla dyskretnych ich reprezentacji w
>> maszynie) to jak najbardziej algorytm zadziała, ale nie wszystkie
>> zbiory są przeliczalne (a więc nie zawsze dają się posortować) i... z
>
> Ależ przeliczalność w ogóle nie jest konieczna (liczby rzeczywiste
> sortują się naprawdę dobrze - polecam sprawdzić :)).

Może i głupi jestem, ale posortuj mi zbiór (0,1) /* odcinek otwarty
liczb rzeczywistych od zera do jedynki */ od największego do
najmniejszego :D Można oczywiście ustanowić relację porządku, ale to
jeszcze nie sortuje zbioru (nie ustawia elementów w ciąg zgodnie z
relacją porządku :D). Wiem że podzbiory zbioru liczb rzeczywistych
świetnie się sortują... jeśli są skończone bądź dyskretne :D


> Aby sortowanie miało sens (teoretyczny) musi istnieć jakaś metoda
> porównywania, czyli na zbiorze musi istnieć jakiś porządek liniowy.

To jest warunek konieczny, ale nie wystarczający, zbiór musi być
jeszcze przeliczalny. Zbioru liczb rzeczywistych (bądź dowolnego
wypukłego jego podzbioru) nie da się ustawić w liniowy porządek (ale
już liczby wymierne się da, a że w komputerach liczby rzeczywiste
przybliżamy wymiernymi, to "w praktyce" to działa :D).


>
>> Wszystkie współczesne komputery cyfrowe (łącznie z kwantowymi) to
>> maszyny Turinga, więc rozróżnienia się nie robi, w tym sensie można
>> pominąć szczegóły maszyny, ale samo pojęcie algorytmu to coś więcej
>> niż "proces wykonywany przez maszynę cyfrową".
>
> Z tym "wszystkie komputery cyfrowe to maszyny Turinga" to taki trochę
> niepewny tekst (zależy co by nazwać komputerem).

Ok, zbyt ogólnie to napisałem, biję się w piersi :D


> Za to nie wszystkie języki programowania są zupełne (kompletne
> w sensie Turinga).

Można wręcz powiedzieć, że wszystkie implementacje języków
programowania nie są kompletne w sensie Turinga, bo nie ma czegoś
takiego jak nieograniczona pamięć (no może poza implementacjami na
komputery kwantowe, ale te dla odmiany nie są deterministyczne :D).

Algorytm w sensie matematycznym to tylko model, na tej samej zasadzie
jak mapa to nie to samo co terytorium, mapa pozwala poruszać się po
terenie i zawiera elementy przydatne z punktu widzenia jej
użytkownika, mapa sporządzona dla geologa może być zupełnie
nieprzydatna dla kierowcy samochodu czy dla wojska, teren jest jeden,
a map wiele i nie ma się co spierać nad wyższością jednej nad drugą (a
uniwersalnej mapy zadowalającej wszystkich możliwych użytkowników po
prostu nie ma :D).

Teoria teorią, a praktyka praktyką, dla początkującego adepta
informatyki chyba równie ważne (jeśli nie ważniejsze) jest także
intuicyjne rozumienie pojęcia algorytmu, w ten sposób może dobrać
odpowiedni model teoretyczny (mapę) do rozpatrywanego zagadnienia, a
modeli teoretycznych jest wiele i nie ma jednej "ogólnej teorii
wszystkiego" (teza Godla ;)).