Zamierzam udzielić tej samej odpowiedzi, której udzieliłem poprzednim razem, gdy pojawiło się to pytanie.

Po pierwsze, zrozum, że w chwili pisania tego tekstu nie ma dobrej formalnej definicji „algorytmu”. Kluczowym słowem jest tutaj „formalny”.

Jednak istnieją inteligentnych ludzi, którzy nad tym pracują.

Wiemy, że czymkolwiek jest „algorytm”, znajduje się gdzieś pomiędzy „funkcją matematyczną” a „programem komputerowym”.

Funkcja matematyczna to formalne pojęcie odwzorowania danych wejściowych na wyjściowe. Na przykład „sortowanie” to odwzorowanie między sekwencją możliwych do uporządkowania pozycji a sekwencją możliwych do uporządkowania elementów tego samego typu, które odwzorowuje każdą sekwencję na jej uporządkowaną sekwencję. Ta funkcja może być zaimplementowane przy użyciu różnych algorytmów (np. sortowanie przez scalanie, sortowanie na stosie) .Każdy algorytm z kolei może być zaimplementowane przy użyciu różnych programów (nawet z tym samym językiem programowania).

Najlepszym podejściem do tego, czym jest „algorytm”, jest to, że jest to rodzaj klasy równoważności programów, gdzie dwie programy są równoważne, jeśli robią „zasadniczo to samo”. Dowolne dwa programy, które implementują ten sam algorytm, muszą obliczyć tę samą funkcję, ale odwrotność nie jest prawdą.

Podobnie istnieje klasa równoważności między algorytmami, gdzie dwa algorytmy są równoważne, jeśli obliczają tę samą funkcję matematyczną .

Najtrudniejszą częścią tego wszystkiego jest próba uchwycenia tego, co rozumiemy przez „w zasadzie to samo”.

Jest kilka oczywistych rzeczy, które powinniśmy uwzględnić. Na przykład dwa programy są zasadniczo takie same, jeśli różnią się jedynie zmiennymi nazwami. Większość modeli języków programowania ma natywne pojęcia „równoważności” (np. Redukcja beta i konwersja eta w rachunku lambda), więc powinniśmy je również wrzucić.

Niezależnie od wybranej relacji równoważności, daje nam to pewną strukturę . Algorytmy tworzą kategorię ze względu na fakt, że stanowią ilorazową kategorię programów. Wiadomo, że pewne interesujące relacje równoważności prowadzą do interesujących struktur kategorialnych; na przykład kategoria prymitywnych algorytmów rekurencyjnych jest uniwersalnym obiektem w kategorii kategorii. Ilekroć zobaczysz taką interesującą strukturę, wiesz, że ta linia zapytania prawdopodobnie będzie przydatna.

Komentarze

• Dziękuję za dokładną odpowiedź, po prostu kolejne pytanie. Jeśli weźmiemy pod uwagę dowolny program, niezależnie od tego, co robi, nadal otrzymuje on pewne dane wejściowe i postępuje zgodnie z niektórymi instrukcjami oraz daje pewne wyniki w trakcie ich wykonywania. Mogą nawet nie ' rozwiązać żadnego problemu (jak to nazywamy), ale nadal jest to mapowanie. czy to znany algorytm, mam na myśli dowolny program?
• Jeśli ' czytam Cię poprawnie, ' ponowne pytanie, czy formalna definicja algorytmu ” ” powinna, czy nie powinna zawierać pod warunkiem, że musi to być ” przydatne „. Powiedziałbym ” nie „, choćby dlatego, że ' nie można tego sformalizować pojęcie.
• przepraszam! mój angielski nie jest dobry, więc mówisz ” nie ” do czego? przyznajesz, że ' nie da się sformalizować użyteczności programu i po prostu z definicji każdy program jest algorytmem? czy też mówisz, że ' czy konieczne jest rozważenie użyteczności obok algorytmu?
• Nie ' nie sądzę, że formalna definicja algorytmu ” ” powinien wymagać, aby był użyteczny, ponieważ ” przydatne ” może ' t być formalnie zdefiniowane.
• Twoja odpowiedź jest najbardziej przydatna w tym wątku +1. Uważam, że ” zasadniczo to samo „, masz na myśli ” semantycznie równoważne „. Myślę też, że wszystkie programy są zasadniczo algorytmami (jak mówi OP), ponieważ wszystkie programy są implementacjami, które mapują pewne dane wejściowe na niektóre dane wyjściowe, nawet jeśli mapowanie to jest niejawne. Jak powiedziałeś, wszystko zależy od perspektywy.

Ostatecznie różnica polega na perspektywie . Program to program: sekwencja instrukcji w jakimś języku, być może w języku programowania lub instrukcjach na poziomie maszyny. Algorytmy są zwykle opisywane na wyższym poziomie niż instrukcje maszynowe lub instrukcje języka programowania, ale poziom jest dość elastyczny. Na przykład, w pewnych okolicznościach, „Sortuj tablicę, a następnie spójrz na $ k $ ten element” jest bardzo dobrym opisem algorytmu do znajdowania $ k $ tego największego obiektu w tablicy; w innych okolicznościach możesz chcieć bardziej szczegółowo opisać sposób sortowania.

Jak mówisz, algorytm to coś w rodzaju „procesu lub zestawu reguł, których należy przestrzegać podczas obliczeń lub innego problemu -rozwiązywanie operacji, zwłaszcza przez komputer ”. Zatem dosłownie każdy program jest algorytmem. Zwykle jednak mówimy o programach implementujących algorytmy. Zazwyczaj opisując algorytm, unikamy niskopoziomowych szczegółów dotyczących tego, w jaki sposób rzeczy są implementowane, zakładając, że kompetentny programista byłby w stanie zaimplementować go w wybranym przez siebie języku.

Komentarze

• Myślę, że precyzja algorytmu jest związana z koncepcją matematyczną, rachunkiem lambda lub maszyną Turinga, nadal nie ' nie wiem, co to jest język abstrakcji? matematyka lub język naturalny z wieloma rozmytymi instrukcjami
• @Ahmad Algorytm to nieformalna koncepcja. Nie ma formalnej definicji. W pewnym sensie ' jest jak dowód matematyczny, który różni się od formalnego dowodu w formalnym systemie dowodowym. Uważamy, że nieformalne dowody można ” rozszerzyć ” do formalnych dowodów w dowolnym wybranym (wystarczająco silnym) formalnym systemie dowodowym, tak jak każdy algorytm można w pełni zaimplementować w dowolnym języku programowania (Turing-complete).

Algorytmy w języku Turing -kompletne nastawienie jest zwykle określane przez dane wejściowe i wyjściowe. Prawdziwe programy robią więcej;

• komunikują się z użytkownikiem,
• komunikują się z innymi maszynami,
• reagują na otoczenie,
• nie przerywają pracy i nadal są przydatne,

i nie tylko. Te rzeczy zwykle nie są brane pod uwagę w algorytmach lub teorii obliczeń, ale mają zasadnicze znaczenie dla większości programów.

Komentarze

• To bardzo dobra uwaga. Ale czy masz na myśli coś takiego, jak „, zwykle określane jako sposób mapowania wejścia na wyjście „? Samo określenie wejścia i wyjścia nie jest ' t wystarczające: np. Scalanie i szybkie sortowanie dają te same dane wyjściowe z dowolnego wejścia, ale nie są ' brane pod uwagę być tym samym algorytmem.
• @DavidRicherby Myślałem o specyfikacji w sensie PL; nie ' nie określamy niczego innego, więc algorytmy nie mogą robić nic innego. Oczywiście, aby opisać konkretny algorytm, musimy podać więcej niż specyfikację.
• Zalety, ale jeśli przyznamy, że ostatecznie każdy program jest algorytmem, nie ' wiem, jak te sprawy, do których się odnosiliście, są mierzone w algorytmie. Może temat AI ?!
• Kto by to przyznał i dlaczego? A co masz na myśli przez miarę? (I na pewno nie ' nie widzę tutaj kąta AI).
• @Raphael Mogę to przyznać (patrząc na składnię, wszystkie programy wyglądają podobnie, są to sekwencje instrukcji lub mapowanie danych wejściowych na wyjściowe), po prostu nie ' nie wiem, jak inne cechy programu (te, do których się odwołałeś) można wyodrębnić z tej definicji. na przykład różnica między quick-sort a MATLAB lub Windows Media Player !!

• Algorytm to systematyczne podejście do rozwiązania określonego problemu.

• Program to zestaw instrukcji, których ma przestrzegać komputer.

Dlatego program nie musi nawet rozwiązywać problemu.Jestem pewien, że wszyscy możemy wymyślić kilka programów, które spowodowały więcej problemów niż rozwiązały. Program może być implementacją wielu algorytmów lub algorytm można zaimplementować, łącząc razem wiele programów. Program nie może nawet zawierać żadnych algorytmów. Na przykład pusty program, który po prostu wychodzi, a może nawet Hello World, mógłby zostać uznany za program bez algorytmu.

Ponieważ algorytm rozwiązuje określony problem, koncentruje się na określonej całościowej koncepcji. Dlatego algorytm zapewnia abstrakcyjne kroki przetwarzania jednego zestawu powiązanych informacji w inny zestaw informacji pochodnych. Program nie wymaga, aby jego części składowe były w ogóle powiązane koncepcyjnie. Na przykład program może mieć jajko wielkanocne, ale coś, co właściwie nazywa się algorytmem, nie powinno. Możesz mieć wirusa lub trojana czającego się w programie, ale nie w algorytmie. Algorytm najbliższy temu mógłby być czymś w rodzaju backdoora w algorytmie szyfrującym, gdzie planowana wada jest częścią relacji informacyjnej ustanowionej przez algorytm.

I na koniec program. skrót od programu komputerowego, tautologicznie wymaga komputera. Algorytm tego nie robi. Jeśli systematycznie oddzielam koszule, spodnie i skarpetki od prania przed ich odłożeniem, to jest to algorytm. Zajmuje się powiązanymi danymi wejściowymi i wyjściowymi, można je opisać na schemacie blokowym i ma obliczalne konsekwencje pod względem wydajności (na przykład liczba elementów odzieży, które należy porównać, aby znaleźć pasujące skarpetki).

Algorytm to koncepcja lub idea. Jest to formalne podejście do rozwiązania problemu. Algorytmy można wyrazić lub zaimplementować w różnych językach programowania (zwykle prawie każdy język może implementować dowolny algorytm). Aby zapoznać się z przykładami, należy przeczytać algorytmy sortowania w Wikipedii.

Program komputerowy to określona sekwencja instrukcji w określonym języku programowania . Program może zawierać implementację wielu algorytmów. Excel to program, ale jego możliwości sortowania są przejawem działania algorytmu.

Algorytm to niezależny zbiór operacji wykonywanych krok po kroku w celu rozwiązania określonego problemu lub klasy problemów.

Program komputerowy to sekwencja instrukcje, które są zgodne z regułami określonego języka programowania, napisane w celu wykonania określonego zadania z komputerem.

Algorytmy są ogólne i muszą być przetłumaczone na specyficzny język programowania (zaimplementowany).

Komentarze

• Ale cały problem polega na tym, że program (albo jego kod źródłowy, albo skompilowany plik binarny ) to ” samodzielny zestaw operacji krok po kroku, które należy wykonać w celu rozwiązania określonego problemu lub klasy problemów. ”
• Ale to nie jest ' t. Program nie jest tym operacje ose, ale ich implementacja : coś, co wykonuje je w określonym kontekście. Na przykład. narzędzie Unix sort nie jest algorytmem sortowania, używa algorytmu sortowania.

Algorytm przedstawia nasz pomysł lub rozwiązanie konkretnego problemu w podejściu krok po kroku. jest to tylko rozwiązywanie problemów i podejście zrozumiałe dla człowieka, a nie system komputerowy

Program to instrukcje krok po kroku realizowane w celu rozwiązania problemu przez system komputerowy. Musi być zrozumiały nie tylko dla programisty, ale i dla komputera.

Komentarze

• Witamy w Computer Science Stack Exchange. Przeczytaj cs.stackexchange.com/tour.if , jeszcze tego nie zrobiłeś.

Myślę, że inne odpowiedzi tutaj pomijają ważny punkt. Definicja „algorytmu”, której mnie uczono, zawierała wymóg, aby procedura zatrzymuje się na wszystkich wejściach . To oczywiście sprawia, że „program” jest szerszą klasą procedur niż „algorytm”, ponieważ niektóre programy zatrzymują się na wszystkich wejściach, a inne nie.

Komentarze

• To nie jest uniwersalne. Definicja, której mnie nauczono, nie ' nie obejmowała tego wymagania.

Oto kilka sposobów na wyznaczenie granicy między algorytmem a programem:

Sensowny cel

Programy są pisane w określonym celu i stanowią próbę osiągnięcia cel. Algorytmy można postrzegać jako narzędzia do osiągnięcia tego celu.

Np. śrubokręt to algorytm modyfikujący stan śruby, ale sam śrubokręt nie ma celu, aby to zrobić.Cel leży w głowie operatora śrubokręta, który trzyma program jak stawianie półek.

Logika biznesowa

Ten punkt silnie odnosi się do celu programu. Ponieważ programy mają cele, nieuchronnie zawierają w sobie fragmenty prawdziwego świata, takie jak konkretne daty, pomiary, technologie, nazwy itp.

Z drugiej strony algorytmy nie zawierają ani logiki biznesowej, ani bitów świata rzeczywistego i zamiast działać na określone wartości działają na zmiennych.

Np. w tym sensie możesz porównać funkcję matematyczną, taką jak f(x) = x^2, która jest abstrakcyjna i operuje na zmiennych, z przepisem gotowania, który zawiera dokładne wartości (przynajmniej jedną w celach informacyjnych).

Wynik

Ten punkt silnie odnosi się do logiki biznesowej programu. Agent (podobnie jak użytkownik przeglądarki internetowej) wykorzystuje wynik programu, a nie wynik algorytmu.

Np. konsument przepisu kulinarnego spożywa ciasto, a nie w wyniku ubijania śmietany lub podgrzewania piekarnika.

Komentarze

• Być może lepiej byłoby powiedzieć, że czy śrubokręt nie ' nie ma zamiaru przekręcać śrub? W codziennym języku angielskim z pewnością powiedzielibyśmy, że celem śrubokręta spełnia jest obracanie śrub: dokręcanie śrub jest dokładnie tym, do czego został zaprojektowany.
• Ponadto I ' Nie wiem, co masz na myśli przez ” logikę biznesową ” (wiele programów nie ma nic do zrobienia z biznesem) lub mówiąc, że algorytm ” nie zawiera ani logiki biznesowej, ani bitów świata rzeczywistego „. Na przykład mógłbym doskonale sformułować algorytm najkrótszej ścieżki w postaci miast i dróg, a nie wierzchołków i krawędzi. Czy algorytm nie ' t ” zawiera … bity świata rzeczywistego ” ?
• @DavidRicherby, masz rację, moje sformułowanie jest niejednoznaczne. Miałem na myśli znaczący cel. Obracanie śrub, aby obracać śruby, jest bezcelowe, podobnie jak sortowanie tablicy, która nigdy nie jest używana. Przez logikę biznesową rozumiem całą logikę programu z wyjątkiem logiki narzędzi i schematu stosu technologii, tj. Całą logikę, która faktycznie realizuje cel programu, tj. Logika biznesowa pieczenia ciasta polega na mieszaniu składników i pieczeniu i nie obejmuje nauki mieszania lub pieczenia ( co jest w tym przypadku ponownie wykorzystaną logiką narzędzi).
• @DavidRicherby, tak jak w przypadku bitów świata rzeczywistego , mam na myśli aktualizację, tj. program w przeciwieństwie do algorytmu musi się w jakiś sposób komunikować świat fizyczny. Z drugiej strony algorytm może być pojęciem czysto matematycznym.

I jestem prawie pewien, że inne odpowiedzi są wystarczająco dobre, aby przejąć inicjatywę, ale oto jak widzę różnicę między algorytmem a programem

• Algorytm składa się po prostu z kroków (niezależnych od komputera), które należy wykonać w celu rozwiązania problemu.

• Program to zestaw instrukcji dla określonego typu maszyny, aby zastosować algorytm do ćwiczenia .

Na przykład.

Powiedzmy, że masz algorytm, który ma krok dla dotarcie do określonego miejsca przed wykonaniem innego kroku. teraz, w jaki sposób ten etap dotarcia zostanie przeprowadzony, nie jest dokładnie zdefiniowany. możesz wybrać spacer, bieganie lub skorzystanie z autobusu, ale to zależy od tego, jak zdecydujesz się to zrealizować (który jest twoim prog ram).

Można powiedzieć, że algorytm jest abstrakcją programu, tj. brakuje dokładnych szczegółów, ale przedstawia plan, aby coś zrobić .