algorytm - Algorithm


Z Wikipedii, wolnej encyklopedii

Schemat blokowy algorytmu ( algorytm Euklidesa ) do obliczania największy wspólny dzielnik (GCD) dwóch liczb a i b, w miejscach, nazwany A i B. wpływy algorytm przez kolejne odejmowania w dwóch pętlach: Jeśli test B ≥ a daje „tak” (lub prawda) (dokładniej liczba b w położenie b jest większa niż lub równa liczby A w położenie A) następnie algorytm określa b ← b - A (co oznacza, że numer b - zastąpienie starego b ). Podobnie, gdy A> B, następnie ← A - B, proces kończy się, gdy zawartość (B) 0, w wyniku czego otrzymano GCD w A. (algorytm pochodzący od Scott 2009: 13; symboli i styl rysunku z Tausworthe 1977) ,

W matematyce i informatyce , algorytm ( / ć l ɡ ə r ɪ ð əm /  ( słuchać )O tym dźwiękiem ) jest jednoznaczne określenie, jak rozwiązać klasę problemów. Algorytmy mogą wykonywać obliczenia , przetwarzanie danych oraz zautomatyzowane rozumowania zadań.

Jako skuteczny sposób , algorytm może być wyrażona w ograniczonej ilości miejsca i czasu w dobrze określonym języku formalne do obliczania funkcji . Począwszy od początkowego wkładu początkowego stanu i (być może pusty ), instrukcje opisują obliczenia , że kiedy wykonywane , przechodzi przez skończoną liczbę dobrze zdefiniowanych kolejnych państw, w końcu produkcji „wydajność” i kończące w końcowym stanie końcowym. Przejście z jednego stanu do drugiego, nie ma konieczności deterministyczny ; Niektóre algorytmy zwane randomizowanych algorytmów , wyposażonych w wejście losowego.

Pojęcie algorytmu istnieje od wieków. Greccy matematycy algorytmy wykorzystywane w, na przykład, Sito Eratostenesa do znajdowania liczb pierwszych i algorytm Euklidesa znajdowania największego wspólnego dzielnika dwóch liczb.

Słowo algorytm sam pochodzi z 9. wieku matematyk Muhammad ibn Musa al-Chuwarizmi , latinized Algoritmi . Częściowa formalizacja co stanie się nowoczesna koncepcja algorytmu zaczął z prób rozwiązania Entscheidungsproblem (problem decyzji) stwarzane przez Davida Hilberta w 1928 Późniejsze formalizacji zostały ukształtowane jako próbuje zdefiniować „ skuteczne wymierność ” lub „skuteczną metodę”. Formalizacji te obejmowały Gödel - Herbrand - KLEENE rekurencyjne funkcje z 1930, 1934 i 1935, Alonzo Church 's lambda rachunku 1936, Emil post ' s Preparat 1 z 1936 roku, a Alan Turing „s maszyny Turinga w latach 1936-37 i 1939.

Etymologia

Słowo „algorytm” ma swoje korzenie w latinizing nazwisko Muhammad ibn Musa al-Chuwarizmi w pierwszym etapie do algorismus . Al-Khwarizmi ( perski : خوارزمی ., C 780-850) był perski matematyk, astronom , geograf i uczony w Domu Mądrości w Bagdadzie , którego nazwa oznacza „rodem z Chorezm ”, region, który był częścią większa Iran i jest obecnie w Uzbekistanie .

O 825, al-Khwarizmi napisał Język arabski traktat o Hindu-arabskiej systemie liczbowym , który został przetłumaczony na łacinę w 12 wieku pod tytułem Algoritmi de numero Indorum . Ten tytuł oznacza „Algoritmi na liczebność Indian”, gdzie „Algoritmi” był tłumacza latynizacji o nazwie Al-Khwarizmi użytkownika. Al-Khwarizmi był najbardziej poczytnych matematyk w Europie w późnym średniowieczu, głównie dzięki kolejnym z jego książek, z algebry . Pod koniec średniowiecza Łacińskiej, algorismus , angielski „ algorytm ”, zepsucie jego imienia, po prostu oznaczało „dziesiętny system liczbowy”. W 15 wieku, pod wpływem greckiego słowa ἀριθμός „number” ( por „arytmetyka”), łacińskie słowo zostało zmienione na algorithmus , a odpowiadający angielski termin „algorytm” jest najpierw poświadczone w 17 wieku; współczesny sens został wprowadzony w 19. wieku.

W języku angielskim, został po raz pierwszy użyty w około 1230 roku, a następnie przez Chaucera w 1391 English przyjęty termin francuskiej, ale dopiero pod koniec 19 wieku, że „algorytm” odbyła się w ten sposób, że ma we współczesnym języku angielskim.

Inną wcześnie użycie tego słowa jest od 1240 roku, w podręczniku zatytułowanym Carmen de Algorismo skomponował Alexandre de Villedieu . Zaczyna się tak:

HAEC algorismus ARS Praesensie dicitur w qua / Talibus Indorum fruimur bis quinque figuris.

co tłumaczy się jako:

Algorytm jest sztuką, w którym obecnie używamy tych indyjskich dane, których liczba dwa razy pięć.

Wiersz jest długi kilkaset wierszy i podsumowuje sztukę obliczania z nowym stylu Indian kości lub Talibus Indorum lub cyfr hinduskich.

nieformalna definicja

Nieformalna definicja może być „zbiór zasad, które dokładnie określa kolejność operacji.” który obejmowałby wszystkie programy komputerowe, w tym programy, które nie wykonują obliczenia numeryczne. Generalnie program jest tylko algorytm, który przestaje w końcu.

Prototypowe przykładem algorytmu jest euklidesowa algorytm w celu określenia maksymalnej wspólny dzielnik dwóch liczb; przykład (są inne) opisany jest wykresem powyżej jako przykład w dalszej części.

Boolos Jeffrey & 1974, 1999 oferta nieformalna znaczenie słowa w poniższym cytacie:

Żadna istota ludzka nie może pisać na tyle szybko, lub na tyle długo, albo na tyle mała † († „mniejsze bez limitu ... byłbyś próbuje pisać na cząsteczkach, na atomach, na elektronów”) notować wszystkie członkami enumerably nieskończony ustawiony przez wypisując ich imiona, jeden po drugim, w pewnym zapisie. Ale ludzie mogą zrobić coś równie użyteczny w przypadku niektórych zestawów enumerably nieskończone: Mogą one dać wyraźne instrukcje dla ustalania n th członka zestawu , dla dowolnego skończonego n . Takie instrukcje powinny być podane całkiem wyraźnie, w postaci, w której mogą być następnie przez maszynę obliczeniową , albo przez człowieka, który jest zdolny do wykonywania operacji tylko bardzo elementarne na symbole.

Określenie „enumerably nieskończony zbiór” jest ten, którego elementy mogą być wprowadzane do korespondencji jeden do jednego z całkowitymi. Zatem Boolos i Jeffrey mówią, że algorytm zakłada instrukcje dla procesu, który „tworzy” całkowite wyjście z arbitralnej „Input” lub liczb całkowitych, które teoretycznie mogą być dowolnie duże. Zatem algorytm może być równanie algebraiczne, takie jak y = m + n - dwóch dowolnych zmiennych wejściowych „” m i n , które wytwarzają sygnał wyjściowy y . Ale próby różnych autorów zdefiniowanie pojęcia wskazują, że słowo oznacza znacznie więcej niż to, co na zlecenie (na przykład dodawanie):

Dokładne instrukcje (w języku zrozumiałym dla „komputer”) do szybkiego, skutecznego, „dobrego” proces, który określa się „ruchy” w „komputerze” (maszyna lub człowiek, wyposażony w niezbędne wewnętrznie zawierały informacje i możliwości), aby znaleźć , dekodowania, a następnie proces dowolna / symbole wejściowe liczby całkowite m i n , symboli + i = ... i tworzyć „skuteczne” w „rozsądnej” czas wyjściowy liczbą całkowitą Y w określonym miejscu i w określonym formacie.

Pojęcie algorytmu jest również stosowany w celu zdefiniowania pojęcia rozstrzygalności . Że pojęcie to centralny do wyjaśnienia w jaki sposób formalny systemy powstają zaczynając od małego zbioru aksjomatów i reguł. W logice , czas że algorytm wymaga, aby zakończyć nie można zmierzyć, ponieważ nie jest najwyraźniej związane z naszym zwyczajowym wymiarze fizycznym. Z takich niepewności, które charakteryzują trwające prace, łodygi niedostępność definicji algorytmu , który odpowiada zarówno konstrukcyjny (w pewnym sensie) i abstrakcyjne użycia tego terminu.

Formalizowanie

Algorytmy są niezbędne do danych, sposób komputery procesowego. Wiele programów komputerowych zawierają algorytmy, które szczegółowo konkretne instrukcje komputer powinien wykonać (w określonej kolejności) wykonywanie określonego zadania, takie jak obliczenia czeki lub studentów drukarskiego pracowników kart zgłoszeń. W ten sposób, algorytm może być uważany za dowolnym ciągiem operacji, które mogą być symulowane przez Turinga całkowitego systemu. Autorzy zapewni to tezę obejmują Minsky'ego (1967), 1987) (Savage i Gurevich (2000),

Minsky: „Ale będziemy też utrzymywać z Turinga, że ​​każda procedura, która mogłaby...«Naturalnie»nazwać skuteczne, mogą w rzeczywistości być realizowane przez (prosty) maszyny Chociaż może to wydawać skrajny, argumenty... . na jego rzecz są trudne do odparcia”.

Gurevich: „... nieformalny argumentem Turinga na rzecz swojej pracy uzasadnia silniejszą tezę: każdy algorytm może być symulowane przez maszynę Turinga ... według Savage [1987], algorytm jest procesem obliczeniowym zdefiniowane przez maszynę Turinga” ,

Zazwyczaj, gdy algorytm jest związana z przetwarzania informacji, dane mogą być odczytane ze źródła wejściowego, napisany do urządzenia wyjściowego i przechowywane do dalszego przetwarzania. Przechowywane dane są traktowane jako część stanu wewnętrznego podmiotu realizującego algorytm. W praktyce, państwo jest przechowywany w jednej lub kilku struktur danych .

Z jakiegoś takiego procesu obliczeniowego, algorytm musi być rygorystycznie zdefiniowane: określone w sposób ona zastosowanie we wszystkich możliwych okolicznościach, które mogłyby się pojawić. Oznacza to, że wszelkie kroki warunkowe musi być systematycznie rozpatrywane, indywidualnie dla każdego przypadku; kryteria każdym przypadku muszą być jasne (i obliczalne).

Ponieważ algorytm jest dokładna lista precyzyjnych kroków, kolejność obliczeń jest zawsze kluczowe znaczenie dla funkcjonowania algorytmu. Instrukcje są zwykle zakłada się, że wymienione wyraźnie i są opisane jako zaczynając „od góry” i będzie „do dołu”, pomysł, który jest opisany bardziej formalnie przez przepływ sterowania .

Do tej pory, ta dyskusja o sformalizowanie algorytmu przejęła lokal o programowaniu rozkazującym . Jest to najczęstsza koncepcja i próbuje opisać zadania w dyskretnych, „mechaniczne” oznacza. Unikalne dla tej koncepcji sformalizowanych algorytmów jest operacja przypisania ustawienie wartości zmiennej. Wywodzi się od intuicji „ pamięci ” jako scratchpad. Jest to przykład poniżej takiego zadania.

Dla niektórych alternatywnych koncepcji, co stanowi algorytm patrz programowanie funkcyjne i programowanie logiki .

wyrażając algorytmów

Algorytmy mogą być wyrażone w wielu rodzajach notacji, w tym języków naturalnych , Pseudokod , schematów blokowych , Drakon-charty , języków programowania lub tabel sterujących (przetworzone przez tłumaczy ). Naturalne wyrażenia językowe algorytmy wydają się być gadatliwym i niejednoznaczne i są rzadko stosowane w przypadku złożonych lub technicznych algorytmów. Pseudokod, diagramy, Drakon-wykresy i tabele sterujące są strukturyzowane sposoby wyrażania algorytmów, które unikają wielu niejasności wspólnych w naturalnych wypowiedzi językowych. Języki programowania są przeznaczone głównie do wyrażania algorytmów w postaci, która może być wykonana za pomocą komputera, ale często są wykorzystywane jako sposób definiowania algorytmów lub dokumentów.

Istnieje wiele różnych reprezentacji możliwe i można wyrazić daną maszynę Turinga programu w sekwencji tabelach urządzenia (patrz u automat skończony , tabela przejść stanów i tablicy kontrolnej ), a schematach i drakon-wykresów (patrz u diagram stanu ) lub w postaci elementarnego kodu maszynowego lub kodu maszynowego zwane „zestawy” czterokrotnie (więcej na maszynie Turingowi ).

Reprezentacje algorytmów mogą być klasyfikowane w trzech przyjętych poziomów Turinga Opis maszyny:

1 Opis wysokiego poziomu
„... proza ​​opisać algorytm, ignorując szczegóły wykonania. Na tym poziomie nie musimy wspomnieć, jak maszyna zarządza taśmy lub głowę.”
2 Opis Wprowadzenie
„... proza ​​używany do określenia sposobu maszyna Turinga wykorzystuje swoją głowę i sposób, że przechowuje dane na jej taśmie. Na tym poziomie nie dajemy szczegóły stanów lub funkcji przejścia.”
3 formalnego opisu
Najbardziej szczegółowy „najniższy poziom” daje „stół” stan urządzenia Turinga.

Na przykład prostego algorytmu „Dodaj m + n” opisany w trzech poziomach, patrz algorytm # przykłady .

Projekt

Algorytm wzór odnosi się do sposobu lub procesu matematycznych algorytmów i rozwiązywania problemów technicznych. Konstrukcja algorytmów jest częścią wielu teorii rozwiązania z badań operacyjnych , takich jak programowanie dynamiczne i dziel i zwyciężaj . Techniki projektowania i wdrażania projektów algorytmu nazywane są również wzorców projektowych algorytmów, takich jak wzór metoda szablon i dekorator deseń.

Jednym z najważniejszych aspektów projektowania algorytmu jest stworzenie algorytmu, który ma skutecznego run-time, znany również jako Big O .

Typowe kroki w rozwoju algorytmów:

  1. Definicja problemu
  2. Opracowanie modelu
  3. Specyfikacja algorytmu
  4. Projektowanie algorytmu
  5. Sprawdzanie poprawności algorytmu
  6. Analiza algorytmów
  7. Implementacja algorytmu
  8. testowanie programu
  9. przygotowanie dokumentacji

Realizacja

Logiczne NAND algorytm realizowany elektronicznie w 7400 chipie

Większość algorytmów mają być realizowane jako programy komputerowe . Jednakże, algorytm są realizowane przy użyciu innych środków, takich jak na sieć neuronowa (na przykład ludzki mózg realizacji arytmetyki lub owada poszukiwaniu pokarmu) w obwodzie elektrycznym , albo za pomocą urządzenia mechanicznego.

algorytmy komputerowe

Schematów blokowych przykłady kanonicznych struktur Böhm-Jacopini : sekwencja (prostokąty malejąca strony), czas-DO i IF-THEN-ELSE. Trzy konstrukcje wykonane z pierwotnego GOTO warunkowego ( IF Test = prawda to GOTO etap XXX ) (diament) bezwarunkowe GOTO (prostokąt), różne operatory przypisania (prostokąt) i HALT (prostokąt). Zagnieżdżenia tych struktur wewnątrz przydziału bloków spowodować złożonych schematów (CF Tausworthe 1977, 100,114).

W systemach komputerowych , algorytm jest w zasadzie instancją logiki pisemnej oprogramowania przez programistów, aby być skuteczne do zamierzonego „docelowej” komputera (-ów) w celu wytworzenia wyjścia z danej (chyba null) wejście . Optymalny algorytm, nawet uruchomiony w starym sprzęcie, będzie produkować szybsze rezultaty niż nieoptymalne (większa złożoność czas ) algorytmu dla tego samego celu, działa w bardziej wydajny sprzęt; dlatego algorytmów, takich jak sprzęt komputerowy, są uważane technologia.

„Elegant” (Compact) programów, „dobre” (fast) programów pojawia się pojęcie „prostoty i elegancji” nieformalnie w: Knuth i właśnie w Chaitina :

Knuth.”. .We chcesz dobre ...... Algorytmy w pewnym sensie estetycznym luźno zdefiniowane Jednym kryterium jest czas wzięty do wykonywania algorytmu .. Inne kryteria to zdolność adaptacji algorytmu do komputerów, jego prostoty i elegancji , etc”
Chaitin: „.. Program jest«elegancki», przez co rozumiem, że jest to najmniejsza program do wytwarzania wyjście, że robi”

Chaitin poprzedza jego definicję z: „Pokażę nie można udowodnić, że program jest«elegancki » ” -such dowodem rozwiąże problemu stopu (tamże).

Algorytm w porównaniu do funkcji obliczeniowego algorytmem : Dla danej funkcji może istnieć wiele algorytmów. To prawda, nawet bez zwiększania dostępnego zestawu instrukcji dostępnych dla programisty. Rogers stwierdza, że „to,., Ważne jest, aby odróżnić między pojęciem algorytmu , czyli procedury i pojęciem funkcji za pomocą algorytmu obliczeniowego , to znaczy odwzorowania uzyskanych przez procedury. Ta sama funkcja może mieć wiele różnych algorytmów.”

Niestety, nie może być kompromis pomiędzy dobroci (prędkości) i elegancji (zwartość) -an elegancki program może podjąć kolejne kroki, aby ukończyć obliczeń niż jeden mniej eleganckie. Przykładem, który wykorzystuje algorytm Euklidesa pojawia się poniżej.

Komputery (i computors), modele obliczeniowe : Komputer (lub ludzki „computor”) jest ograniczony typ maszyny, jest „dyskretna deterministyczny urządzenie mechaniczne”, który ślepo stosować się do jego wskazówek. Modele prymitywne Melzak i Lambek jest zredukowana to pojęcie do czterech elementów: (i) dyskretnych, rozróżnialne lokalizacje , (ii) dyskretnych, nie do odróżnienia liczniki (iii) środek, oraz (iv) wykaz instrukcji, które są skuteczne w stosunku do możliwości z agent.

Minsky opisuje bardziej sympatyczny odmianę modelu „liczydła” Lambek w jego „Bardzo proste zasady do obliczalności ”. Maszyna Minsky za przechodzi kolejno przez jego pięć (lub sześć, w zależności od tego, jak jeden impulsy) instrukcje, chyba że którakolwiek warunkowej IF-THEN GOTO lub bezwarunkowego GOTO zmienia przepływ programu poza kolejnością. Poza HALT urządzenie Minsky obejmuje trzy zadania (wymiana, podstawienie) operacje: zero (np zawartość położenia zastąpione 0: L ← 0), następca (np l ← L + 1), zmniejszania (np l ← L - 1 ). Rzadko musi programista pisać „kod” z takim ograniczonym zestawem instrukcji. Ale Minsky pokazuje (podobnie jak Melzak i Lambek), że jego maszyna jest Turinga kompletne z zaledwie czterech ogólnych typów wykładowy: warunkową Goto, bezwarunkowej Goto, przypisania / zamiennik / substytucji i zatrzymania.

Symulacja algorytmu: Komputer (computor) język : Knuth przypomina czytelnikowi, że „.. Najlepszym sposobem, aby dowiedzieć się algorytm jest spróbować natychmiast wziąć pióro i papier i pracy poprzez przykład”. Ale co z symulacji lub wykonania prawdziwe? Programista musi tłumaczyć algorytm w języku, który symulator / komputer / computor można skutecznie wykonać. Kamień daje tego przykład: przy obliczaniu korzenie kwadratowego równania computor musi umieć wziąć pierwiastek kwadratowy. Jeśli nie, to algorytm, aby była skuteczna, musi dostarczyć zestaw reguł dla wydobywania pierwiastek kwadratowy.

Oznacza to, że programista musi znać „język”, który jest skuteczny w stosunku do środka docelowego obliczeniowej (komputer / computor).

Ale jaki model powinien być używany do symulacji? Van Emde Boas zauważa „nawet jeśli opieramy teorii złożoności na abstrakcyjny zamiast konkretnych maszyn, arbitralność wyboru modelu pozostaje. Jest w tym momencie, że pojęcie symulacji wejścia”. Gdy prędkość jest mierzona, instrukcja ustawić sprawy. Na przykład, podprogram algorytm Euklidesa do obliczenia pozostałej byłoby wykonać znacznie szybciej, jeśli programista miał „ Moduł właściwy ” Instrukcja dostępne, a nie tylko odejmowanie (lub gorzej: tylko Minsky za „Decrement”).

Programowanie strukturalne, struktury kanoniczne : Per na Hipoteza Churcha-Turinga , każdy algorytm może być obliczona przez model znanej być Turinga kompletne , a za demonstracji Minsky, w Kompletność Turinga wymaga tylko czterech instrukcji typy-warunkową Goto, bezwarunkową Goto, zadania, zatrzymania. Kemeny i Kurtz zauważyć, że podczas gdy „niezdyscyplinowany” Zastosowanie bezwarunkowych GOTOS i warunkowa IF-THEN GOTOS może spowodować „ spaghetti code ”, programista może napisać ustrukturyzowanych programów przy użyciu tylko tych instrukcji; Z drugiej strony „to możliwe, a także nie jest zbyt trudne, aby pisać programy źle skonstruowany w oparciu o określony język”. Tausworthe zwiększa trzy Böhm-Jacopini struktur kanonicznych : sekwencja, IF-THEN-ELSE, a jednocześnie-DO, o dwa więcej: DO-WHILE i CASE. Dodatkową zaletą programu jest to, że uporządkowany nadaje się do dowodów poprawności wykorzystaniem indukcji matematycznej .

Kanoniczne symbole schematów blokowych : Adiutant graficzny zwany schemat , oferuje sposób opisać i udokumentować algorytmu (i programu komputerowego z jednego). Podobnie jak w przypadku przebiegu programu w maszynie Minsky, schemat blokowy zawsze zaczyna się na górze strony i przechodzi w dół. Jego głównymi symbole są tylko cztery: ukierunkowany strzałki pokazujące przebiegu programu prostokąt (sekwencja Goto) diamentu (IF-to-inaczej) i DOT (OR-tie). W Böhm-Jacopini struktury kanoniczne są wykonane z tych pierwotnych kształtów. Sub-struktury mogą „gniazdo” w prostokąty, ale tylko wtedy, gdy występuje jeden zjazd z nadbudową. Symbole i ich zastosowanie do budowy struktury kanoniczne są pokazane na rysunku.

Przykłady

przykładem algorytmu

Animację algorytmu Quicksort sortowania tablicy randomizowanych wartości. Czerwone paski zaznaczyć element obrotowy; Na początku tej animacji element najdalej z prawej strony został wybrany jako osi obrotu.

Jednym z najprostszych algorytmów jest znalezienie jak największej liczby na liście liczb kolejności losowej. Znalezienie rozwiązania wymaga patrząc na każdego numeru na liście. Z tego wynika prosty algorytm, który może być podany w opisie wysokiego szczebla w angielskiej prozy, jak:

Opis wysokiego poziomu:

  1. Jeśli nie ma żadnych numerów w zestawie to nie ma najwyższy numer.
  2. Załóżmy, że pierwszy numer w zestawie jest największą liczbę w zbiorze.
  3. Dla każdej pozostałej liczby w zestawie: jeśli liczba ta jest większa niż obecnie największa liczba, uważają, że liczba ta będzie największą liczbę w zbiorze.
  4. Kiedy nie ma już w zestawie iteracyjne nad numery, pod prąd największa liczba będzie największa liczba zestawie.

(Quasi-) formalny opis: Napisana w prozie, ale znacznie bliżej do języka wysokiego poziomu programu komputerowego, następujące jest bardziej formalna kodowanie algorytmem w Pseudokod lub kod pidgin :

Algorithm LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.
  if L.size = 0 return null
  largestL[0]
  for each item in L, do
    if item > largest, then
      largestitem
  return largest
  • „←” oznacza zadanie . Na przykład, „ największypozycja ” oznacza, że wartość największych zmian wartości pozycji .
  • Powrót ” kończy algorytmu i wyprowadza się następujące wartości.

Algorytm Euklidesa

Przykład-schemat algorytmu Euklidesa z TL Zdrowia (1908), bardziej szczegółowo dodany. Euklides nie wykracza poza trzeciego wymiaru i nie daje przykłady liczbowe. Nikomachus podaje przykład 49 i 21, „I odjąć od mniej więcej; 28 jest lewy, a następnie znowu odejmowanie to samo 21 (w tym celu jest to możliwe), 7 w lewo, że odjąć od 21 14 lewo, od którego znowu odjąć 7 (w tym jest to możliwe), 7 w lewo, a 7 nie może zostać odjęta od 7.” Heath komentuje, że „ostatnie zdanie jest ciekawy, ale znaczenie to jest oczywiste, wystarczy, jak również znaczenia określenia«około kończąc w jednym i tym samym numerem».” (Heath 1908: 300).

Euklides algorytm „s obliczyć największy wspólny dzielnik (GCD) do dwóch liczb pojawia się jako Proposition II w książce VII («Elementary Number Theory») z jego elementów . Euklides stwarza problem w ten sposób: „Biorąc pod uwagę dwa numery nie pierwsze dla siebie, aby znaleźć ich największy wspólny środek”. Definiuje „Numer [do] mnogość zbudowany z jednostek”: liczba zliczania dodatnią liczbę całkowitą nie w tym zero. Na „pomiar” jest umieszczenie krótszy odcinek pomiarowy s kolejno ( q razy) po dłuższych L , aż pozostała część R jest mniejsza niż długość krótszego s . W nowoczesnych słowy, reszta r = l - q x S , Q jest iloraz lub reszta R jest „moduł”, część całkowita ułamkową pozostały po podziale.

Dla metody Euklidesa, aby odnieść sukces, długości wyjścia musi spełniać dwa warunki: (i) długości nie musi wynosić zero, oraz (ii) odejmowanie musi być „właściwe”; czyli test musi gwarantować, że mniejszy z dwóch liczb jest odejmowana od większych (na przemian, dwa może być równa więc ich rentowności odejmowanie zero).

Oryginalny dowód Euklidesa dodaje trzeci warunek: dwa odcinki nie musi być pierwsze dla siebie. Euklides określone to, żeby mógł skonstruowania reductio ad absurdum dowód, że wspólne działanie dwóch liczb jest w rzeczywistości największe . Chociaż algorytm Nikomachus jest taka sama jak Euklidesa, gdy numery te pierwsze dla siebie, to daje liczbę «1» dla ich wspólnego środka. Tak więc, aby być precyzyjnym, to naprawdę dodaje algorytm Nikomachus.

Graficzna ekspresja algorytmu Euklidesa, aby znaleźć największy wspólny dzielnik dla 1599 i 650.
 1599 = 650×2 + 299
 650 = 299×2 + 52
 299 = 52×5 + 39
 52 = 39×1 + 13
 39 = 13×3 + 0

język komputerowy dla algorytmu Euklidesa

Tylko kilka instrukcji typy są wymagane do wykonania algorytmu-kilka testów Euklidesa logiczne (GOTO warunkowy), bezwarunkowe Goto, przypisanie (wymiana), i odejmowanie.

  • Położenie jest symbolizowane przez wielką literę (y), na przykład S, A, etc.
  • Zmieniająca się ilość (liczba) w takim miejscu jest napisane w dolnej litera (-y) sprawy oraz (zazwyczaj) wiąże się z nazwą lokalizacji użytkownika. Na przykład, położenie L na początku może zawierać numer L = 3009.

Nieeleganckie program dla algorytmu Euklidesa

„Nieeleganckie” jest tłumaczeniem wersji Knutha algorytmu z odejmowania oparte resztkowej pętli zastępująca jego wykorzystanie podziału (lub „moduł” instrukcją). Pochodzące z Knuth 1973: 2-4. W zależności od dwóch liczb „nieeleganckie” może obliczyć GCD w mniejszej liczbie etapów niż „Elegant”.

Następujący algorytm jest skonstruowane, czterostopniowym wersji Knutha z Euklidesa i Nikomachus, lecz, zamiast podział znaleźć pozostałej wykorzystuje kolejne odejmowanie od długości krótszych y niż długość pozostałych RR jest mniejszy niż s . Opis wysokiego poziomu, pogrubioną czcionką, przystosowany z Knuth 1973: 2-4:

WEJŚCIE :

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
  INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
  R ← L

E0 [Upewnić rs ].

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
  IF R > S THEN
    the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
    GOTO step 6
  ELSE
    swap the contents of R and S.
4   L ← R (this first step is redundant, but is useful for later discussion).
5   R ← S
6   S ← L

E1: [Find pozostałą] : Do długość pozostałego R w R jest mniejszy niż krótsza długość s w S wielokrotnie odejmować liczba pomiarowy s w S od długości pozostały R w R.

7 IF S > R THEN
    done measuring so
    GOTO 10
  ELSE
    measure again,
8   R ← R − S
9   [Remainder-loop]:
    GOTO 7.

E2: [Czy zerowe reszta?] : (I) ostatni środek był dokładny, pozostała w R wynosi zero, a program można zatrzymać, lub (ii) algorytm musi kontynuować: ostatnia miara pozostawił resztę w R mniej niż pomiar liczby w S.

10 IF R = 0 THEN
     done so
     GOTO step 15
   ELSE
     CONTINUE TO step 11,

E3: [Interchange s i R ] : Nakrętka algorytmu Euklidesa. Używać pozostałą R pomiaru, co było wcześniej mniejsza liczba s ; L służy jako tymczasowej lokalizacji.

11  L ← R
12  R ← S
13  S ← L
14  [Repeat the measuring process]:
    GOTO 7

WYJŚCIE :

15 [Done. S contains the greatest common divisor]:
   PRINT S

Sporządzono :

16 HALT, END, STOP.

Elegancki program dla algorytmu Euklidesa

Kolejna wersja algorytmu Euklidesa wymaga tylko sześć podstawowych wskazówek, aby robić to, co trzynaście muszą zrobić „nieeleganckie”; gorzej „nieeleganckie” wymaga więcej rodzajów instrukcji. Schemat blokowy z „Elegant” można znaleźć w górnej części tego artykułu. W niestrukturalnych () języka podstawowego, kroki są ponumerowane, a instrukcja jest instrukcja przypisania symbolizowane przez ←. LET [] = []

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 0"
  10 INPUT A,B
  20 IF B=0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B=B-A
  50 GOTO 20
  60 LET A=A-B
  70 GOTO 20
  80 PRINT A
  90 END

Poniższa wersja może być używany z Object Oriented języków:

// Euclid's algorithm for greatest common divisor
integer euclidAlgorithm (int A, int B){
     A=Math.abs(A);
     B=Math.abs(B);
     while (B!=0){
          if (A>B) A=A-B;
          else B=B-A;
     }
     return A;
}

Jak "Elegant" działa : W miejscu zewnętrznej "Euclid pętli", "elegancki" przesuwa się tam iz powrotem pomiędzy dwoma "co-pętli" An A> Pętla B, który oblicza ← A - B, a B ≤ A pętli który oblicza B ← B - A. Ten działa, ponieważ kiedy w końcu odjemna M jest mniejsze niż lub równe odjemnika s (= odjemnej Difference - odjemnik) odjemna może stać s (nowa długość pomiarowa) i może odjemnik się nową R (długość do zmierzenia); Innymi słowy „zmysł” odejmowania odwraca.

Testowanie algorytmów Euclid

Czy algorytm robić to, co autor chce to zrobić? Kilka przypadków testowych zwykle wystarczają, aby potwierdzić podstawowe funkcje. Jednym ze źródeł używa 3009 i 884. Knuth zasugerował 40902, 24140. Innym ciekawym przypadkiem jest dwa względnie pierwszymi 14157 numery i 5950.

Ale wyjątkowe przypadki muszą być zidentyfikowane i przetestowane. Będzie "nieeleganckie" wykonać poprawnie, gdy R> S, S> R, R = S? Ditto dla "Elegant": B> A, A> B, A = B? (Tak dla wszystkich). Co się dzieje, gdy jedna liczba jest równa zero, obie liczby są równe zeru? ( „Nieeleganckie” oblicza zawsze we wszystkich przypadkach; „Elegant” oblicza zawsze gdy A = 0.) Co się stanie, jeśli ujemne numery są wprowadzane? Liczby ułamkowe? Jeśli numery wejściowe, czyli domenę funkcji obliczonego przez algorytm / programu, ma zawierać tylko liczby całkowite dodatnie włącznie zera, to awarie na zero wskazują, że algorytm (i program, który tworzy wystąpienie go) jest częściowy funkcja zamiast całkowita funkcja . Godnym uwagi na brak wyjątków jest Ariane 5 Flight 501 Awaria rakiety (04 czerwca 1996).

Dowód poprawności programu za pomocą indukcji matematycznej : Knuth demonstruje zastosowanie indukcji matematycznej do „rozszerzonego” wersję algorytmu Euklidesa, a on proponuje „ogólną metodę stosowaną do udowodnienia zasadności jakiegokolwiek algorytmu”. Tausworthe proponuje miarą złożoności programu mieć długość jego poprawności dowodu.

Pomiar i poprawa algorytmów Euclid

Elegance (zwartość) versus dobroci (prędkość) : W ciągu zaledwie sześciu podstawowych instrukcji „Elegant” jest zdecydowanym zwycięzcą w porównaniu do „nieeleganckie” w trzynastu instrukcji. Jednak „nieeleganckie” jest szybciej (to przybywa HALT w mniejszej liczbie etapów). Algorytm analizy wskazują, dlaczego tak jest: „Elegant” ma dwa testy warunkowe w każdej pętli odejmowania, a jedynie „nieeleganckie” robi jeden. Ponieważ algorytm (zazwyczaj) wymaga wielu loop-through, na średniej dużo czasu marnuje się robi „B = 0?” Test, który jest potrzebny tylko po reszta jest obliczana.

Mogą zostać ulepszone algorytmy? : Po sędziów programista program „fit” i „skuteczne” -to znaczy, że oblicza funkcja przeznaczona przez jego autora, a następnie staje się pytanie, można go poprawić?

Zwartość „nieeleganckie” można poprawić poprzez wyeliminowanie z pięciu etapów. Ale okazało się, że zagęszczanie Chaitin algorytm nie można zautomatyzować za pomocą uogólnionego algorytmu; raczej, to można zrobić tylko heurystycznie ; Czyli, wyczerpującego poszukiwania (przykłady można znaleźć w zajęty Beaver ) metodą prób i błędów, cleverness, wgląd stosowanie rozumowania indukcyjne itp Zauważmy, że etapy 4, 5 i 6 są powtarzane, w krokach 11, 12 i 13. Porównanie z „Elegant” stanowi wskazówkę, że te kroki, łącznie z etapów 2 i 3, mogą być wyeliminowane. Zmniejsza to liczbę instrukcji rdzeniowych od trzynastu do ośmiu, co sprawia, że „bardziej elegancka” niż „Elegant”, w dziewięciu krokach.

Prędkość „Elegant” można poprawić poprzez przesuwanie „B = 0?” Test poza dwoma pętlami odejmowanie. Zmiana ta wymaga dodawania trzech instrukcji (B = 0 ?, a = 0 ?, GOTO). Teraz „Elegant” oblicza PRZYKŁAD numery szybciej; czy jest to zawsze ma miejsce w danym A, B, R, S wymaga szczegółowej analizy.

analiza algorytmiczne

Jest często ważne, aby wiedzieć, ile z danego zasobu (takie jak czas lub magazynowania) jest teoretycznie wymagana dla danego algorytmu. Formy zostały opracowane dla analizy algorytmy w celu uzyskania takich odpowiedzi ilościowe (szacunki); Na przykład, algorytm sortowania powyżej ma wymogu czasie O ( n ), stosując duży notacji O o n co długość listy. Przez cały czas algorytm musi tylko pamiętać o dwóch wartości: największa liczba znalezionych do tej pory, a jego pozycja na liście wejściowej. W związku z tym mówi się, że zapotrzebowanie miejsca w O (1) , gdy wymagana przestrzeń do przechowywania numerów wejściowe nie jest liczona, albo O ( n ), jeśli jest liczona.

Różne algorytmy mogą zakończyć to samo zadanie z innym zestawem instrukcji w mniej lub więcej czasu, przestrzeni, lub „ wysiłku ” niż inni. Na przykład binarny wyszukiwania algorytm (z kosztów O (log n)) przewyższa sekwencyjne przeszukiwanie (koszt O (n)), gdy używany wyszukiwań stołowych na posortowanych list lub tablic.

Formalne kontra empiryczny

Analiza i badanie algorytmów jest dyscypliną informatyki i jest często praktykowane abstrakcyjnie, bez stosowania określonego języka programowania lub realizacji. W tym sensie analiza algorytm przypomina innych dyscyplin matematycznych w to, że koncentruje się na właściwościach bazowych algorytm, a nie od specyfiki konkretnej implementacji. Zazwyczaj pseudokod jest wykorzystywany do analizy, ponieważ jest to najprostszy i najbardziej ogólnym przedstawieniem. Jednak ostatecznie, większość algorytmy są zazwyczaj realizowane na poszczególnych platformach sprzętowych / programowych i ich wydajność oprogramowania ostatecznie poddana próbie przy użyciu prawdziwego kodu. Do roztworu „jednorazową” problem, wydajność konkretnego algorytmu nie może mieć znaczące konsekwencje (chyba, że n jest bardzo duża), ale dla algorytmów przeznaczonych do szybkiego interaktywny, handlowego lub naukowego długi czas użytkowania może być krytyczny. Skalowania od małych do dużych n n często nieefektywne ujawnia algorytmów, które są w inny sposób łagodny.

Badania empiryczne jest przydatna, ponieważ może odkryć nieoczekiwane oddziaływania, które wpływają na wydajność. Benchmarki mogą być wykorzystane do porównania przed / po potencjalnych ulepszeń do algorytmu po optymalizacji programu. Badania empiryczne nie może zastąpić analizy formalnej, choć i nie są trywialne, aby wykonać w sposób uczciwy.

efektywność wykonanie

Aby zilustrować możliwe ulepszenia możliwe nawet w ściśle ustalonych algorytmów ostatnie znaczące innowacji, odnośnie FFT algorytmów (bardzo obciążony w dziedzinie przetwarzania obrazu), może zmniejszyć czas obróbki do 1000 razy w zastosowaniach medycznych, takich jak obrazowanie. Ogólnie rzecz biorąc, poprawa prędkości zależy od szczególnych właściwości tego problemu, które są bardzo popularne w zastosowaniach praktycznych. Speedups tej wielkości umożliwić urządzeń komputerowych, które sprawiają, że szerokie wykorzystanie przetwarzania obrazu (takich jak aparaty cyfrowe i sprzęt medyczny) zużywają mniej energii.

Klasyfikacja

Istnieją różne sposoby, aby klasyfikować algorytmów, każdy z jego własnych zasług.

poprzez realizację

Jednym ze sposobów klasyfikowania algorytmów jest drogą realizacji.

rekurencja
Rekurencyjny algorytm jest taka, która wywołuje (odnosi się do) się kilkakrotnie aż do uzyskania pewnego stanu (znany również jako warunek zakończenia) odpowiada, co jest sposobem wspólne programowania funkcjonalnego . Iteracyjne algorytmy użyciu powtarzalnych konstrukcji jak pętle , a czasami dodatkowych struktur danych, takie jak stosy rozwiązać podane problemy. Niektóre problemy są naturalnie przystosowane do realizacji jednego lub drugiego. Na przykład, Wieże Hanoi jest dobrze zrozumiany za pomocą rekurencyjnego realizację. Każdy rekurencyjne wersja ma odpowiednika (ale może bardziej lub mniej złożone) wersja iteracyjny, i vice versa.
Logiczny
Algorytm może być postrzegane jako kontrolowany logicznej dedukcji . Koncepcja ta może być wyrażona jako: Algorithm = + logiki sterowania . Komponent logika wyraża aksjomaty, które mogą być wykorzystane do obliczenia i komponent sterujący określa, w jaki sposób odliczenie jest stosowana do aksjomatów. Stanowi to podstawę dla programowania logicznego paradygmatu. W czystych języków programowania logicznego, komponent kontrola jest stała i algorytmy są określone poprzez dostarczanie tylko element logiczny. Atrakcyjność tego podejścia jest eleganckie semantyka : zmiana aksjomatów produkuje dobrze określoną zmianę w algorytmie.
Szeregowe, równoległe lub rozprowadzane
Algorytmy są zwykle omawiane przy założeniu, że komputery wykonanie jednej instrukcji algorytmu naraz. Komputery te są czasami nazywane komputer szeregowy. Algorytm przeznaczony dla takiego środowiska nazywa się algorytmem seryjnego, a nie równolegle algorytmów lub rozproszone algorytmy . Algorytmy równoległe wykorzystać architektur komputerowych, gdzie kilka procesory mogą działać na problem w tym samym czasie, podczas gdy rozproszone algorytmy wykorzystują wielu komputerów połączonych z siecią komputerową . Algorytmy równoległe albo rozmieszczone podzielić problem na bardziej symetryczne lub asymetryczne podproblemów i zbierania wyników z powrotem. Zużycie zasobów w takich algorytmów to nie tylko na poszczególnych cykli procesora procesor ale również górny komunikacja pomiędzy procesorami. Niektóre algorytmy sortowania można parallelized sprawnie, ale ich głowami komunikacja jest drogie. Algorytmy iteracyjnych są na ogół parallelizable. Niektóre problemy nie mają równoległe algorytmy i nazywane są problemy natury seryjne.
Deterministyczny lub niedeterministyczne
Algorytm deterministyczny rozwiązać problem z dokładnym decyzji na każdym etapie algorytmu natomiast algorytmy deterministyczne nie rozwiązywać problemy poprzez zgadywanie chociaż typowe domysły są bardziej dokładne dzięki zastosowaniu heurystyki .
Dokładna lub przybliżone
Choć wiele algorytmów osiągnięcia dokładnego rozwiązania, algorytmy aproksymacji szukać zbliżenia, które jest bliżej do prawdziwego rozwiązania. Przybliżenie można dotrzeć zarówno za pomocą deterministyczny lub losowy strategii. Takie algorytmy mają praktyczną wartość dla wielu trudnych problemów. Jednym z przykładów algorytmu, w przybliżeniu jest problemem plecaka . Problem plecakowy jest problem, gdzie znajduje się zestaw danych przedmiotów. Celem tego problemu jest spakować plecak, aby uzyskać maksymalną łączną wartość. Każdy element ma pewną masę i pewną wartość. Całkowita waga, że możemy nosić ma więcej niż pewnym ustalonym numerem X. Tak więc, musimy wziąć pod uwagę masę przedmiotów, jak również ich wartość.
algorytm kwantowy
Rzucają się na realistycznym modelu obliczeń kwantowych . Określenie to jest zwykle stosowane dla tych algorytmów, które wydają się nieodłącznie kwantowej lub stosować pewną istotną cechę Quantum komputerowych , takich jak superpozycji kwantowej lub zaplątania kwantowej .

Przez paradygmat projektowania

Innym sposobem jest algorytmy klasyfikacji metodologii projektowania lub paradygmatu. Istnieje pewna liczba modeli, z których każdy różni się od innych. Ponadto, każda z tych kategorii zawiera wiele różnych rodzajów algorytmów. Niektóre wspólne paradygmaty są:

Brute-force lub wyczerpującej wyszukiwania
Jest to naiwny sposób próbuje wszelkich możliwych rozwiązań, aby zobaczyć co jest najlepsze.
Dziel i rządź
Algorytm dziel i przejęcie wielokrotnie zmniejsza wystąpienie problemów z jednym lub więcej mniejszych wystąpień tego samego problemu (zwykle rekurencyjnie ), aż do wystąpienia są wystarczająco małe, aby rozwiązać łatwo. Jednym z takich przykładów jest dziel i przejęcie połączyć sortowania . Sortowanie może być przeprowadzone dla każdego segmentu danych przez podział danych na segmenty i sortowania wszystkich danych można uzyskać w fazie przejęcie przez połączenie segmentów. Prostszy wariant dziel i przejęcie nazywa się spadek i podbijać algorytm , który rozwiązuje identyczną subproblem i wykorzystuje rozwiązanie tego subproblem rozwiązać większy problem. Podzielić przejęcie dzieli się na wiele problemów podproblemów a więc przejęcie etapu jest bardziej skomplikowane niż maleją podbić algorytmów. Przykładem algorytmu zmniejsz i przejęcie jest wyszukiwanie binarne .
Wyszukiwanie i wyliczenie
Wiele problemów (takich jak gra w szachy ) można modelować jako problemów na wykresach . Algorytm wykres badanie określa zasady poruszania się na wykresie i jest przydatna do takich problemów. Kategoria ta obejmuje również algorytmy wyszukiwania , metoda podziału i ograniczeń wyliczanie i wycofywania .
algorytm probabilistyczny
Takie algorytmy, że pewne wybrane losowo (lub pseudo-losowe). Mogą to być bardzo użyteczne w przybliżeniu znalezienia rozwiązania dla problemów, jeżeli stwierdzenie dokładnego rozwiązania może być niepraktyczne (patrz metoda heurystycznego poniżej). Dla niektórych z tych problemów, to wiadomo, że najszybciej przybliżenia musi obejmować pewną przypadkowość . Czy algorytmy randomizowane z wielomianu czasu złożoności może być najszybsze algorytmy dla niektórych problemów jest kwestią otwartą, znany jako P kontra NP problemu . Istnieją dwie duże klasy takich algorytmów:
  1. Algorytmy Monte Carlo zwróci poprawną odpowiedź z wysokim prawdopodobieństwem. Np RP jest podklasą te, które działają w czasie wielomianowym .
  2. Las Vegas algorytmy zawsze zwraca poprawną odpowiedź, ale ich czas pracy jest tylko probabilistycznie związana, np ZPP .
Redukcja złożoności
Technika ta polega na rozwiązaniu trudnego problemu poprzez przekształcenie go w bardziej znanego problemu, dla którego mamy (mam nadzieję) asymptotycznie optymalnych algorytmów. Celem jest znalezienie redukujący algorytm, którego złożoność nie jest zdominowany przez wynikających obniżonych algorytmu. Na przykład jeden algorytm wyboru za znalezienie medianę w liście niesegregowanych obejmuje najpierw sortowanie listy (kosztowna część), a następnie wyciągając element środkowy w uporządkowanym wykazie (tanie części). Technika ta znana jest również jako transformacji i podbić .
Powrót śledzenia
W tym podejściu, wiele rozwiązań są budowane stopniowo i opuszczony, gdy okaże się, że nie mogą one prowadzić do prawidłowego pełnego rozwiązania.

problemy optymalizacyjne

Do problemów optymalizacyjnych jest bardziej specyficzne algorytmy klasyfikacji; Algorytm takich problemów, które mogą należeć do jednej lub więcej z ogólnych grup opisanych powyżej, jak również w jednym z następujących:

Programowanie liniowe
Podczas poszukiwania optymalnych rozwiązań dla funkcji liniowej związany liniowych ograniczeń równości i nierówności, ograniczenia tego problemu może być stosowany bezpośrednio w tworzeniu optymalnych rozwiązań. Istnieją algorytmy, które można rozwiązać każdy problem w tej kategorii, takich jak popularny algorytm simplex . Problemy, które mogą zostać rozwiązane z programowania liniowego obejmują problem maksymalnego przepływu dla wykorzystania wykresów. Jeśli problem wymaga dodatkowo, że jeden lub więcej niewiadomych musi być liczbą całkowitą to jest klasyfikowany w programowaniu całkowitej . Liniowy algorytm programowania może rozwiązać taki problem, jeśli można udowodnić, że wszystkie ograniczenia dla wartości całkowitych są powierzchowne, czyli rozwiązania spełniają te ograniczenia i tak. W ogólnym przypadku, wyspecjalizowane algorytmy lub algorytm, który znajduje przybliżone rozwiązania jest używany, w zależności od stopnia trudności problemu.
Programowanie dynamiczne
Kiedy problem pokazuje optymalne podbudów - oznacza to optymalne rozwiązanie problemu może być wykonana z optymalnych rozwiązań podproblemów - i nakładających podproblemów , czyli same podproblemów są wykorzystywane do rozwiązywania wielu różnych wystąpień problemowych, szybsze podejście nazywa programowanie dynamiczne unika rozwiązania ponowne obliczanie że zostały już obliczone. Na przykład, Floyd- Warshall algorytm najkrótsza ścieżka bramką z wierzchołkiem w ważonej wykresu można znaleźć przez najkrótszą ścieżkę bramki ze wszystkich sąsiednich wierzchołków. Programowanie dynamiczne i memoization idą w parze. Główną różnicą między programowania dynamicznego i dziel i rządź jest podproblemów są mniej lub bardziej niezależne w dziel i rządź, natomiast podproblemów pokrywają się programowania dynamicznego. Różnica między programowania dynamicznego i proste rekursji jest buforowanie lub memoization wywołań rekurencyjnych. Kiedy podproblemów są niezależne i nie ma powtarzania, memoization nie pomoże; stąd dynamiczne programowanie nie jest rozwiązaniem dla wszystkich złożonych problemów. Dzięki zastosowaniu memoization lub utrzymania stół z podproblemów już rozwiązany, programowanie dynamiczne zmniejsza wykładniczy charakter wielu problemów do wielomianu stopnia złożoności.
Sposób chciwy
Zachłanny algorytm jest podobny do algorytmu programowania dynamicznego w to, że działa poprzez analizę podbudowy, w tym przypadku nie stanowi problemu, ale danego rozwiązania. Takie algorytmy początek pewnego rozwiązania, które może być podana lub zostały wykonane w inny sposób, i poprawić je za pomocą niewielkich zmian. Dla niektórych problemów mogą znaleźć optymalne rozwiązanie dla innych zatrzymują się w lokalnym optimum , czyli w rozwiązaniach, które nie mogą zostać ulepszone przez algorytm, ale nie są optymalne. Najbardziej popularnym zastosowaniem algorytmów zachłannych jest do znalezienia minimalnego drzewa rozpinającego gdzie znalezienie optymalnego rozwiązania jest to możliwe przy użyciu tej metody. Huffman Drzewo , Kruskala- , Prim , Sollin są zachłanne algorytmy, które mogą rozwiązać ten problem optymalizacji.
Sposób heurystyczny
W problemów optymalizacyjnych , algorytmy heurystyczne mogą być wykorzystane w celu znalezienia rozwiązania blisko optymalnego rozwiązania w przypadkach, gdy znalezienie optymalnego rozwiązania jest niepraktyczne. Algorytmy te działają poprzez coraz bliżej do optymalnego rozwiązania, ponieważ postęp. W zasadzie, jeśli prowadzony przez nieskończoną ilość czasu, będą one znaleźć optymalne rozwiązanie. Ich zasługą jest to, że mogą one znaleźć rozwiązanie bardzo blisko do optymalnego rozwiązania w stosunkowo krótkim czasie. Takie algorytmy obejmują lokalne wyszukiwanie , przeszukiwanie tabu , symulowanego wyżarzania i algorytmów genetycznych . Niektóre z nich, jak symulowanego wyżarzania są algorytmy nie deterministyczne, podczas gdy inni, jak przeszukiwanie tabu, są deterministyczne. Gdy granice błędu z non-optymalnego rozwiązania jest znany algorytm jest dalej klasyfikowane jako algorytm aproksymacji .

Przez kierunek studiów

Każda dziedzina nauki ma swoje własne problemy i wymaga wydajnych algorytmów. Powiązane problemy w jednej dziedzinie są często badane razem. Niektóre zajęcia są przykładowe algorytmy wyszukiwania , algorytmy sortowania , scalania algorytmów , algorytmy numeryczne , algorytmy wykres , algorytmy strunowe , algorytmów obliczeniowych geometryczne , algorytmy kombinatoryczne , algorytmy medyczne , uczenie maszynowe , kryptografia , kompresji danych Algorytmy i techniki analizowania .

Pola często pokrywają się ze sobą, a postęp w jednej dziedzinie algorytm może poprawić te z drugiej strony, czasami zupełnie niezwiązane, pola. Na przykład, programowanie dynamiczne został wymyślony dla optymalizacji zużycia zasobów w przemyśle, ale jest obecnie wykorzystywana w rozwiązywaniu szeroki zakres problemów w wielu dziedzinach.

przez złożoności

Algorytmy mogą być klasyfikowane według ilości czasu potrzebnych do zakończenia stosunku do ich wielkości wejściowych:

  • Stała czasowa: jeśli czas potrzebny algorytmu jest taka sama, niezależnie od wielkości wejściowej. Np dostęp do tablicy elementu.
  • czas liniowy: jeśli czas jest proporcjonalna do wielkości wejściowej. Np trawers listy.
  • Logarytmiczna czas: jeśli czas jest logarytmiczną funkcją wielkości wejściowej. Np algorytm wyszukiwania binarnego .
  • Wielomian czas: jeśli czas jest potęgą wielkości wejściowej. Np bubble sort algorytm ma złożoność kwadratową czasu.
  • Wykładniczy czas: jeśli czas jest wykładniczą funkcją wielkości wejściowej. Np wyszukiwania brute-force .

Pewne problemy mogą mieć wiele algorytmów o różnej złożoności, podczas gdy inne mogą mieć żadnych problemów ani żadnych znanych algorytmów efektywnych algorytmów. Istnieją również pewne problemy z mapowania do innych problemów. Dzięki temu, okazało się być bardziej odpowiedni do sklasyfikowania same problemy zamiast algorytmów język klas równoważności w oparciu o złożoności najlepszych możliwych algorytmów dla nich.

algorytmy ciągłe

Przymiotnik „ciągły”, gdy stosuje się słowo „algorytm” może oznaczać:

  • Algorytm działa na danych, które stanowią ciągłe ilości, nawet jeśli dane są reprezentowane w pojedynczych przybliżeń, takie algorytmy są badane w analizie numerycznej ; lub
  • Algorytm w postaci równań różniczkowych , które działa w sposób ciągły na podstawie danych, uruchomiony w komputerze analogowym .

Zagadnienia prawne

Algorytmy same w sobie nie są zazwyczaj opatentowaniu. W Stanach Zjednoczonych, roszczenie składająca się wyłącznie z prostych manipulacji pojęciami abstrakcyjnymi, cyfr lub sygnałów nie stanowią „procesy” (USPTO 2006), a więc nie mogą zostać opatentowane algorytmy (jak w Gottschalk v. Benson ). Jednak praktyczne zastosowania algorytmów są czasami patentową. Na przykład, w Diamentowej v. Diehr , stosowanie prostego zwrotnego algorytmu w celu ułatwienia utwardzania kauczuku syntetycznego uznano zdolność patentową. Patentowanie oprogramowania jest wysoce kontrowersyjne, a są bardzo krytykowane patenty obejmujące algorytmy, zwłaszcza kompresji danych algorytmów, takich jak Unisys ' LZW patentu .

Dodatkowo, niektóre algorytmy kryptograficzne mają ograniczeń eksportowych (patrz eksport kryptografii ).

Historia: Rozwój pojęcia „algorytmu”

Starożytnego Bliskiego Wschodu

Algorytmy zostały wykorzystane w starożytnej Grecji. Dwa przykłady to sito Eratostenesa , który został opisany w Wprowadzenie arytmetyczną przez Nikomachus , a algorytm euklidesowej , który został po raz pierwszy opisany w elementy euklidesowej (ok. 300 BC). Babilońskie gliniane tabliczki opisać i zatrudniają algorytmicznych procedur, aby obliczyć czas i miejsce ważnych wydarzeń astronomicznych.

Rozróżnialne dyskretne i symbole

Tally-znaki : Aby śledzić ich stada, ich worków zboża i ich pieniędzy starożytni używane liczenie: gromadzenie kamieni lub ślady zadrapań na kije lub podejmowania dyskretnych symboli w glinie. Przez babilońskiej i egipskiej stosowania znaków i symboli, w końcu cyframi rzymskimi i liczydła ewoluowała (Dilson, str. 16-41). Tally znaki pojawiają się w widocznym miejscu w jedynkowy system liczbowy arytmetyki stosowanych w maszynie Turinga i Post-maszyny Turinga obliczeń.

Manipulacja symbolami jak „miejsce” dla posiadaczy numerów: algebra

Praca z dawnych geometrów greckich ( Algorytm Euklidesa ), The Indian matematyk Brahmagupta i perski matematyk Al-Khwarizmi (od którego imię zasady „ algorytm ” i „algorytm” pochodzą), a zachodnie matematyków europejskich zwieńczeniem Leibniz „s pojęcie ratiocinator nazębnego (ca 1680)

Dobrym i pół wieku przed swoim czasie, Leibniz zaproponował algebry logiki, algebrę, która określa zasady do manipulowania pojęć logicznych w sposób zwyczajny algebra określa zasady manipulacji liczb.

contrivances mechaniczne o stanach dyskretnych

Zegar : Bolter kredytów wynalezieniem wagi napędzany zegarem jako „Kluczem wynalazku [Europy w średniowieczu]”, w szczególności, spływających do poboczy , które dostarcza nam kleszcza i Tock zegara mechanicznego. „Dokładne automat” doprowadziły bezpośrednio do mechanicznego „ automatów ” rozpoczynający się w 13 wieku i wreszcie do „maszyny obliczeniowe” -the silnik różnica i maszyna analityczna z Charles Babbage i hrabiny Ada Lovelace , w połowie 19 wieku. Lovelace jest uznawany za pierwszego stworzenia algorytmu przeznaczonego do obróbki na komputerze - maszyny analitycznej Babbage'a pierwsze urządzenie uważane za prawdziwe Turing-complete komputer zamiast tylko kalkulatora - a nazywa się czasem „Historia Pierwszy programista” w wyniku, choć pełne wdrożenie drugiego urządzenia Babbage'a nie będą realizowane aż dziesięciolecia po jej życia.

Maszyny logiczne 1870- Stanley Jevons ' «logiczne liczydło» i «logiczne maszyna» : Problem techniczny było zmniejszenie równań logicznych gdy przedstawiane w formie podobnej do tego, co jest obecnie znany jako metoda karnaugh . Jevons (1880) opisuje pierwszy prosty „liczydła” w „pasków drewna wyposażone w kołki, wymyślony, aby każda część czy klasy [logicznych] kombinacje mogą być zbierane w sposób mechaniczny... Ostatnio jednak, że zmniejszyły System do postaci całkowicie mechaniczny, iw ten sposób urzeczywistnił całość procesu pośredniego wnioskowania w tym, co można nazwać Logical maszyna „Jego maszyna przyszedł wyposażony w«niektórych ruchomych drewnianych prętów»i” u stóp są 21 klawisze, takie jak te z fortepian [etc]... ". Dzięki tej maszynie mógł analizować „ sylogizm lub inny prosty logiczny argument”.

Ta maszyna on wyświetlany w 1870 roku, zanim naukowcy z Royal Society. Innym logik John Venn , jednak w jego 1881 Symbolic Logic , odwrócił się żółtaczką oko do tego wysiłku: „Nie mam wysokiego oszacowania sobie z odsetek lub znaczenia jakie są czasami nazywane maszyn logicznych ... nie wydaje mi się, że wszelkie contrivances chwili obecnej znane lub które mogą być odkryta rzeczywiście zasługują na miano maszyn logicznych "; zobacz więcej na charakterystykach algorytmu . Ale nie być gorszym on zbyt przedstawiony „plan nieco analogiczne, uznaję, prof Jevon za liczydła ... [I] [a] zysk, co odpowiada logicznej maszyny prof Jevonsa w następujący pomysłowość może być opisany. Wolę nazwać jedynie maszynę logicznym schematem ... ale przypuszczam, że może to zrobić bardzo całkowicie wszystko, co można racjonalnie oczekiwać jakiegokolwiek logicznego maszyny”.

Maszyna żakardowa, Hollerith kart dziurkowanych, telegrafii i telefonii-przekaźnik elektromechaniczny : Bell i Newell (1971) wskazują, że krosno żakardowe (1801), prekursora kart Hollerith (kart perforowanych, 1887) i „telefonicznych przełączania technologii” były korzenie drzewa prowadzące do rozwoju pierwszych komputerów. W połowie 19 wieku telegrafu , prekursor telefon był w użyciu na całym świecie, jego dyskretny i odróżniające kodowania liter jak „kropek i kresek” wspólnego brzmienia. Pod koniec 19 wieku taśmy giełdowy (1870 CA) był w użyciu, podobnie jak korzystanie z kart Hollerith w 1890 roku US Census. Potem ten Teleprinter (ca. 1910) z jego stosowania wycięcie papieru kodu Baudota na taśmie.

Sieci telefoniczne przełączania elektromechanicznych przekaźników (wymyślone 1835) był za dzieło George Stibitz (1937), wynalazca urządzenia cyfrowego dodawania. Ponieważ pracował w Bell Laboratories, zauważył na „uciążliwe” używania kalkulatorów mechanicznych z biegami. «On poszedł do domu pewnego wieczoru w 1937 roku zamierza przetestować swój pomysł ... Gdy majstrowanie nad, Stibitz skonstruował binarny urządzenie dodając» ,

Davis (2000) zwraca uwagę na szczególne znaczenie przekaźnika elektromechanicznego (z jego dwóch „stanów binarnych” otwartych i zamkniętych ):

Dopiero wraz z rozwojem, począwszy od 1930 roku, z użyciem przekaźników elektromechanicznych kalkulatorów elektrycznych, że maszyny zostały zbudowane posiadające zakres Babbage nie przewidywał „.

Matematyka w 19 wieku do połowy 20 wieku

Symbole i zasady : w krótkim odstępie czasu, matematyka George Boole'a (1847, 1854), Gottlob Frege (1879) i Giuseppe Peano (1888/89) zmniejszyło arytmetyczne do sekwencji symboli manipulacji regułami. Peano za Zasady arytmetyki, prezentowane przez nową metodę (1888) była „pierwszą próbą na aksjomatyzacji matematyki w języku symbolicznym”.

Ale Heijenoort daje Frege (1879) to sława: Frege jest „chyba najważniejszym zadaniem, jakie kiedykolwiek napisano w logice ... w którym widzimy.” „Język” wzór, który jest characterica lingua , język pisany ze specjalnymi symbolami „dla czystej myśli”, czyli wolne od retorycznych ozdobników ... zbudowane z określonych symboli, które są manipulowane zgodnie z określonymi regułami”. prace Frege był jeszcze bardziej uproszczone i wzmacniany przez Alfred North Whitehead i Bertrand Russell w swoich Principia Mathematica (1910/13).

Paradoksy : Jednocześnie szereg niepokojących paradoksów pojawił się w literaturze, w szczególności paradoks Burali-Forti (1897), przy czym paradoks Russella (1902/03), a Richard Paradox . Uzyskane rozważania doprowadziły do Kurt Gödel papieru „S (1931) -On szczególności wymienia paradoksu kłamcy-które całkowicie zmniejsza zasady rekursji do numerów.

Skuteczna wymierność : W celu rozwiązania Entscheidungsproblem określonym precyzyjnie przez Hilberta w 1928 roku, matematycy pierwszy przystąpił do zdefiniowania, co rozumie się pod pojęciem „skuteczna metoda” lub „skuteczna obliczenia” lub „skuteczna wymierność” (czyli obliczenie że uda ). W krótkim odstępie czasu dodaje się pojawił: Alonzo Church , Stephen KLEENE i JB Rosser „s X nazębnego drobno szlifowany definicji«ogólnej rekursji»z prac Gödel działając na sugestie Jacques Herbrand (por Gödla Princeton wykłady 1934) i kolejne uproszczeń Kleene. Dowód Kościoła, że Entscheidungsproblem był nierozwiązywalny, Emil post definicja „s skutecznego wymierność jako pracownik bezmyślnie po listę instrukcji, aby przejść w lewo lub w prawo za pośrednictwem sekwencji pomieszczeń i podczas gdy zarówno znak lub usunąć papier lub obserwować papier i zrobić Tak, żadna decyzja o następnej instrukcji. Dowód Alana Turinga stanowi, że Entscheidungsproblem był nierozwiązywalny przez użycie jego „A- [automatic-] maszyny” -w efekt niemal identyczny „preparat” Post, J. Barkley Rosser definicji „s«skutecznego sposobu»w kategoriach„a maszyna". SC Kleene propozycja „s prekursora do« tezy Kościoła », który nazwał«Teza I», a kilka lat później Kleene na zmianę nazwy swojej rozprawie«Thesis Kościoła»i proponując«Thesis Turinga».

Emil post (1936) oraz Alan Turing (1936/37, 1939)

Oto niezwykły zbieg dwóch mężczyzn nie znając siebie, ale opisując proces mężczyzn-as-komputerów pracujących na obliczeniach, i dają one praktycznie identyczne definicje.

Emil post (1936) opisał działania w „Komputer” (człowiek), jak następuje:

”... dwa pojęcia są zaangażowane: że z przestrzeni symbolu , w którym praca prowadząca od problemu odpowiedzieć ma zostać przeprowadzone, oraz ustaloną niezmiennego zestawu kierunkach .

Jego przestrzeń symbol byłby

„Dwukierunkowa nieskończony ciąg spacji lub pudełkach ... solver problem, czy pracownik jest do poruszania się i pracy w tym miejscu symbolu, zdolny do bycia w, ale i działa w jednym oknie na raz .... okno to przyznać, ale z dwóch możliwych warunkach, czyli bycia pusta lub nieoznaczony, posiadające pojedynczy znak w nim, powiedzmy pionowy skok.
„Jedno opakowanie ma być wyodrębniony i nazywa się punktem wyjścia. ... specyficzny problem ma zostać udzielona w formie symbolicznej przez skończoną liczbę skrzynek [tj INPUT] oznaczony udaru. Podobnie, odpowiedź [tj WYJŚCIE] ma być podana w postaci symbolicznej przez takiej konfiguracji pola zaznaczone ...
„Zbiór kierunkach zastosowanie do ogólnego problemu ustawia deterministyczny procesu, gdy stosuje się do każdego konkretnego przypadku. Proces ten kończy się dopiero wtedy, gdy chodzi o kierunek typu (c) [tj STOP]”. Zobacz więcej na maszynie Post-Turinga
Pomnik Alana Turinga w Bletchley Park

Alan Turing praca jest poprzedzona że z Stibitz (1937); nie wiadomo, czy Stibitz wiedział o pracach Turinga. Biograf Turinga Uważa się, że stosowanie Turinga modelu maszyny do pisania, jak pochodzący z młodzieńczej zainteresowania: „Alan marzył wynalezienie maszyny do pisania jako chłopiec; Pani Turing miał maszynę do pisania, i mógł dobrze zaczęły pytając się, co się rozumie przez wywołanie maszyna do pisania „mechaniczne””. Biorąc pod uwagę częstość występowania i telegrafii Morse'a, ticker magnetofony taśmowe i teletypewriters moglibyśmy przypuszczać, że wszystkie były wpływy.

Turing-jego model obliczeń jest teraz nazywa się maszyny Turinga -begins, podobnie jak stanowisko, z analizy komputera ludzkiej że whittles się do prostego zestawu podstawowych ruchów i „stanów umysłu”. Ale on wciąż o krok dalej i tworzy urządzenia jako modelu obliczeń liczb.

„Komputer jest normalnie zrobić pisząc pewne symbole na papierze. Możemy przypuszczać, papier ten został podzielony na kwadraty jak dziecko w książce arytmetycznej ... Zakładam więc, że obliczenia są wykonywane na papierze jednowymiarowej, czyli na taśmie podzielona na kwadraty. ja przypuszczam również, że liczba symboli, które mogą być drukowane jest skończony ...
„Zachowanie komputera w dowolnym momencie jest określana przez symbole, które jest on obserwację, a jego«stan umysłu»w tym momencie. Możemy przypuszczać, że istnieje granica B do liczby symboli lub kwadratów, które komputer może obserwować w jednej chwili. Jeśli chce obserwować więcej, musi korzystać z kolejnych uwag. będziemy również przypuszczać, że liczba stanów umysłu, które muszą być brane pod uwagę jest skończony ...
„Wyobraźmy sobie, że operacje wykonywane przez komputer, aby być podzielony na«proste czynności», które są tak elementarne, że nie jest łatwo je dalej podzielić wyobrazić.”

redukcja Turinga daje następujące:

„Proste operacje muszą zatem zawierać:
„(A) Zmiany symbolu na jednym z placów obserwowanych
„(B), zmiany w jednym z pól zaobserwowanych kwadracie ciągu L kwadratów z jednym z wcześniej obserwowanych kwadratów.

„Może się zdarzyć, że niektóre z tych zmian musi wywołać zmianę stanu umysłu Najbardziej ogólnie pojedyncza operacja musi zatem być uznany za jedną z następujących czynności.:

„(A) Ewentualna zmiana (a) symbolu wraz z ewentualną zmianą stanu umysłu.
„(B) możliwa zmiana (B) obserwowane kwadratów, wraz z możliwością zmiany stanu umysłu”
„Możemy teraz skonstruować maszynę do pracy z tym komputerem.”

Kilka lat później, Turing rozszerzył swoją analizę (praca, rozdzielczość) z tym mocnym wyrazem nim:

„Funkcja nazywa się«efektywnie obliczalne»jeśli jej wartości można znaleźć jakiś proces czysto mechanicznym. Choć jest to dość łatwo dostać się intuicyjne zrozumienie tego pomysłu, to jednak pożądane, aby mieć trochę bardziej wyraźny, matematyczne ekspresji w definicji ... [omawia historię definicji dość dużo jak przedstawiony powyżej w odniesieniu do Gödel, Herbrand, Kleene, kościół, Turing i post]... Możemy wziąć to stwierdzenie dosłownie zrozumienie przez jeden proces czysto mechaniczne, które mogą być wykonywane przez maszyny. jest to możliwe, aby podać opis matematyczny, w pewnej postaci normalnej, o strukturach tych maszyn. rozwój tych idei prowadzi do definicji autora o przeliczalnych funkcji, a do identyfikacji Obliczalność † skuteczne wymierność....
„† Będziemy używać wyrażenia«funkcja obliczalna»oznacza funkcję się obliczyć przez maszynę, a my niech«efektywnie obliczalne»odnoszą się do intuicyjnej idei bez konkretnej identyfikacji z którymkolwiek z tych definicji”.

Rosser JB (1939), SC Kleene (1943)

J. Barkley Rosser określono za „skuteczną [matematycznej] Metoda” w następujący sposób (italicization dodano):

„Stosuje się«Skuteczna metoda»tutaj w dość szczególnym sensie sposobu każdy krok, który jest precyzyjnie określona i które jest pewne, aby produkować odpowiedź w skończonej liczbie kroków. W tym szczególnym znaczeniu, trzy różne precyzyjne definicje nadano do tej pory [jego przypisie nr 5, patrz dyskusja natychmiast poniżej]. najprostszy z nich do stanu (ze względu na post i Turinga) mówi w zasadzie to. istnieje skuteczna metoda rozwiązywania pewnych zestawów problemów jeśli można zbudować maszynę, która będzie następnie rozwiązać każdy problem zestawu bez interwencji człowieka poza włożeniem pytanie i (później) czyta odpowiedź . Wszystkie trzy definicje są równoważne, więc to nie ma znaczenia, który z nich jest używany. Ponadto fakt, że wszystkie trzy są równoważne jest bardzo mocny argument za poprawność jednego „. (Rosser 1939: 225-6)

Rosser za przypis nr 5 odnośników pracach z (1) Kościół i Kleene i ich definicji X-definiowalności, w użyciu partykularnego za nim w jego An nierozwiązywalny problem z Elementary Number Theory (1936); (2) Herbrand i Gödel, a ich stosowanie rekurencji w użyciu konkretnego Gödla w swoim słynnym artykule On formalnie nierozstrzygalny propozycje Principia Mathematica i systemów pokrewnych I (1931); oraz (3) post (1936) oraz Turing (1936/37) w ich mechanizmem modeli obliczeniowych.

Stephen C. Kleene zdefiniowane jako jego teraz-słynnego „Thesis I” znanej jako Hipoteza Churcha-Turinga . Ale zrobił to w następującym kontekście (tłustym drukiem w oryginale):

„12. algorytmiczne teorie ... W stworzenie kompletnej teorii algorytmów, co możemy zrobić, to opisać procedurę, wykonalne dla każdego zbioru wartości zmiennych niezależnych, które niekoniecznie kończy postępowanie i w taki sposób, że z wyników możemy czytaj jednoznacznej odpowiedzi „tak” lub „nie” na pytanie „jest wartością orzecznik prawda?””(Kleene 1943: 273)

Historia po 1950

Szereg wysiłki zostały skierowane na dalsze udoskonalenia definicji „algorytm”, a działalność jest w toku z powodu kwestii związanych w szczególności podstaw matematyki (zwłaszcza Hipoteza Churcha-Turinga ) i filozofii umysłu (zwłaszcza argumentów o sztucznej inteligencji ). Aby uzyskać więcej, zobacz charakteryzacje Algorytm .

Zobacz też

Uwagi

Bibliografia

  • Axt, P (1959). „Na Subrecursive Hierarchii i prymitywne rekurencyjnych Stopni”. Transactions of the American Mathematical Society . 92 : 85-105. doi : 10,2307 / 1993169 . JSTOR  1993169 .
  • Bell, C. Gordon i Newell Allen (1971), Struktury komputerowe: Odczyty i przykłady , McGraw-Hill Book Company, New York. ISBN  0-07-004357-4 .
  • Blass, Andreas ; Gurevich, Yuri (2003). „Algorytmy: poszukiwanie Bezwzględne Definicje” (PDF) . Biuletyn Europejskiego Stowarzyszenia informatyki teoretycznej . 81 . Zawiera doskonałą bibliografię 56 odnośników.
  • Przesiewacz David J. (1984). Człowiek Turinga: Kultura Zachodnia w Computer Age (1984 ed.). University of North Carolina Press, Chapel Hill NC. ISBN  0-8078-1564-0 ., ISBN  0-8078-4108-0 PBK.
  • Boolos George ; Jeffrey Richard (1999) [1974]. Obliczalność i Logic (4th ed.). Cambridge University Press, London. ISBN  0-521-20402-X .: Por Rozdział 3 maszyny Turinga gdzie dyskutują „pewne zbiory przeliczalne nie skutecznie (mechanicznie) przeliczalny”.
  • Burgin, Mark (2004). Super-rekurencyjne algorytmy . Skoczek. ISBN  978-0-387-95569-8 .
  • Campagnolo ML, Moore, C. , i Costa, JF (2000) Analog charakterystyka funkcji subrecursive. W Proc. z 4. Konferencji na temat liczb rzeczywistych i komputery , Odense University, ss. 91-109
  • Kościół, Alonzo (1936a). „An nierozwiązywalny problem elementarnej teorii liczb”. The American Journal of Mathematics . 58 (2): 345-363. doi : 10,2307 / 2371045 . JSTOR  2371045 .Przedrukowany w The nierozstrzygalny , s. 89ff. Pierwszy wyraz „Thesis Kościoła”. Patrz w szczególności strony 100 ( nierozstrzygalne ), gdzie definiuje pojęcie „skutecznego wymierność” w kategoriach „algorytmu”, a on używa słowa „zakończone jest” itp
  • Kościół, Alonzo (1936b). „Notatkę na Entscheidungsproblem”. The Journal of Symbolic Logic . 1 (1): 40-41. doi : 10,2307 / 2269326 . JSTOR  2269326 .Kościół, Alonzo (1936). „Korekta notatkę na Entscheidungsproblem”. The Journal of Symbolic Logic . 1 (3): 101-102. doi : 10,2307 / 2269030 . JSTOR  2269030 .Przedrukowany w The nierozstrzygalny , s. 110ff. Kościół pokazuje, że Entscheidungsproblem jest nierozwiązywalny w około 3 stron tekstu i 3 strony przypisach.
  • Daffa”, Ali Abdullah al (1977). Wkład muzułmanin do matematyki . London: Croom Helm. ISBN  0-85664-464-1 .
  • Davis, Martin (1965). Nierozstrzygalny: Podstawowe papiery na nierozstrzygalne twierdzenia, nierozwiązywalne problemy i funkcje obliczalne . Nowy Jork: Raven Press. ISBN  0-486-43228-9 .Davis daje komentarz przed każdym artykule. Papiery Gödla , Alonzo Church , Turing , Rosser , Kleene i Emil Napisz są włączone; cytowane w artykule wymieniono z nazwy autora.
  • Davis, Martin (2000). Silniki Logic: Matematycy i pochodzeniu komputera . New York: WW Nortion. ISBN  0-393-32229-7 .Davis oferuje zwięzłe biografie Leibniza , Boole'a , Fregego , Cantor , Hilbert , Gödel i Turing z von Neumanna jako show-kradzież złoczyńcy. Bardzo krótkie bios z Joseph Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken , etc.
  •  Ten artykuł zawiera materiał domeny publicznej  z  NIST dokumentu:  Black, Paul E. „algorytm” . Słownik algorytmów i struktur danych .
  • Dean, Tim (2012). „Ewolucja i różnorodność moralne”. Międzynarodowe Bałtyckie Rocznik poznania, logiki i Komunikacji . 7 .
  • Dennett, Daniel (1995). Niebezpieczny pomysł Darwina . New York: Touchstone / Simon & Schuster. ISBN  0-684-80290-2 .
  • Dilson Jesse (2007). Liczydło ((1968,1994), wyd.). St-Martin Press, Nowy Jork. ISBN  0-312-10409-X ., ISBN  0-312-10409-X (pbk).
  • Yuri Gurevich , sekwencyjne Abstrakt Machines państwowe Przechwytywanie sekwencyjne Algorytmy ACM Transactions on Computational Logic, tom 1, nr 1 (lipca 2000), strony 77-111. Zawiera bibliografię 33 źródeł.
  • van Heijenoort Jean (2001). Od Fregego do Gödel, źródło rezerwować z Logiki Matematycznej, 1879-1931 ((1967) red.). Harvard University Press, Cambridge, MA. ISBN  0-674-32449-8 ., 3. wydanie 1976 [?], ISBN  0-674-32449-8 (pbk).
  • Hodges, Andrew (1983). Alan Turing: Enigma . New York: Simon and Schuster . ISBN  0-671-49207-1 ., ISBN  0-671-49207-1 . Por Rozdział „Duch Prawdy” o historii prowadzącej do i omówienie jego dowód.
  • Kleene Stephen C. (1936). „Ogólne Funkcje rekurencyjne liczb naturalnych” . Mathematische Annalen . 112 (5): 727-742. doi : 10.1007 / BF01565439 .Przedstawiony do amerykańskiego Towarzystwa Matematycznego, wrzesień 1935. przedrukowany w The nierozstrzygalny , s. 237ff. Definicja KLEENE jest z „ogólnym rekursji” (znany obecnie jako jim-rekursji) była używana przez Kościół w jego 1935 papieru An nierozwiązywalny problem elementarnej teorii liczb , które okazały się „problem decyzyjny” być „nierozstrzygalne” (czyli wynik negatywny).
  • Kleene Stephen C. (1943). „Predykaty rekurencyjne i kwantyfikatory”. Transakcje Amerykańskie Towarzystwo Matematyczne . 54 (1): 41-73. doi : 10,2307 / 1990131 . JSTOR  1990131 .Przedrukowany w The nierozstrzygalny , s. 255ff. Kleene rafinowany swoją definicję „ogólnego rekursji” i zaczął w swoim rozdziale „teorie 12. algorytmiczne” postulować „Thesis I” (str 274).; miałby później powtarzać tę tezę (w Kleene 1952: 300) i nazwij go "Thesis Kościoła" (1952: 317 KLEENE) (czyli teza Church ).
  • Kleene Stephen C. (1991) [1952]. Wprowadzenie do metamatematyki (red Dziesiąta.). Północno-Holland Publishing Company. ISBN  0-7204-2103-9 . Doskonała inwalidzkim, źródło czytelne odniesienie do matematycznych „fundamentów”.
  • Knuth, Donald (1997). Podstawowe algorytmy, wydanie trzecie . Reading, Massachusetts: Addison-Wesley. ISBN  0-201-89683-4 .
  • Knuth, Donald (1969). Tom 2 / Seminumerical Algorytmy, Sztuka programowania First Edition . Reading, Massachusetts: Addison-Wesley.
  • Kosovsky NK Elementy logiki matematycznej i jej zastosowania do teorii Subrecursive algorytmów , LSU Publ., Leningrad, 1981
  • Kowalski, Robert (1979). "Algorytm = Logic + Control". Communications of the ACM . 22 (7): 424-436. doi : 10,1145 / +359131,359136 .
  • AA Markowa (1954) Teoria algorytmów . [Tłumaczone przez Jacques J. Schorra-Kon i personelu PST] Stopka Moskwie Akademii Nauk ZSRR, 1954 [czyli Jerozolima, Izrael Program do tłumaczenia naukowe, 1961; dostępny od Biura Usług Technicznych, US Dept. of Commerce, Washington] OPIS 444 p. 28 cm. Dodano tp w rosyjskiej tłumaczenie dzieł Instytutu Matematycznego, Akademii Nauk ZSRR, przeciwko 42. Tytuł oryginalny:. Teoriya algerifmov. [QA248.M2943 Dartmouth College Library. US Dept. of Commerce, Biuro Usług Technicznych, numer OTS 60-51085.]
  • Minsky Marvin (1967). Obliczenia: skończone i nieskończone Machines (pierwsze wyd.). Prentice Hall, Englewood Cliffs, NJ. ISBN  0-13-165449-7 .Minsky rozszerza swoje „... pomysł algorytm-skutecznej procedury ...” w rozdziale 5.1 obliczalności, skutecznych procedur i algorytmów. Maszyny nieskończony.
  • Post, Emil (1936). "Skończone Procesy combinatory, Preparat I". The Journal of Symbolic Logic . 1 (3): 103-105. doi : 10,2307 / 2269031 . JSTOR  2269031 .Przedrukowany w The nierozstrzygalny , s. 289ff. Post definiuje prostą algorytmiczne, jak proces mężczyzny pisania znaków i usuwanie znaków i przejście z pudełka do pudełka i ostatecznie powstrzymując, kiedy następuje lista prostych instrukcji. To jest cytowany przez Kleene jako jednego źródła swego „ja”, Thesis tzw Hipoteza Churcha-Turinga .
  • Rogers, Jr Hartley (1987). Teoria funkcji rekurencyjnych i skuteczne obliczalności . MIT Press. ISBN  0-262-68052-1 .
  • Rosser JB (1939). „Nieformalne Ekspozycja Dowody twierdzenia Godła i Kościoła twierdzenia”. Journal of Symbolic Logic . 4 (2): 53-60. doi : 10,2307 / 2269059 . JSTOR  2269059 .Przedrukowany w The nierozstrzygalny , s. 223ff. Jest tu słynna definicja Rosser za „skutecznej metody”:”... sposób każdy etap, który jest precyzyjnie określona i które jest pewne, aby produkować odpowiedź w skończonej liczbie kroków ... maszyny, która będzie następnie rozwiązać każdy problem zestaw bez interwencji człowieka poza włożeniem pytanie i (później) czyta odpowiedź”(str. 225-226, nierozstrzygalne )
  • Santos-Lang, Krzysztof (2014). „Moralne Ekologia Podejścia do Maszyn Etyki”. W van Rysewyk, Simon; Pontier, Matthijs. Maszyna Medical Ethics (PDF) . Szwajcaria: Springer. ss. 111-127. doi : 10.1007 / 978-3-319-08108-3_8 .
  • Scott, Michael L. (2009). Język programowania Pragmatyka (3rd ed.). Morgan Kaufmann Publishers / Elsevier. ISBN  978-0-12-374514-9 .
  • Sipser, Michael (2006). Wprowadzenie do teorii obliczeń . PWS Publishing Company. ISBN  0-534-94728-X .
  • Trzeźwy, Elliott; Wilson, David Sloan (1998). Do innych: ewolucja i Psychologii bezinteresownej Behavior . Cambridge: Harvard University Press.
  • Kamień Harold S. (1972). Wprowadzenie do Organizacji Informatyki i struktur danych (1972 ed.). McGraw-Hill, New York. ISBN  0-07-061726-0 .Por w szczególności pierwszy rozdział zatytułowany: algorytmy Maszyna Turinga, a programy . Jego zwięzłe nieformalna definicja: „... każdy ciąg instrukcji, które mogą być przestrzegane przez robota, nazywany jest algorytm ” (str. 4).
  • Tausworthe Robert C (1977). Standaryzowany Rozwój Komputery: oprogramowanie Część 1 Metod . Englewood Cliffs NJ: Prentice Hall, Inc. ISBN  0-13-842195-1 .
  • Turing Alan M. (1936/37). „On obliczalny numery, wraz z wnioskiem o Entscheidungsproblem”. Proceedings of London Mathematical Society . Seria 2. 42 : 230-265. doi : 10,1112 / PLMS / s2-42.1.230 ., Korekty, jak wyżej, tom. 43 (1937), str. 544-546. Przedrukowany w The nierozstrzygalny , s. 116ff. Słynny papier Turinga zakończone jak dysertacji magisterskich, podczas gdy w King College w Cambridge w Wielkiej Brytanii.
  • Turing Alan M. (1939). „Systemy oparte na logice na porządkowych”. Proceedings of London Mathematical Society . 45 : 161-228. doi : 10,1112 / PLMS / s2-45.1.161 .Przedrukowany w The nierozstrzygalny , s. 155ff. Papier Turinga, który definiuje „wyrocznię” była jego praca doktorska, podczas gdy w Princeton w USA.
  • Biuro Patentów i Znaków Towarowych USA (2006), 2106,02 **> algorytmy matematyczne: 2100 patentowa , Podręcznik Patent Badanie Procedura (MPEP). Najnowsza wersja sierpień 2006

Dalsza lektura

Linki zewnętrzne

repozytoria algorytm
Lecture notes