algorytm

Al-Khwarizmi , imiennik algorytmu z Khorezmia , na sowieckim znaczku pocztowym z okazji 1200. rocznicy jego urodzin

Algorytm jest jednoznaczny przepis dla roztworem problemu lub klasy problemów. Algorytmy składają się ze skończonej liczby dobrze zdefiniowanych pojedynczych kroków. Tak, aby mogły one do wykonania w zaimplementowanym programie komputerowym , ale także w języku ludzkim są sformułowane. Podczas rozwiązywania problemu określone wejście jest przekształcane w określone wyjście.

definicja

Maszyny Turinga i pojęcie algorytmów

Brak matematycznej dokładności terminu algorytm niepokoił wielu matematyków i logików XIX i XX wieku, dlatego w pierwszej połowie XX wieku opracowano cały szereg podejść, które powinny doprowadzić do precyzyjnego zdefiniowania. Główną rolę odgrywają tu pojęcia maszyny Turinga z Alan Turing jeden. Dalsze formalizacje koncepcji obliczalności to maszyny rejestrujące , rachunek lambda ( Alonzo Church ), funkcje rekurencyjne , gramatyki Chomsky'ego (patrz Hierarchia Chomsky'ego ) i algorytmy Markowa .

Wykazano – ze znacznym wkładem samego Alana Turinga – że wszystkie te metody mają tę samą moc obliczeniową (są równie potężne ). Mogą być emulowane przez maszynę Turinga i odwrotnie, mogą emulować maszynę Turinga.

Formalna definicja

Za pomocą pojęcia maszyny Turinga można sformułować następującą formalną definicję pojęcia:

Reguła obliczeniowa do rozwiązania problemu nazywana jest algorytmem wtedy i tylko wtedy, gdy istnieje maszyna Turinga równoważna tej regule obliczeniowej, która zatrzymuje się dla każdego wejścia, które ma rozwiązanie.

Właściwości algorytmu

Z tej definicji można wyprowadzić następujące właściwości algorytmu:

1. Procedura musi być jasno opisana w skończonym tekście (skończoność).
2. Każdy etap procedury musi faktycznie być wykonywalny (wykonywalny).
3. Metoda może wymagać tylko skończonej ilości miejsca do przechowywania w dowolnym momencie (dynamiczna skończoność, patrz złożoność przestrzeni ).
4. Procedura może wymagać tylko skończonej liczby kroków ( zakończenie , patrz także złożoność czasowa ).

Ponadto termin algorytm jest często ograniczony do następujących właściwości w obszarach praktycznych:

1. Algorytm musi dostarczyć ten sam wynik w tych samych warunkach ( determinacja ).
2. Kolejna zasada do zastosowania w procedurze jest jasno określona w każdym momencie ( determinizm ).

Teza Kościoła Turinga

The Church-Turinga teza stanowi, że każdy intuicyjnie obliczalne problem może być rozwiązany przez maszynę Turinga. Jako formalne kryterium algorytmu stosuje się implementowalność w dowolnym formalizmie równoważnym maszynie Turinga, w szczególności implementowalność w języku programowania - jednak termin wymagany przez Church nie jest jeszcze podany.

Pojęcie obliczalności definiuje się w taki sposób, że problem można obliczyć dokładnie, gdy istnieje algorytm (zakończający) dla problemu, to znaczy, gdy odpowiednio zaprogramowana maszyna Turinga może rozwiązać problem w skończonym czasie .

Należy zauważyć, że niejednoznaczność terminu „problem obliczalny intuicyjnie” uniemożliwia matematyczne udowodnienie tej tezy. Teoretycznie można sobie wyobrazić, że istnieją intuicyjnie obliczalne problemy, które nie są uważane za „obliczalne” zgodnie z tą definicją. Jednak do tej pory nie znaleziono takiego problemu.

Abstrakcyjne automaty

Maszyny Turinga dobrze harmonizują z abstrakcyjnymi, obliczalnymi funkcjami matematycznymi , ale rzeczywiste problemy są znacznie bardziej złożone, dlatego sugerowano inne maszyny.

Maszyny te różnią się w przybliżeniu siłą poleceń; Zamiast prostych operacji maszyny Turinga mogą czasami wykonywać potężne operacje, takie jak transformacje Fouriera , w jednym kroku obliczeniowym.

Lub nie są ograniczone do jednej operacji na krok obliczeniowy, ale umożliwiają operacje równoległe, takie jak dodawanie dwóch wektorów w jednym kroku.

Modelem rzeczywistej maszyny jest Sequential Abstract State Machine (short seq.ASM ) o następujących właściwościach:

Algorytm kolejnego ASM ma:

• może być określony przez skończony tekst programu
• można wykonywać stopniowo
• zakończyć dla pewnych stanów, ale nie zawsze musi się kończyć (przydatnym kontrprzykładem wymagania, że ​​zakończenie musi być zawsze przeprowadzane, jest program, który nieustannie znajduje liczby pierwsze lub system operacyjny)
• może zmienić tylko ograniczoną liczbę stanów na krok (ograniczenie równoległości)
• może przeprowadzić inspekcję tylko ograniczonej liczby stanów na krok (ograniczenie eksploracji).

Informatyka i matematyka

Algorytmy są jednym z głównych tematów w informatyce i matematyce . Są one przedmiotem szeregu specjalistycznych dziedzin z zakresu informatyki teoretycznej , teorii złożoności i teorii obliczalności , a czasami osobny dział poświęcony jest algorytmice lub teorii algorytmów . W postaci programów komputerowych i obwodów elektronicznych algorytmy sterują komputerami i innymi maszynami .

Algorytm i programy

Istnieją różne formalne reprezentacje algorytmów. Obejmują one od algorytmu jako abstrakcyjnego odpowiednika do programu specjalnie dopasowanego do maszyny (tzn. abstrakcja odbywa się tutaj poprzez pominięcie szczegółów rzeczywistej maszyny, program jest specyficzną formą algorytmu, dostosowaną do potrzeb i możliwości rzeczywistej maszyny) do poglądu, że algorytmy są właśnie programami maszynowymi maszyn Turinga (przy czym tutaj abstrakcja odbywa się w wykorzystaniu samej maszyny Turinga, czyli idealnej maszyny matematycznej ).

Algorytmy mogą być przedstawiane graficznie na schematach blokowych programu zgodnie z DIN 66001 lub ISO 5807 .

Pierwszy algorytm komputerowy

Pierwszy algorytm przeznaczony dla komputera (do obliczania liczb Bernoulliego ) został zapisany w 1843 roku przez Adę Lovelace w swoich notatkach o silniku analitycznym Charlesa Babbaga . Jest więc uważana za pierwszą kobietę programistkę . Ponieważ Charles Babbage nie mógł ukończyć swojego silnika analitycznego, algorytm Ady Lovelace nigdy nie został na nim zaimplementowany.

Dzisiejsza sytuacja

Zasada działania algorytmu Rete dla systemów ekspertowych ; opublikowano: 1979; wolny

Obecnie algorytmy dla komputerów są tak różnorodne, jak aplikacje, które mają umożliwić. Można znaleźć tysiące algorytmów, od elektronicznych jednostek sterujących do stosowania w pojazdach po kontrolę pisowni i struktury zdań w przetwarzaniu tekstu i analizie rynków akcji . W odniesieniu do idei i zasad, na których oparty jest program komputerowy, algorytmowi zwykle odmawia się ochrony praw autorskich . Jednakże, w zależności od krajowej struktury praw własności intelektualnej, algorytmy informatyki są dostępne do ochrony patentowej , tak że indywidualne dzieła wolne od praw autorskich będące wynikiem własnej twórczości intelektualnej nie zawsze mogą być swobodnie wykorzystywane ekonomicznie. Dotyczy to lub dotyczyło z. B. algorytmy oparte na matematyce transformacji Hougha (dziesięciolecia stare, ale wielokrotnie aktualizowane pojęcie z nową rejestracją), programy, które chciały odczytywać i zapisywać format obrazu GIF , czy programy z zakresu przetwarzania audio i wideo, ponieważ powiązane algorytmy zaimplementowane w powiązanych kodekach często nie są swobodnie dostępne. Odpowiadający temu potencjał oszczędności dla wszystkich użytkowników na całym świecie ( milion USD był kiedyś wspomniany na DEC XCON dla algorytmu Rete ) powinien teraz wielokrotnie przekraczać limit miliarda USD rocznie.

Różnicowanie od heurystyk

Przejście między algorytmami a heurystyką jest płynne: heurystyka to metoda uzyskiwania wyników, które są jak najbardziej znaczące z niekompletnych danych wejściowych. Wiele procedur heurystycznych jest precyzyjnie zdefiniowanych, a więc algorytmów. Dla niektórych jednak nie jest dokładnie określone na każdym kroku, jak postępować – użytkownik musi „zgadywać tanio”. Nie można ich (całkowicie) sformułować jako algorytm.

nieruchomości

Determinacja

Algorytm jest określany, jeśli zapewnia te same wyniki za każdym razem, gdy jest wykonywany z tymi samymi warunkami początkowymi i danymi wejściowymi.

determinizm

Algorytm jest deterministyczny, jeśli następny krok jest jasno określony w każdym momencie wykonywania algorytmu . Jeżeli istnieje więcej niż jedna możliwość w co najmniej jednym punkcie (bez określenia, którą wybrać), to cały algorytm jest niedeterministyczny .

Przykładami algorytmów deterministycznych są sortowanie bąbelkowe i algorytm euklidesowy . Obowiązuje tu, że każdy algorytm deterministyczny jest określony, a nie każdy algorytm wyznaczany jest deterministyczny. Czyli Quicksort z losowym wyborem elementu pivot jest przykładem algorytmu deterministycznego, ale nie deterministycznego, ponieważ jego wynik dla tego samego wejścia i jednoznacznej kolejności jest zawsze taki sam, ale jest wykonywany losowo.

Ogólnie rzecz biorąc, niedeterministycznych algorytmów nie można zaimplementować bezpośrednio w żadnej rzeczywistej maszynie (nawet w komputerach kwantowych ) .

Przykładem niedeterministycznego algorytmu byłby przepis kulinarny, który opisuje kilka wariantów. To od kucharza zależy, który zechce wykonać. Nawet przejście przez labirynt pozostawia kilka opcji na każdym skrzyżowaniu, a oprócz wielu ślepych zaułków, do wyjścia może prowadzić kilka ścieżek.

Skończoność

Skończoność statyczna

Opis algorytmu ma skończoną długość, więc tekst źródłowy musi składać się z ograniczonej liczby znaków.

Skończoność dynamiczna

Algorytm może wymagać tylko ograniczonej ilości miejsca do przechowywania w dowolnym momencie podczas jego wykonywania.

Rozwaga

Algorytm ' kończy się wszędzie ' lub 'kończy się', jeśli zatrzymuje się (lub zatrzymuje się w kontrolowany sposób) po skończonej liczbie kroków - dla każdego możliwego wejścia. Algorytm niekończący (a więc nie dający żadnego wyniku) wchodzi w tak zwaną pętlę nieskończoną (dla niektórych danych wejściowych).

W przypadku niektórych procesów pożądane jest zachowanie niekończące się, np. B. Systemy kontroli, systemy operacyjne i programy, które opierają się na interakcji z użytkownikiem. O ile użytkownik nie wyda polecenia wyjścia, te programy z założenia działają w nieskończoność. Donald Knuth sugeruje w tym kontekście, aby algorytmy i metody obliczeniowe (Computational Methods) nie były wywoływane.

Ponadto nie można zdecydować o zakończeniu algorytmu ( problem zatrzymania ) . Oznacza to, że problem ustalenia, czy (dowolny) algorytm kończy się z jakimkolwiek wejściem, nie może być rozwiązany przez algorytm.

skuteczność

Efekt każdej instrukcji algorytmu musi być jasno określony.

Przykłady (dalszych) właściwości algorytmów

• Prosta podstawowa operacja: „Otwórz butelkę wina”. - Tutaj zakłada się znajomość sposobu jej otwierania.
• Algorytm sekwencyjny: „Piwo na winie, niech tak będzie.” - Obie operacje mają przypisaną sekwencję.
• Algorytm współbieżny: „Sok jabłkowy i woda sodowa są pijane.” - Kolejność nie jest określona i może odbywać się jednocześnie.
• Wykonanie równoległe: „Tosty z szampanem” - można to wykonać tylko w tym samym czasie (równolegle), a nie jeden po drugim (sekwencyjnie).
• Algorytm niedeterministyczny/nieokreślony: „Dodaj do ciasta 200 ml piwa lub wody.” - Wynik może się różnić w zależności od wybranej alternatywy.

Analiza algorytmu

Badanie i analiza algorytmów jest głównym zadaniem informatyki i odbywa się głównie teoretycznie (bez konkretnej implementacji w języku programowania). Jest to zatem podobne do procedury w niektórych obszarach matematycznych, w których analiza koncentruje się bardziej na podstawowych pojęciach niż na konkretnych implementacjach. Algorytmy są poddawane analizie w postaci silnie sformalizowanej i badane za pomocą środków semantyki formalnej .

Analiza podzielona jest na różne podobszary:

• Na przykład zachowanie algorytmów w odniesieniu do wymagań dotyczących zasobów , takich jak wymagania dotyczące czasu obliczeniowego i pamięci, jest przedmiotem teorii złożoności ; wyniki są zwykle podawane asymptotycznie (np. jako asymptotyczny czas przebiegu ). Zapotrzebowanie na zasoby jest generalnie określane w zależności od długości danych wejściowych, to znaczy zapotrzebowanie na zasoby zależy głównie od tego, ile wartości wejściowych ma zostać przetworzonych, „jak „duży” jest wkład (ilość)”.
• Zachowanie w odniesieniu do terminacji, czyli tego, czy algorytm może kiedykolwiek zakończyć się pomyślnie, zajmuje się teorią obliczalności .

Rodzaje i przykłady

Rozwiązanie do gry Towers of Hanoi z trzema kawałkami - prosty algorytm

Najstarszym znanym nietrywialnym algorytmem jest algorytm euklidesowy . Specjalne typy algorytmów to algorytm randomizowany (ze składnikiem losowym), algorytm aproksymacyjny (jako metoda aproksymacyjna), algorytmy ewolucyjne (oparte na modelu biologicznym) oraz algorytm zachłanny .

Lista algorytmów i kategoria Algorytm zapewniają dalszy przegląd .

Codzienne formy algorytmów

Reguły obliczeniowe są podgrupą algorytmów. Opisują instrukcje matematyczne w odniesieniu do liczb. Inne podgrupy algorytmów to m.in. B. Przepisy kulinarne, przepisy, regulaminy, umowy, instrukcje montażu.

Pochodzenie słowa

Strona z tłumaczenia łacińskiego (rękopis z Cambridge) rozpoczynająca się od „Dixit algorizmi”

Słowo algorytm jest modyfikacją lub zniekształceniem imienia perskiego mistrza arytmetyki i astronoma Abu Dschaʿfara Muhammada ibn Musa al-Chwārizmī , którego część imienia ( Nisba ) al-Chwarizmi oznacza „Choresmier” i odnosi się do pochodzenia okaziciel z Choresmii . Oparł się na pracach indyjskiego matematyka Brahmagupty z VII wieku . Pierwotnym znaczeniem było przestrzeganie zasad arytmetycznych przy użyciu cyfr indoarabskich . Oryginalna definicja ewoluowała wraz z tłumaczeniem na łacinę. Jego podręcznik O cyfrach indyjskich (napisany ok. 825 r. w Domu Mądrości w Bagdadzie ) został przetłumaczony z arabskiego na łacinę w XII wieku i tym samym stał się obok Leonarda Pisanosa najważniejszym źródłem wiedzy i rozpowszechniania języka indyjskiego w świecie zachodnim Liber Abaci System liczb arabskich i arytmetyka pisemna. W łacińskim tłumaczeniu al-Chwārizmī nazwisko autora również zostało zlatynizowane, opierając się na pierwszych słowach najstarszej wersji tego tłumaczenia ( Dixit Algorismi „Algorismi powiedział”). Al-Chwārizmī przekształciło się w średniowysoko-niemiecki algorismus, alchorismus lub algoarismus - słowo, które zostało przetłumaczone z łaciny prawie jednocześnie i identycznie na starofrancuski ( algorisme , argorisme) i średnioangielski ( augrim , augrim ). Algoryzm był terminem używanym do opisu podręczników, które wprowadzały do ​​około 1600 r. używanie numerów palców, liczydła, zera, liczb indyjsko-arabskich i arytmetyki pisanej. Arytmetyka pisana dopiero stopniowo zyskała akceptację. Na przykład angielski poeta Geoffrey Chaucer opisuje w swoich Opowieściach kanterberyjskich pod koniec XIV wieku astrologa, który trzymał „kamienie augymowe” u wezgłowia łóżka:

Ten urzędnik był cleped hende Nicholas. / Jego augrym kamienie leżały osobno, / Na półkach rozłożonych u jego łóżka uwaga;

W średniowiecznej tradycji szybko okazało się, że słowo to wymaga wyjaśnienia, a od XIII wieku głównie jako kompozycja imienia Algus i greckiego ῥυσμός (forma załącznika od ῥυθμός ) oznaczającego zapożyczony element słowa "liczba" - rismus interpretowany.

Algus, rzekomy wynalazca tej sztuki arytmetyki, był postrzegany przez niektórych jako Arab, przez innych jako Grek lub przynajmniej autor piszący po grecku, a czasami także jako „Król Kastylii” (Jan z Norfolk). W tradycji wernakularnej ten „mistrz Algus” pojawia się czasem w szeregu z wielkimi starożytnymi myślicielami, takimi jak Platon , Arystoteles i Euklides , jak w starej francuskiej powieści de la Rose , podczas gdy stary włoski wiersz Il Fiore zrównuje go nawet z budowniczym statku Argo , którym Jason wyruszył w poszukiwaniu Złotego Runa.

Na para-etymologiczny śledzenia tyłu drugiego składnika -rism greckim ῥυσμός , ῥυθμός , tym bardziej precyzyjna forma łacińskiego słowa Algorytm bazuje , który od wczesnego czasach współczesnych , początkowo także z wariantu pisowni algorythmus , zyskała szerokie zastosowanie i większą wreszcie słowo oznaczające, które jest dziś zwyczajowo terminem technicznym dla uregulowanych procedur rozwiązywania określonych problemów.

Historia algorytmu

rozwój historyczny

Wraz z rozwojem języka ludzie wymyślali zasady postępowania, przykazania, prawa - najprostsze algorytmy - do wspólnego życia w większych grupach. Język jest również odpowiednim sposobem przekazywania procedur i umiejętności - bardziej złożonych algorytmów. Pierwsze zawody powstały ze specjalizacji poszczególnych członków grupy w określonych umiejętnościach.

Pojęcie algorytmów jako abstrakcyjnego spojrzenia na ścieżki rozwiązywania problemów po raz pierwszy weszło do świadomości ludzi w kontekście matematyki, logiki i filozofii. Przykładem starożytnego algorytmu matematycznego jest algorytm Euklidesa .

Starożytna Grecja

Chociaż pochodzenie etymologiczne tego słowa jest arabskie, pierwsze algorytmy powstały w starożytnej Grecji . Najważniejszą przykłady obejmują Sito Eratostenesa do znajdowania liczb pierwszych , które zostało opisane w książce Wprowadzenie do arytmetyki przez Nikomachus i euklidesowej algorytmu obliczania największy wspólny dzielnik dwóch liczb naturalnych z pracy „ elementów ”. Jednym z najstarszych algorytmów zajmujących się liczbą rzeczywistą jest algorytm Archimedesa do aproksymacji , który jest również jedną z najstarszych metod numerycznych .${\ styl wyświetlania \ pi}$

Matematyka w XIX i XX wieku

Poważną pracę wykonali XIX-wieczni logicy. George Boole , który stworzył pierwszy rachunek logiki algebraicznej w swojej pracy The Mathematical Analysis of Logic , stworzył w ten sposób nowoczesną logikę matematyczną, która różni się od tradycyjnej logiki filozoficznej spójną formalizacją. Gottlob Frege był pierwszym, który opracował język formalny i wynikające z tego dowody formalne . Giuseppe Peano zredukował arytmetykę do sekwencji symboli manipulowanych przez symbole. Zajmował się aksjomatyką liczb naturalnych. W tym miejscu pojawiły się aksjomaty Peano .

Praca Fregego została znacznie rozwinięta i uproszczona przez Alfreda Northa Whiteheada i Bertranda Russella w ich Principia Mathematica . Bertrand Russell wcześniej sformułował słynną antynomię Russella , która doprowadziła do upadku naiwnej teorii mnogości . Rezultat doprowadził również do pracy Kurta Gödla .

David Hilbert sformułował problem decyzyjny właśnie w swoim programie badawczym około 1928 roku . Alan Turing i Alonzo Church uznali problem za nierozwiązywalny w 1936 roku.

literatura

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein : Algorytmy. Wstęp. 2., kor. Wydanie. Oldenbourg, Monachium, Wiedeń 2007, ISBN 3-486-58262-3 . (Tytuł oryginalny: Wprowadzenie do algorytmów. Tłumaczone przez Karen Lippert, Micaela Krieger-Hauwede).
  Oryginalne wydanie w języku angielskim: Wprowadzenie do algorytmów. Wydanie II. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7 .
• Christoph Drösser : Całkowicie przewidywalny? Kiedy decydują za nas algorytmy. Hanser-Verlag , 2016, ISBN 978-3-446-44699-1 .
• John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Wprowadzenie do teorii automatów, języków formalnych i teorii złożoności . 2., poprawione. Wydanie. Pearson Studium, Monachium 2002, ISBN 3-8273-7020-5 (tytuł oryginalny: Wprowadzenie do teorii automatów, języków i obliczeń . Przetłumaczone przez Sigrid Richter, Ingrid Tokar). 
• Donald E. Knuth : Sztuka programowania komputerowego . Tom 1-3. Addison-Wesley, Reading (Mass.) 1998, ISBN 0-201-48541-9 .
• Anany Levitin: Wprowadzenie do projektowania i analizy algorytmów. Addison-Wesley, 2007, ISBN 0-321-36413-9 .
• Thomas Ottmann, Peter Widmayer: Algorytmy i struktury danych. Wydanie IV. Wydawnictwo Akademickie Spectrum, Heidelberg 2002, ISBN 3-8274-1029-0 .
• Sebastian Stiller: Planeta algorytmów - przewodnik turystyczny. Knaus-Verlag , 2015. ISBN 978-3-641-16793-6 .
• Jochen Ziegenbalg, Oliver Ziegenbalg i Bernd Ziegenbalg: O koncepcji algorytmu. W: Algorytmy od Hammurabiego do Gödla. 3. Wydanie. Niemiecki, Frankfurt 2010, ISBN 978-3-8171-1864-9 , s. 24-31.

linki internetowe

Wikisłownik: Algorytm  - wyjaśnienia znaczeń, pochodzenie słów, synonimy, tłumaczenia

• Tom Schimmeck : Algorytmy w amerykańskim systemie sprawiedliwości: maszyny losu. W: deutschlandfunk.de , 20 czerwca 2017,
• Algorytm tygodnia (jasno wyjaśnione algorytmy, opublikowany przez Dzień Wydziału Informatyki)
• Słownik Algorytmy i struktury danych z NIST (English)
• Czym jest algorytmika? - Strona na Wydziale Informatyki TU Darmstadt
• Notatki z wykładów na temat wyższych algorytmów na FU Berlin (PDF; 1,9 MB)

Przypisy