Najlepsza odpowiedź
Nie ma na to odpowiedzi.
Znajdźmy odpowiedź na to stwierdzenie problemu:
Q. Jak sprawdzić, czy któryś algorytm działa lepiej?
A. Najpopularniejsze sposoby porównywania algorytmów:
1) Złożoność czasowa
2) Złożoność przestrzenna
3) Jakość rozwiązania (może nie ma zastosowanie, jeśli proponuje dokładne rozwiązanie problemu). To może być ogromnym czynnikiem, jeśli mówimy o algorytmach przybliżenia.
4) Łatwość implementacji / adaptacji algorytmu. Niektóre algorytmy mogą wiązać się z dużym narzutem, aby poprawnie zaimplementować. Czasami są bardziej odpowiednie algorytmy na przykład w obliczeniach równoległych, większość uzna Bellmana-Forda za bardziej użytecznego niż algorytm Dijkstry ze względu na sposób działania Bellmana-Forda.
Jednak czas i złożoność nie są * zawsze * pożądana funkcja maksymalizacji; Podam dwa przykłady.
Jednym z nich jest „stabilność numeryczna” , cecha algorytmów zarówno w algebrze liniowej, jak i w równaniach różniczkowych. Poświęcimy zarówno więcej czasu algorytmicznego, jak i większą złożoność algorytmiczną na algorytmy, które są bardziej stabilne numerycznie. W algebrze liniowej niestabilność jest generalnie powodowana, gdy algorytm napotyka liczby zbyt bliskie zeru lub nieskończoność lub jedno i drugie, ponieważ skończona reprezentacja rozdzielczości liczb może zostać utracona. Ogólnie rzecz biorąc, powoduje to bardzo nieznacznie różne liczby, tylko kilka epsilonów różniących się od siebie (gdzie epsilon jest najmniejszą liczbą, którą można dodać do jednej na maszynie i uzyskać wynik! = 1), co powoduje duże różnice w odpowiedź. Tak więc, na przykład, poświęcamy dużo czasu i złożoności przestrzennej, „obracając się” w rozkładzie LU w celu uzyskania stabilnego algorytmu; bez obrotowej jednostki LU nie jest stabilna. Podobnie mamy algorytmy, które nie robią nic poza macierzami „warunków”, aby uniknąć niestabilności.
Drugi przykład to „solidność” w jej techniczny sens statystyczny. Odporność oznacza miarę lub algorytm, który * nie * jest wrażliwy na wartości odstające. Na przykład, kiedy dopasowuję linię najmniejszych kwadratów do zestawu punktów, linia może być mocno pochylona o jedną bardzo dużą wartość. Nawet jeśli mam 99 par liczb, które tworzą idealną linię pod kątem 45 stopni, jeśli dodam pojedynczą parę wartości odstających, dla których wartość Y jest sto razy większa niż „powinna” znajdować się na tej samej linii, dopasowana linia będzie poważnie odchylony od linii 45 stopni. Algorytm „zrezygnuje” z idealnego dopasowania dla 99 punktów, aby lepiej przedstawić jeden punkt odstający. To jest * nie * solidne.
Solidne podejście metodą najmniejszych kwadratów polega na tym, że zamiast znajdować linię, która minimalizuje sumę kwadratów błędów utworzonych przy użyciu tej linii, znajduje linię, która minimalizuje * medianę * kwadratowe błędy utworzone przy użyciu tej linii. W tym przykładzie ta linia jest linią 45 stopni, a mediana kwadratów błędów wynosi zero, a punkt odstający (a nawet 98 bardziej szalonych wartości odstających) zostałby całkowicie zignorowany. Zostałaby znaleziona linia 45 stopni.
Istnieją podobne solidne algorytmy dopasowywania krzywych statystycznych, znajdowania kształtów itp. Jednak są one kosztowne w czasie, a czasem bardzo. Jednak koszt czasu jest tego wart, ponieważ solidne statystyki są skutecznie odporne na „szum” w sygnałach, gdzie metody najmniejszego kwadratu błędów nie są. Rzeczywisty świat jest pełen zarówno szumów, jak i wartości odstających, a niektóre z nich są spowodowane błędami człowieka lub maszyny, w szczególności w przypadku obrazów podzielonych na piksele lub próbkowanego dźwięku. W takich okolicznościach bardziej kosztowny, niezawodny algorytm może znaleźć sygnały w hałaśliwym środowisku, w którym szybsze algorytmy generują odpowiedzi tak zniekształcone przez szum, że są one bezużyteczne lub nawet niebezpieczne, jeśli zostaną zaakceptowane.
W niektórych przypadkach czas i złożoność przestrzeni nie są tak ważne, jak znalezienie odpowiedzi, która prawdopodobnie będzie modelować rzeczywisty sygnał pomimo szumu i degradacji sygnału.
Odpowiedź
Algorytmy wywodzące się z matematyki jako „receptury” do wykonywania obliczeń opartych na funkcjach, które można śledzić mechanicznie. W matematycznym światopoglądzie opartym na funkcjach wszystkie dane wejściowe muszą zostać określone na początku obliczenia, które przebiega w sposób zamknięty. Pojęcie algorytmu jest z natury nieformalne, ponieważ opis algorytmiczny nie jest ograniczony do żadnego pojedynczego języka ani formalizmu.
Być może najstarszym przykładem jest algorytm Euclid do znajdowania wspólnych dzielników. Algorytmy wychwytują, co to znaczy, że obliczenia są „skuteczne”. Podobnie jak wzory matematyczne, algorytmy mówią nam, jak obliczyć wartość; w przeciwieństwie do nich, algorytmy mogą obejmować to, co teraz nazywamy pętlami lub rozgałęzieniami.
Rola algorytmu: biorąc pod uwagę pewną skończoną wartość wejściową x, algorytm opisuje kroki umożliwiające skuteczne przekształcenie jej w wartość wyjściową y, gdzie y jest f (x) dla niektórych funkcji rekurencyjnych f.
Algorytmy zostały przyjęte przez pierwszych informatyków w latach pięćdziesiątych XX wieku, którzy połączyli algorytmy z maszynami Turinga (TM, formalnym modelem obliczeń datowanym na rok 1936), porównując ich ekspresję.
Słynny i wpływowy podręcznik Knutha „The Art of Computer Programming, Vol. 1” pod koniec lat 60-tych spopularyzował centralne znaczenie algorytmów w informatyce. W swojej definicji algorytmów Knuth był zgodny z matematycznymi podstawami teorii obliczeń opartymi na funkcjach. „Istnieje wiele innych zasadniczo równoważnych sposobów sformułowania koncepcji efektywnej metody obliczeniowej (na przykład przy użyciu baz TM)”.
Knuth wyraźnie stwierdził, że algorytmy są zamknięte; żadne nowe dane wejściowe nie są akceptowane po rozpoczęciu obliczeń: „Algorytm ma zero lub więcej danych wejściowych, tj. wielkości, które są mu dane początkowo przed rozpoczęciem algorytmu”. Odróżnił algorytmy od arbitralnych obliczeń, które mogą obejmować operacje wejścia / wyjścia. Jednym z przykładów problemu, który nie jest algorytmiczny, podał następująca instrukcja z przepisu: „wrzuć lekko, aż mieszanina będzie krucha”. Ten problem nie jest algorytmiczny, ponieważ komputer nie może wiedzieć, jak długo mieszać; może to zależeć od jednego z zewnętrznych dynamicznie zmieniających się warunków, takich jak wilgotność, których nie można przewidzieć z wyprzedzeniem.
Chociaż nie ma zgody co do dokładnego pojęcia algorytmów, dyskusja Knutha na temat algorytmów pozostaje ostateczna.
Pierwszym językiem programowania wysokiego poziomu opracowanym specjalnie w celu określenia algorytmów był ALGOL (język ALGOrithmic). Wprowadzony pod koniec lat 50. i udoskonalany w latach 60. służył jako standard do publikacji algorytmów. Zgodnie z konceptualizacją algorytmów opartą na funkcjach, ALGOL nie dostarczył żadnych konstrukcji dla danych wejściowych i wyjściowych, biorąc pod uwagę te operacje poza zagadnieniem algorytmów. (Nic dziwnego, że ta nieobecność utrudniła przyjęcie ALGOL-u przez przemysł do zastosowań komercyjnych).
W latach sześćdziesiątych XX wieku pojawiły się liczne programy licencjackie z zakresu informatyki (CS). Według Association for Computing Machinery (ACM) liczba programów CS w USA wzrosła z 11 w 1964 r. Do 92 w 1968 r. Wzrostowi temu towarzyszyła intensywna aktywność na rzecz ugruntowania prawomocności tej nowej dyscypliny w oczach naukowców. społeczność. ACM odegrał kluczową rolę w tej działalności. W 1965 r. Ogłosił uzasadnienie i opis CS jako dyscypliny, która posłużyła jako podstawa jego zaleceń z 1968 r. Dla programów licencjackich CS.
W opisie CS ACM wskazał efektywną transformację informacji jako główny problem: „ Informatyka zajmuje się informacją w tym samym sensie, w jakim fizyka zajmuje się energią … Informatyk jest zainteresowany odkryciem pragmatycznych środków, za pomocą których można przekształcić informacje ”. Opis ten umieszcza algorytmy w centrum informatyki, ponieważ są one „receptami” na dokonywanie tych efektywnych przekształceń danych wejściowych w dane wyjściowe. W rzeczywistości ACM skupił się na algorytmach wyraźnie w następnym zdaniu swojego raportu:
„Zainteresowanie to prowadzi do badania skutecznych sposobów przedstawiania informacji, skutecznych algorytmów przekształcania informacji, efektywnych języków, za pomocą których można wyrażać algorytmy … i skuteczne sposoby osiągnięcia tego przy rozsądnych kosztach. ”
Mając centralny problem algorytmiczny, analogiczny do troski o energię w fizyce, pomógł ustalić CS jako uprawnioną dyscyplinę akademicką na równi z fizyka. Algorytmy pozostają w centrum informatyki do dnia dzisiejszego.
Współistnienie nieformalnego (opartego na algorytmach) i formalnego (opartego na TM) podejść do definiowania problemów, które można rozwiązać, trwa do dziś i można je znaleźć w wszystkie współczesne podręczniki na temat algorytmów lub obliczalności. Okazało się to bardzo wygodne dla informatyków, ponieważ pozwoliło nam opisać obliczenia algorytmiczne nieformalnie za pomocą „pseudokodu”, wiedząc, że można skonstruować równoważną maszynę Turinga.
– Problem można rozwiązać, jeśli można go określone przez algorytm. – Problem można rozwiązać, jeśli istnieje do niego maszyna Turinga.
Decyzja teoretyków i nauczycieli z lat 60. o umieszczeniu algorytmów w centrum CS została wyraźnie odzwierciedlona we wczesnych podręcznikach licencjackich. Jednak nie było jednoznacznej, standardowej definicji algorytmu, a różne podręczniki zdecydowały się inaczej zdefiniować ten termin. Podczas gdy niektóre podręczniki, takie jak ten autorstwa Knutha, starały się wyraźnie ograniczyć algorytmy do tych, które obliczają funkcje i dlatego są równoważne z maszynami Turinga, większość książek teoretycznych pozostawiła to ograniczenie dorozumiane, ale nie podano.
Wczesnym przykładem jest podręcznik Hopcrofta i Ullmana z 1969 roku, którego późniejsze wydania są używane do dziś: „Procedura to skończona sekwencja instrukcji, które można wykonać mechanicznie, np. program komputerowy …Procedura, która zawsze się kończy, nazywana jest algorytmem ”.
Ten opis algorytmu nie wyklucza wyraźnie niefunkcjonalnych obliczeń, takich jak przygotowywanie posiłków. Jednak ich przykłady różnych problemów jasno pokazują, że rozważali tylko obliczenia oparte na funkcjach. W rzeczywistości użyli ALGOL-a do swoich przykładów, który nie oferował nawet żadnych konstrukcji dla wejścia i wyjścia.
Od późnych lat 60-tych języki programowania wysokiego poziomu używane w praktyce i nauczane w programach CS przestały być związany algorytmicznymi ograniczeniami wczesnego ALGOL-u. Możesz pisać programy, które na bieżąco oddziałują ze swoim środowiskiem podczas obliczeń, takie jak systemy operacyjne, graficzne interfejsy użytkownika lub pojazdy automatyczne i inne roboty.
W odpowiedzi współczesne podręczniki programowania, takie jak Rice i Rice (1969) wyraźnie rozszerzył pojęcie algorytmów na problemy niefunkcjonalne. Podejście to, odzwierciedlające centralne znaczenie algorytmów bez ograniczania ich do obliczania funkcji, stało się typowe dla podręczników nieteorycznych. Tematem tych podręczników jest raczej metodologia programowania niż teoria obliczeń, a zasady matematyczne, na których opierają się nasze modele obliczeń, zostały odrzucone ze względu na praktyczność.
Pozornie definicja algorytmu w Rice and Rice i innych tego typu podręcznikach nie różni się od Hopcrofta i Ullmana: „Algorytm to przepis, zestaw instrukcji lub specyfikacja procesu, który ma na celu zrobienie czegoś. To coś zazwyczaj rozwiązuje jakiś problem ”. Jednak ich przykłady obliczalnych problemów nie opierają się już na funkcjach, uznając tylko rodzaj obliczeń, które Knuth odrzucił. Dwa takie przykłady, które podobno można rozwiązać za pomocą algorytmu, to robienie wódki ziemniaczanej i napełnianie rowu piaskiem; Knuth odrzuciłby oba z nich.
W tych podręcznikach nie było żadnych twierdzeń o równoważności TM dla ich „algorytmów”. Jednak uczniowie nie zostali poinformowani, że pojęcie algorytmów różni się od pojęcia Knutha i że w ten sposób poszerzył się zestaw problemów uznawanych za obliczalne. Łącząc szerszą, bardziej praktyczną konceptualizację algorytmów (a tym samym problemów obliczalnych) z teoriami, które głoszą, że bardzo obliczalny problem może być obliczony przez TM, program nauczania CS skoncentrowany na algorytmach pozostawił uczniów z błędnym wrażeniem, że ten szerszy zestaw problemów może rozwiązują również bazy TM.
Podczas gdy praktyczni informatycy już dawno poszli za przykładem Rice and Rice i poszerzyli koncepcję algorytmów poza obliczanie funkcji, teoretyczna informatyka zachowała matematyczny pogląd na świat obliczenia jako oparte na funkcjach i odpowiednio ograniczają nasze pojęcie problemu obliczeniowego. Dzieje się tak przynajmniej na poziomie licencjackim. Rezultatem jest dychotomia, w której społeczność informatyczna uważa algorytmy za synonimy z ogólnym pojęciem obliczeń („co robią komputery”), a jednocześnie jako równoważne z maszynami Turinga.
Pomyślałem Musiałem napisać tę długą odpowiedź, aby uświadomić ludziom tę dychotomię. Jak powiedziałem na początku, pojęcie algorytmu jest nieformalne. Możemy myśleć o tym jako o ekwiwalencie obliczania funkcji (lub o maszynach Turinga) lub możemy o tym myśleć jako o wszystkim, dla czego można napisać program, w tym interaktywnych programach czasu rzeczywistego, takich jak systemy operacyjne lub automatyczne samochody. Ale te dwie definicje nie są równoważne, pomimo powszechnego pomyłki, która jest wręcz przeciwna.