Dyskusja:Algorytm: Różnice pomiędzy wersjami

Ten nowy wstęp był straszny. Ja rozumiem, że autor chciał był precyzyjny, ale nie można pisać w sposób tak hermetyczny we wstępie do artykułu. Na początku w kilku zdaniach należy przedstawić temat. Dopiero potem w treści artykułu można rozpisywać się, co jest, a co nie jest algorytmem. Zachęćmy czytelnika do poznania tematu, zamiast strzelać do niego od razu z grubej rury.

Po tej małej dygresji trochę merytorycznych zarzutów:

Algorytm to skończony zbiór jasno zdefiniowanych, możliwie elementarnych kroków koniecznych do wykonania pewnego zdania w skończonym czasie.

Algorytmami nie są:

Podać liczbę o 1 większą od najmniejszej 1000000 cyfrowej liczby pierwszej

*krok 1: podaj najmniejsza 1000000 cyfrowa liczb pierwsza

*krok 2: dodaj do niej 1

Nie jest to algorytm gdyż nie składa się z możliwie elementarnych kroków.

Kroki wcale nie muszą być elementarne, wszystko zależy od poziomu abstrakcji języka zapisu. Dla przykładu mamy trzy metody obliczania iloczynu 3 i 3:

Metoda 1:

wynik=3*3 

Metoda 2:

wynik=3+3+3

Metoda 3:

move acc, 0                  #kopiuje 0 do akumulatora
add acc, 3                   #dodaje 3 do akumulatora
add acc, 3                     
add acc, 3                     
move EF21A29C, acc           #kopiuje zawartość akumulatora do komórki pamięci – adres w hex

Czy pierwsza metoda jest algorytmem skoro działanie mnożenia da się rozpisać na bardziej elementarne operacje w drugim i trzecim przykładzie? Wszystkie te metody obliczania iloczynu są algorytmami. Dla pierwszej zdefiniowano wcześniej operacje mnożenia. Druga została zapisana w języku pozbawionym tej operacji. Trzecia metoda nie opiera się na zmiennych, tylko operacjach procesora. Tak prosty algorytm da się rozpisywać jeszcze dużo dalej, aż do granicy mikroświata. Algorytmem jest każdy zestaw kroków, które są jasno zdefiniowane, czyli zapisane w języku sformalizowanym.

Podać największą liczbę naturalna (przy założeniu, że taka istnieje, ale nie jest to ważne dla rozpatrywanego przykładu)

*krok 1: przypisz pewnej zmiennej x wartość 0

*krok 2: sprawdź czy istnieje liczba większa od x przez sprawdzenie czy po dodaniu do x liczby 1

*otrzymany wynik będzie większy niż x

*krok 3: jeśli x + 1 > x, przypisz x wartość x + 1 i skocz do kroku 1

Nie jest to algorytm gdyż nie poda największej liczby naturalnej w skończonym czasie.

Ten przykład jest nawet ciekawy. Każdy komputer, na którym puścimy taki algorytm skończy swoją pracę dosyć szybko. Liczby zawsze są reprezentowane ze skończoną precyzją. Kiedy licznik się zapełni, to kolejna liczba nie będzie już większa. Większość programów nada liczbie wartość nieskończoności i zwróci błąd przepełnienia.

Każdy przykład algorytmu musi mieć jakiś sens. Takie wymyślanie algorytmów z sufitu nic nie wznosi i tylko ogłupia czytelnika.

Superborsuk 00:02, 26 lis 2004 (CET)[odpowiedz]

Dodałem 'w skończonej liczbie kroków', bo tak mnie uczyli na Polibudzie.

--zolv 5 lip 2005 19:11 (CEST) Ale co to są "jasno zdefiniowane" czynności? Czy będzie jasno zdefiniowaną czynnością coś takiego:

Zadanie: Wyznaczyć algorytm rozkładu liczby na czynniki pierwsze (wiemy, że zadanie nie jest banalne)

Algorytm: krok 1. Wyznacz rozkład liczby na czynniki pierwsze.

Określenie czy coś można rozbić jescze na mniejsze kawałki czy nie zależy od interpretacji człowieka (tak jak podane wyżej 3 metody zadania 3*3). Stąd też uważam, że powinno być coś takiego (improwizacja) "zbiór możliwie elementarnych czynności..." lub coś podobnego. ale nie "jasno zdefiniowanych". W zasadzie to słowo "jasno" jest tutaj zbędne i chaczy o NPW, bo to czy coś jest jasne dla kogoś czy nie to kwestia indywidualna, a jeśli coś jest zdefiniowane to chyba wystarczy.

Dodatkowo skończona liczba kroków nie determinuje skończonego czasu, natomiast odwrotnie jest poprawnie. stąd też zamieniłbym skończoną liczbę kroków na skończony czas.

W efekcie podtrzymałbym swoją poprzednią wersję: Algorytm to skończony zbiór zdefiniowanych, możliwie elementarnych kroków koniecznych do wykonania pewnego zdania w skończonym czasie.

Właściwie powinno być 'Algorytm to uporządkowany i skończony zbiór jasno zdefiniowanych czynności'. W gruncie rzeczy jeśli zbiór jest skończony, to nie trzeba by pisać 'w skończonej liczbie kroków'. Ale że zbiór jest uporządkowany, to na pewno.

Ogromna większość problemów związanych z codziennym życiem jest rozwiązywana przez algorytmy N-P zupełne a nie czasem problemy są NP zupełne a nie algorytmy? -zolv 16:49, 10 listopad 2005 (CET)

jestem na lekcji i chcę do domu!!!!!!!!1