Dnia 16.10.2012 Michoo <m...@v...pl> napisał/a:
> On 16.10.2012 04:12, Baranosiu wrote:
>> Dnia 15.10.2012 Michoo<m...@v...pl> napisał/a:
>>
>> Dochodzi jeszcze kwestia tego co rozumie się przez zbiór "czynnoiści
>> elementarnych"
>
> Ale one nie muszą być "elementarne". W algorytmie znajdowania przecięci
> zbiorów może być "posortuj oba zbiory w ciągi rosnące" bez
> wyspecyfikowania metody, nie trzeba wplatać logiki sortowania do środka.

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
algorytmu "dupa" :D Dziedzina KAŻDEGO algorytmu to nie tylko dane na
jakich on działa, ale także zbiór operacji jakie musi być w stanie
wykonać maszyna inaczej się nie da (spróbuj znaleźć przecięcie
zbiorów, jeśli maszyną jest na przykład kucharz, nie da się,
choć... kucharz może zrealizować algorytm sporządzenia zupy
pomidorowej :D).



>
>> , bo na przykład kiedyś konstruowano komputery
>> analogowe, które jedną "czynnością elementarną" przechodziły przez
>> nieskończoną liczbę stanów i algorytm działający na maszynie
>> analogowej może już nie być algorytmem na maszynie dyskretnej.
>
> Dlatego napisałem - "na pewnej abstrakcyjnej maszynie".

Na "abstrakcyjnej" czyli na żadnej :D Zwykle w informatyce przyjmuje
się w domyśle maszyny Turinga, ale samo pojęcie algorytmu nie musi ich
dotyczyć :D


>> Tak
>> więc definicja "abstrakcyjnej maszyny" jest też częścią algorytmu a
>> nie tylko same czynności
>
> Mamy maszynę, więc definiujemy w oparciu o nią algorytm. W tym sensie
> definicja maszyny jest częścią algorytmu. Nie wciągałbym jednak
> szczegółów maszyny do samego algorytmu.

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


>> Mnie na studiach uczono (a były to
>> lata 90-te), że tak na prawdę nie ma jednej uniwersalnej matematycznej
>> definicji czym jest algorytm, dlatego w różnych kontekstach przyjmuje
>> się różne "modele" tego pojęcia.
>
> Czy nie ma uniwersalnej to bym się kłócił, ale jak to zwykle im coś
> bardziej uniwersalne tym ogólniejsze. Istnieją więc też "definicje
> szczegółowe" np. "algorytm na NDTM", "algorytm na DNA", "algorytm na
> studencie".

Ok, są, ale to są tylko konkretne modele. Można na przykład
zdefiniować pojęcie algorytmu w oparciu o maszyny Turinga ale... takie
pojęcie algorytmu już nie będzie pasowało do "przepisu na zrobienie
pomidorowej". Ogólnej definicji algorytmu (w sensie matematycznym) nie
ma, a w informatyce przyjmuje się pewien "podzbiór" tego pojęcia w
kontekście określonej klasy maszyn, aby się na tym matematykę dało
uprawiać :D No ale to już wykracza poza główny temat wątku :D