algoritme

Van Wikipedia, de gratis encyclopedie
Spring naar navigatie Spring naar zoeken
Al-Khwarizmi , de naamgenoot van het algoritme uit Khoresmia , op een Sovjet- postzegel ter gelegenheid van zijn 1200-jarig jubileum

Een algoritme is een eenduidige regel voor de oplossing van een probleem of een klasse van problemen. Algoritmen bestaan ​​uit een eindig aantal goed gedefinieerde individuele stappen. [1] Zodat ze voor uitvoering in een computerprogramma geïmplementeerd kunnen worden , maar ook in mensentaal zijn geformuleerd. Bij het oplossen van een probleem wordt een specifieke input omgezet in een specifieke output. [2]

definitie

Turingmachines en het concept van algoritmen

Het gebrek aan wiskundige nauwkeurigheid van de term algoritme stoorde veel wiskundigen en logici van de 19e en 20e eeuw, daarom werd in de eerste helft van de 20e eeuw een hele reeks benaderingen ontwikkeld die tot een nauwkeurige definitie moesten leiden. Het concept van de Turingmachine van Alan Turing speelt hierbij een centrale rol. Verdere formaliseringen van het begrip berekenbaarheid zijn de registermachines , de lambda-calculus ( Alonzo Church ), recursieve functies , Chomsky-grammatica's (zie Chomsky-hiërarchie ) en Markov-algoritmen .

Er werd aangetoond - met een belangrijke bijdrage van Alan Turing zelf - dat al deze methoden dezelfde rekenkracht hebben (even krachtig zijn ). Ze kunnen worden nagebootst door een Turing-machine en omgekeerd kunnen ze een Turing-machine nabootsen.

Formele definitie

Met behulp van het concept van de Turingmachine kan de volgende formele definitie van het concept worden geformuleerd:

Een rekenregel voor het oplossen van een probleem wordt een algoritme genoemd als en slechts als er een Turingmachine is die equivalent is aan deze rekenregel, die stopt voor elke invoer die een oplossing heeft.

Eigenschappen van het algoritme

Uit deze definitie kunnen de volgende eigenschappen van een algoritme worden afgeleid:

  1. De procedure moet duidelijk te omschrijven zijn in een eindige tekst (eindigheid).
  2. Elke stap van de procedure moet ook daadwerkelijk haalbaar zijn (haalbaarheid).
  3. De methode kan op elk moment slechts een eindige hoeveelheid opslagruimte nodig hebben (dynamische eindigheid, zie ruimtecomplexiteit ).
  4. De procedure kan slechts een eindig aantal stappen vereisen ( beëindiging , zie ook tijdscomplexiteit ).

Bovendien is de term algoritme vaak beperkt tot de volgende eigenschappen op praktische gebieden:

  1. Het algoritme moet onder dezelfde condities hetzelfde resultaat opleveren ( determinacy ).
  2. De volgende regel die in de procedure moet worden toegepast, is op elk moment duidelijk gedefinieerd ( determinisme ).

Church-Turing-these

De Church-Turing-these stelt dat elk intuïtief berekenbaar probleem kan worden opgelost door een Turing-machine. Als formeel criterium voor een algoritme gebruikt men de implementeerbaarheid in elk formalisme dat equivalent is aan een Turing-machine, in het bijzonder de implementeerbaarheid in een programmeertaal - de door Church vereiste beëindiging is echter nog niet gegeven.

Het concept van berekenbaarheid is zo gedefinieerd dat een probleem precies kan worden berekend wanneer er een (terminerend) algoritme voor het probleem is, dat wil zeggen wanneer een correct geprogrammeerde Turing-machine het probleem in een eindige tijd zou kunnen oplossen.

Opgemerkt moet worden dat de dubbelzinnigheid van de term "intuïtief berekenbaar probleem" het wiskundige bewijs van deze stelling onmogelijk maakt. Het is theoretisch denkbaar dat er intuïtief berekenbare problemen zijn die volgens deze definitie niet als "berekenbaar" worden beschouwd. Een dergelijk probleem is tot op heden echter niet gevonden. [3]

abstracte automaten

Turingmachines harmoniëren goed met de abstract mathematisch berekenbare functies , maar echte problemen zijn veel complexer, daarom zijn er andere machines voorgesteld.

Deze machines verschillen grofweg in de kracht van de commando's; In plaats van de eenvoudige bewerkingen van de Turing-machine, kunnen ze soms krachtige bewerkingen, zoals Fourier-transformaties , in één rekenstap uitvoeren.

Of ze zijn niet beperkt tot één bewerking per rekenstap, maar maken parallelle bewerkingen mogelijk, zoals het optellen van twee vectoren in één stap.

Een model van een echte machine is de Sequential Abstract State Machine (short seq. ASM ) [4] met de volgende eigenschappen:

Een algoritme van een volgende ASM wordt verondersteld

  • kan worden gespecificeerd door een eindige programmatekst
  • kan geleidelijk worden uitgevoerd
  • beëindigen voor bepaalde toestanden, maar hoeft niet altijd te eindigen (handige tegenvoorbeelden voor de eis dat beëindiging altijd moet worden gemaakt, zijn een programma dat continu priemgetallen vindt of een besturingssysteem)
  • kan slechts een beperkt aantal toestanden per stap wijzigen (beperking van parallellisme)
  • kan slechts een beperkt aantal toestanden per stap inspecteren (beperking van exploratie).

Informatica en wiskunde

Algoritmen zijn een van de centrale onderwerpen in de informatica en wiskunde . Ze zijn het onderwerp van een aantal specialistische gebieden in theoretische informatica , complexiteitstheorie en berekenbaarheidstheorie , en soms is een aparte afdeling gewijd aan algoritmiek of algoritmetheorie . In de vorm van computerprogramma's en elektronische schakelingen besturen algoritmen computers en andere machines .

Algoritme en programma's

Er zijn verschillende formele representaties voor algoritmen. Deze variëren van het algoritme als abstracte tegenhanger tot een programma dat specifiek is afgestemd op een machine (dat wil zeggen, de abstractie vindt hier plaats door de details van de echte machine weg te laten, het programma is een specifieke vorm van het algoritme, aangepast aan de behoeften en mogelijkheden van de echte machine) tot de opvatting dat algoritmen precies de machineprogramma's van Turingmachines zijn (waarbij hier de abstractie plaatsvindt in het gebruik van de Turingmachine zelf, dat wil zeggen een ideale wiskundige machine ).

Algoritmen kunnen grafisch worden weergegeven in programmastroomschema 's volgens DIN 66001 of ISO 5807 .

Eerste computeralgoritme

Het eerste algoritme bedoeld voor een computer (voor het berekenen van Bernoulli-getallen ) werd in 1843 vastgelegd door Ada Lovelace in haar aantekeningen op Charles Babbag's Analytical Engine . Ze wordt dan ook beschouwd als de eerste vrouwelijke programmeur . Omdat Charles Babbage zijn analytische engine niet kon voltooien, is het algoritme van Ada Lovelace er nooit op geïmplementeerd.

Situatie van vandaag

Principe van het Rete-algoritme voor expertsystemen ; gepubliceerd: 1979; vrij

Algoritmen voor computers van tegenwoordig zijn net zo divers als de toepassingen die ze zouden moeten mogelijk maken. Er zijn duizenden algoritmen te vinden, van elektronische regeleenheden voor gebruik in voertuigen tot spelling- en zinsstructuurcontrole bij tekstverwerking en analyse van aandelenmarkten . Met betrekking tot de ideeën en principes waarop een computerprogramma is gebaseerd, wordt een algoritme meestal geen auteursrechtelijke bescherming verleend . [5] Afhankelijk van de nationale structuur van intellectuele eigendomsrechten zijn er echter computerwetenschappelijke algoritmen beschikbaar voor octrooibescherming , zodat auteursrechtvrije individuele werken, als resultaat van de eigen intellectuele creatie, toch niet altijd vrij economisch kunnen worden geëxploiteerd. Dit betreft of betreft z. B. algoritmen die gebaseerd zijn op de wiskunde van de Hough-transformatie (decennia oud, maar herhaaldelijk bijgewerkt concept met nieuwe registratie), programma's die het beeldformaat GIF wilden lezen en schrijven, of programma's op het gebied van audio- en videoverwerking, sinds de bijbehorende algoritmen, zoals geïmplementeerd in de bijbehorende codecs , zijn vaak niet vrij beschikbaar. Het bijbehorende besparingspotentieel voor alle gebruikers wereldwijd (één miljoen USD werd ooit genoemd op DEC XCON voor het Rete-algoritme ) zou nu gemakkelijk tientallen keren de limiet van één miljard USD per jaar moeten overschrijden.

Differentiatie van heuristieken

De overgang tussen algoritmen en heuristieken is vloeiend: een heuristiek is een methode om zo zinvolle mogelijk resultaten te krijgen uit onvolledige invoergegevens. Veel heuristische procedures zijn zelf nauwkeurig gedefinieerd en dus algoritmen. Voor sommigen is het echter niet bij elke stap precies aangegeven hoe te handelen - de gebruiker moet "goedkoop raden". Ze zijn niet (volledig) als algoritme te formuleren.

eigenschappen

Bepaling

Een algoritme wordt bepaald als het dezelfde resultaten levert elke keer dat het wordt uitgevoerd met dezelfde startvoorwaarden en invoer.

determinisme

Een algoritme is deterministisch als de volgende stap duidelijk is gedefinieerd op elk moment waarop het algoritme wordt uitgevoerd . Als er meer dan één mogelijkheid is op ten minste één punt (zonder een specificatie welke te kiezen), dan is het hele algoritme niet- deterministisch .

Voorbeelden van deterministische algoritmen zijn bellensoort en het Euclidische algoritme . Hierbij geldt dat elk deterministisch algoritme bepaald is, terwijl niet elk bepaald algoritme deterministisch is. Quicksort met een willekeurige selectie van het pivot-element is een voorbeeld van een bepaald, maar niet-deterministisch algoritme, omdat het resultaat altijd hetzelfde is met dezelfde invoer en eenduidige sortering, maar de manier waarop is willekeurig.

Over het algemeen kunnen niet-deterministische algoritmen niet rechtstreeks met een echte machine worden geïmplementeerd (zelfs niet met kwantumcomputers ).

Een voorbeeld van een niet-deterministisch algoritme is een kookrecept dat verschillende varianten beschrijft. Het is aan de kok welke hij wil uitvoeren. Zelfs als je door een doolhof loopt, zijn er bij elke kruising verschillende opties, en naast veel doodlopende wegen kunnen er ook meerdere paden naar de uitgang leiden.

eindigheid

Statische eindigheid

De beschrijving van het algoritme heeft een eindige lengte, dus de brontekst moet uit een beperkt aantal karakters bestaan.

Dynamische eindigheid

Een algoritme kan op enig moment tijdens de uitvoering slechts een beperkte hoeveelheid opslagruimte nodig hebben.

Beraadslaging

Een algoritme ' beëindigt overal ' of 'beëindigt' als het stopt (of gecontroleerd stopt) na een eindig aantal stappen - voor elke mogelijke invoer. Een niet-afsluitend algoritme (dat dus geen resultaat oplevert) komt in een zogenaamde oneindige lus (voor sommige ingangen).

Voor sommige processen is een niet-beëindigend gedrag gewenst, b.v. B. Besturingssystemen, besturingssystemen en programma's die afhankelijk zijn van interactie met de gebruiker. Tenzij de gebruiker een opdracht geeft om af te sluiten, blijven deze programma's door hun ontwerp voor onbepaalde tijd draaien. Donald Knuth suggereert in dit verband te verwijzen naar niet-beëindigende algoritmen en computationele methoden (Computational Methods).

Bovendien kan de beëindiging van een algoritme (het stopprobleem ) niet worden beslist . Dat wil zeggen, het probleem om te bepalen of een (enig) algoritme eindigt met een invoer kan niet worden opgelost door een algoritme.

effectiviteit

Het effect van elke instructie van een algoritme moet duidelijk worden gedefinieerd.

Voorbeelden van (verdere) eigenschappen van algoritmen

  • Eenvoudige basishandeling: "Open de fles wijn." - Kennis van het openen wordt hier verondersteld.
  • Sequentieel algoritme: “Bier op wijn, let it be.” - Beide bewerkingen krijgen een volgorde.
  • Gelijktijdig algoritme: "Appelsap en frisdrank zijn dronken." - De bestelling is niet gespecificeerd en kan ook tegelijkertijd plaatsvinden.
  • Parallelle uitvoering: "Toast met champagne" - dit kan alleen tegelijkertijd (parallel) en niet na elkaar (sequentieel) worden uitgevoerd.
  • Niet-deterministisch / niet-bepaald algoritme: "Voeg 200 ml bier of water toe aan het deeg." - Het resultaat kan verschillen afhankelijk van welk alternatief je kiest.

Algoritme analyse

Het onderzoek en de analyse van algoritmen is een hoofdtaak van de informatica en wordt meestal theoretisch uitgevoerd (zonder concrete implementatie in een programmeertaal). Het is daarom vergelijkbaar met de procedure in sommige wiskundige gebieden, waarbij de analyse meer gericht is op de onderliggende concepten dan op concrete implementaties. Algoritmen worden in een sterk geformaliseerde vorm gebracht voor analyse en onderzocht met behulp van formele semantiek .

De analyse is onderverdeeld in verschillende deelgebieden:

  • Het gedrag van algoritmen met betrekking tot resourcevereisten zoals rekentijd en geheugenvereisten wordt bijvoorbeeld behandeld in de complexiteitstheorie ; de resultaten worden meestal asymptotisch gegeven (bijvoorbeeld als een asymptotische looptijd ). De resourcebehoefte wordt over het algemeen bepaald afhankelijk van de lengte van de input, dat wil zeggen, de resourcebehoefte hangt vooral af van hoeveel inputwaarden er verwerkt moeten worden, "hoe 'groot' de input (hoeveelheid) is".
  • Het gedrag met betrekking tot de beëindiging, dat wil zeggen of het algoritme ooit met succes kan worden beëindigd, wordt behandeld door de theorie van berekenbaarheid .

Soorten en voorbeelden

De oplossing voor het spel Towers of Hanoi met drie stukken - een eenvoudig algoritme

Het oudst bekende niet- triviale algoritme is het Euclidische algoritme . Speciale typen algoritmen zijn het gerandomiseerde algoritme (met een willekeurige component), het benaderingsalgoritme (als benaderingsmethode), de evolutionaire algoritmen (gebaseerd op een biologisch model) en het hebzuchtige algoritme .

De lijst met algoritmen en de categorie Algoritme geven een verder overzicht.

Alledaagse vormen van algoritmen

Rekenregels zijn een subgroep van de algoritmen. Ze beschrijven instructies in de wiskunde met betrekking tot getallen. Andere subgroepen van algoritmen zijn b.v. B. (Kook)recepten, wetten, regels, contracten, montage-instructies.

Woord oorsprong

Pagina uit een Latijnse vertaling (Cambridge manuscript) beginnend met "Dixit algorizmi"

Het woord algoritme is een wijziging of verbastering van de naam van de Pers [6] [7] [8] rekenkundige en astronoom Abu Dschaʿfar Muhammad ibn Musa al-Chwārizmī , wiens naamcomponent ( Nisba ) al-Chwarizmi "de Choresmier" betekent en verwijst naar de oorsprong van de drager uit Khorezmia verwijst. Hij bouwde voort op het werk van de 7e-eeuwse Indiase wiskundige Brahmagupta . [9] [10] De oorspronkelijke betekenis was de naleving van de rekenkundige regels met behulp van de Indo-Arabische cijfers . De oorspronkelijke definitie evolueerde met de vertaling in het Latijn. [11] Zijn leerboek About the Indian Numbers (geschreven rond 825 in het Huis van Wijsheid in Bagdad ) werd in de 12e eeuw vanuit het Arabisch in het Latijn vertaald, waardoor het naast Leonardo Pisanos Liber de belangrijkste bron van kennis en verspreiding in de westerse wereld is. Abaci het Indiaas-Arabische getalsysteem en geschreven rekenkunde. Met de Latijnse vertaling al-Chwārizmī werd ook de naam van de auteur gelatiniseerd, gebaseerd op de eerste woorden van de oudste versie van deze vertaling ( Dixit Algorismi "Algorismi heeft gezegd"). [12] Al-Chwārizmī werd Middelhoogduits algorismus, alchorismus of algoarismus - een woord dat bijna gelijktijdig en identiek uit het Latijn werd vertaald in het Oudfrans ( algorisme , argorisme) en het Middelengels ( augrim , augrym ). Algorisme was de term die werd gebruikt om leerboeken te beschrijven die het gebruik van vingernummers, telraam, nul, Indiaas-Arabische getallen en geschreven rekenkunde introduceerden tot ongeveer 1600. [13] Geschreven rekenen werd pas geleidelijk aan geaccepteerd. Zo beschrijft de Engelse dichter Geoffrey Chaucer in zijn Canterbury Tales aan het einde van de 14e eeuw een astroloog die "augrymstenen" aan het hoofdeinde van zijn bed bewaarde:

Deze klerk werd gecleped hende Nicholas. / Zijn augrymstenen lagen mooi uit elkaar, / Op planken die aan zijn bedden lagen;

In de middeleeuwse traditie kreeg het woord al snel behoefte aan uitleg en sinds de 13e eeuw meestal geïnterpreteerd als een combinatie van een persoonlijke naam Algus en een woordcomponent -rism geleend van het Griekse ῥυσμός ( subvorm van ῥυθμός ) dat "getal" betekent .

Algus, de veronderstelde uitvinder van deze rekenkunst, werd door sommigen beschouwd als een Arabier, door anderen als een Griek of op zijn minst een auteur die in het Grieks schreef, en af ​​en toe ook als de "Koning van Castilië" (Johannes van Norfolk). In de volkstaal staat deze "meester Algus" soms in een rij met grote oude denkers zoals Plato , Aristoteles en Euclides , zoals in de oude Franse roman de la Rose , terwijl het oude Italiaanse gedicht Il Fiore hem zelfs gelijkstelt met de bouwer van het schip Argo , waarmee Jason op zoek ging naar het Gulden Vlies.

Op de para-etymologische terugvoering van de tweede component -risma naar het Griekse ῥυσμός , ῥυθμός , is het preciezere Latijnse woordvormalgoritme gebaseerd , dat sinds de vroegmoderne tijd , aanvankelijk ook met de spellingsvariant algoritme , op grotere schaal is gebruikt en ten slotte het woord dat tegenwoordig algemeen wordt gebruikt als een technische term die wordt geaccepteerd voor gereguleerde procedures voor het oplossen van gedefinieerde problemen.

Geschiedenis van het algoritme

historische ontwikkeling

Zelfs met de ontwikkeling van de taal kwamen mensen met gedragsregels, geboden, wetten - de eenvoudigste algoritmen - om in grotere groepen samen te leven. Taal is ook een geschikte manier om procedures en vaardigheden door te geven - complexere algoritmen. De eerste beroepen zijn ontstaan ​​uit de specialisatie van individuele groepsleden in bepaalde vaardigheden.

Het concept van algoritmen als een abstracte kijk op probleemoplossende paden kwam voor het eerst in het bewustzijn van mensen in de context van wiskunde, logica en filosofie. Een voorbeeld van een oud wiskundig algoritme is het Euclidische algoritme .

Het oude Griekenland

Hoewel de etymologische oorsprong van het woord Arabisch is, ontstonden de eerste algoritmen in het oude Griekenland . De belangrijkste voorbeelden zijn de zeef van Eratosthenes voor het vinden van priemgetallen , die werd beschreven in het boek Introduction to Arithmetic van Nicomachus [14] en het Euclidische algoritme voor het berekenen van de grootste gemene deler van twee natuurlijke getallen uit het werk " The Elements ". [15] Een van de oudste algoritmen die met een reëel getal te maken hebben, is het algoritme van Archimedes voor de benadering van , wat ook een van de oudste numerieke methoden is . [16]

Wiskunde in de 19e en 20e eeuw

De logici van de 19e eeuw deden belangrijk werk. George Boole , die de eerste algebraïsche logische calculus creëerde in zijn werk The Mathematical Analysis of Logic , was de grondlegger van de moderne wiskundige logica, die verschilt van de traditionele filosofische logica door consistente formalisering. [17] Gottlob Frege was de eerste die een formele taal ontwikkelde en het resulterende formele bewijs . [18] Giuseppe Peano reduceerde rekenkunde tot een reeks symbolen die door symbolen werden gemanipuleerd. Hij hield zich bezig met de axiomatiek van natuurlijke getallen. Hier kwamen de axioma's van Peano naar voren . [19]

Het werk van Frege werd sterk uitgewerkt en vereenvoudigd door Alfred North Whitehead en Bertrand Russell in hun Principia Mathematica . [20] Eerder formuleerde Bertrand Russell de beroemde Russell-antinomie , die leidde tot de ineenstorting van de naïeve verzamelingenleer . Het resultaat leidde ook tot het werk van Kurt Gödel .

David Hilbert formuleerde het beslissingsprobleem precies in zijn onderzoeksprogramma rond 1928. [21] Alan Turing en Alonzo Church vonden het probleem in 1936 onoplosbaar. [22]

literatuur

web links

WikiWoordenboek: algoritme - uitleg van betekenissen, woordoorsprong, synoniemen, vertalingen

voetnoten

  1. ^ Hartley Rogers, Jr.: Theorie van recursieve functies en effectieve berekenbaarheid , blz. 2.
  2. ^ Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Algoritmen - een inleiding . Oldenbourg Verlag, München 2010, ISBN 978-3-486-59002-9 , pp.   5 .
  3. Hromkovič, Juraj, 1958: Theoretische Informatica, Formele talen, berekenbaarheid, Complexity Theory, algoritmen, Communication and Cryptography / Juraj Hromkovič. 5e, herzien. Editie. Springer Vieweg, Wiesbaden 2014, ISBN 978-3-658-06432-7 .
  4. Sequentiële abstracte toestandsmachine (seq. ASM) .
  5. Duitsland: § 69a Paragraaf (2) UrhG.
  6. ^ Clifford A. Pickover: The Math Book: Van Pythagoras tot de 57e dimensie, 250 mijlpalen in de geschiedenis van de wiskunde . Sterling Publishing Company, Inc., 2009, ISBN 978-1-4027-5796-9 ( beperkte preview in Zoeken naar boeken met Google).
  7. MHMC.htm. Ontvangen op 26 mei 2018 .
  8. ^ Al-Khwarizmi Perzische wiskundige, astronoom en geograaf deel één: Perzisch erfgoed. Ontvangen op 26 mei 2018 .
  9. http://www.andyborne.com/math/downloads/AL-Kwarazmi.pdf .
  10. Brahmagupta biografie .
  11. ^ Geschiedenis van algoritmen en algoritmen. In: Scriptol.com. Ontvangen 7 november 2012 .
  12. Mohammed ibn-Musa al-Hwārizmī: De oudste Latijnse schrift op de Indiase rekenkunde volgens al-Ḫwārizmī. Red.: Menso Folkerts, Paul Kunitzsch. Uitgeverij van de Beierse Academie van Wetenschappen, München 1997.
  13. ^ Kurt Vogel : Der Trienter Algorismus von 1475. In: Nova Acta Leopoldina , New Series, Volume 27, 1963, blz. 183-200.
  14. ^ Roger L. Cooke: De geschiedenis van de wiskunde: een korte cursus , Wiley 2005, blz. 166.
  15. http://aleph0.clarku.edu/~djoyce/elements/bookVII/propVII2.html
  16. http://itech.fgcu.edu/faculty/clindsey/mhf4404/archimedes/archimedes.html .
  17. Project Gutenberg's The Mathematical Analysis of Logic, by George Boole .
  18. Gottlob Frege – Eine Einführung in sein Werk ( PDF )
  19. Peano: Arithmetices principia nova methodo exposita , Turin 1889.
  20. http://name.umdl.umich.edu/AAT3201.0001.001 Principia Mathematica. 1. Auflage. 1910–1913, in der Onlineversion der University of Michigan.
  21. Tapp, Christian: An den Grenzen des Endlichen. Das Hilbertprogramm im Kontext von Formalismus und Finitismus. Springer, Heidelberg 2013, ISBN 978-3-642-29654-3 .
  22. cf. footnote in Alonzo Church 1936a in Davis 1965:90 and 1936b in Davis 1965:110.
  23. Dagmar Röhrlich : Die neue Weltmacht. In: Deutschlandfunk.de , Wissenschaft im Brennpunkt , 20. März 2016, abgerufen am 28. März 2016.