Beste antwoord
Hier is geen antwoord op.
Laten we een antwoord zoeken op deze probleemstelling:
Q. Hoe vind ik dat een algoritme beter presteert?
A. Meest voorkomende manieren om algoritmen te vergelijken:
1) Tijdscomplexiteit
2) Ruimtecomplexiteit
3) Kwaliteit van de oplossing (mogelijk niet van toepassing zijn als het voorstelt een probleem exact op te lossen). Deze kan een grote factor zijn als we het hebben over benaderingsalgoritmen.
4) Eenvoudige implementatie / aanpassing van algoritme. Sommige algoritmen kunnen veel overhead hebben om correct te implementeren. Er zijn soms meer geschikte algoritmen voor uw toepassing. Bij parallel computing zullen de meesten Bellman-Ford nuttiger vinden dan Dijkstras algoritme vanwege de manier waarop Bellman-Ford werkt.
Tijd en complexiteit zijn echter niet * altijd * de gewenste functie om te maximaliseren; Ik zal twee voorbeelden geven.
Een daarvan is “numerieke stabiliteit” , een kenmerk van algoritmen in zowel lineaire algebra als in differentiaalvergelijkingen. We zullen zowel meer algoritmische tijd als meer algoritmische complexiteit besteden aan algoritmen die numeriek stabieler zijn. In lineaire algebra wordt instabiliteit meestal veroorzaakt wanneer een algoritme getallen tegenkomt die te dicht bij nul of oneindig of beide liggen, omdat de eindige weergave van getallen de resolutie verloren kan gaan. In het algemeen veroorzaakt dit zeer licht verschillende getallen, slechts een paar epsilon die van elkaar verschillen (waarbij epsilon het kleinste getal is dat aan één kan worden toegevoegd, op een machine, en een resultaat krijgt! = 1), om grote verschillen in het antwoord. Zo besteden we bijvoorbeeld veel tijd en ruimte aan complexiteit door te “draaien” in de LU-factorisatie om een stabiel algoritme te krijgen; zonder draaien is LU niet stabiel. Evenzo hebben we algoritmen die niets anders doen dan “condition” -matrices om instabiliteit te voorkomen.
Een tweede voorbeeld is “robuustheid” in zijn technische statistische betekenis. Robuustheid betekent een maat of algoritme dat * niet * gevoelig is voor uitschieters. Dus als ik bijvoorbeeld een lijn met de kleinste kwadraten op een reeks punten pas, kan de lijn sterk scheef staan met een enkele extreem grote waarde. Zelfs als ik 99 getallenparen heb die een perfecte lijn van 45 graden vormen, als ik een enkel uitschieterpaar toevoeg waarvoor de Y-waarde honderd keer is wat het “zou moeten” zijn om op dezelfde lijn te vallen, zal de passende lijn ernstig zijn scheef van de 45 graden lijn. Het algoritme zal de perfecte pasvorm voor 99 punten “opgeven” om het ene uitbijterpunt beter weer te geven. Dat is * niet * robuust.
Een robuuste benadering van de kleinste kwadraten is, in plaats van de lijn te vinden die de som van de gekwadrateerde fouten minimaliseert die zijn gemaakt door die lijn te gebruiken, om de lijn te vinden die de * mediaan * van de gekwadrateerde fouten die zijn gemaakt door die regel te gebruiken. In het voorbeeld is die lijn de lijn van 45 graden, en de mediaan van de gekwadrateerde fouten is nul, en het uitbijterpunt (en inderdaad tot 98 meer gekke uitschieters) zou volledig worden genegeerd. De lijn van 45 graden zou worden gevonden.
Er bestaan vergelijkbare robuuste algoritmen voor het aanpassen van statistische curven, het vinden van vormen, enz. Ze zijn echter kostbaar in de tijd, soms zelfs ernstig. Maar de tijdskost is het waard omdat robuuste statistieken effectief immuun zijn voor “ruis” in signalen, waar benaderingen met kleinste kwadraten dat niet zijn. De echte wereld zit vol met zowel ruis als uitschieters, waarvan sommige worden veroorzaakt door menselijke of machinefouten, met name in gepixelde afbeeldingen of gesampled geluid. In dergelijke omstandigheden kan een meer tijdrovend robuust algoritme signalen vinden in een lawaaierige omgeving waar snellere algoritmen antwoorden produceren die zo beschadigd zijn door ruis dat ze nutteloos zijn, of zelfs gevaarlijk als ze worden geaccepteerd.
In sommige gevallen is de tijd nodig. en ruimtecomplexiteit zijn lang niet zo belangrijk als het vinden van een antwoord dat het meest waarschijnlijk het daadwerkelijke signaal modelleert ondanks ruis en verslechtering van het signaal.
Antwoord
Algoritmen zijn ontstaan in de wiskunde als recepten voor het uitvoeren van op functies gebaseerde berekeningen, die mechanisch kunnen worden gevolgd. In het op functies gebaseerde wiskundige wereldbeeld moeten alle invoer worden gespecificeerd aan het begin van de berekening, die verloopt in een gesloten doos. De notie van een algoritme is inherent informeel, aangezien een algoritmische beschrijving niet beperkt is tot een enkele taal of formalisme.
Misschien is het oudste voorbeeld het algoritme van Euclides voor het vinden van gemeenschappelijke delers. Algoritmen leggen vast wat het betekent dat een berekening “effectief” is. Net als wiskundige formules, vertellen algoritmen ons hoe we een waarde moeten berekenen; in tegenstelling tot hen, kunnen algoritmen betrekking hebben op wat we nu loops of branches noemen.
Rol van algoritme: gegeven een eindige invoerwaarde x, beschrijft een algoritme de stappen voor het effectief transformeren naar een uitvoerwaarde y, waarbij y is f (x) voor een recursieve functie f.
Algoritmen werden in de jaren vijftig overgenomen door de vroege computerwetenschappers, die de verbinding legden tussen algoritmen en Turing Machines (TMs, een formeel rekenmodel uit 1936), waarmee ze hun expressiviteit gelijkstellen.
Knuths beroemde en invloedrijke leerboek, “The Art of Computer Programming, Vol. 1” aan het eind van de jaren zestig maakte de centrale plaats van algoritmen in de informatica populair. In zijn definitie van algoritmen was Knuth consistent met de op wiskundige functies gebaseerde grondslagen van de berekeningen. “Er zijn vele andere in wezen gelijkwaardige manieren om het concept van een effectieve computationele methode te formuleren (bijvoorbeeld door TMs te gebruiken).”
Knuth specificeerde expliciet dat algoritmen gesloten zijn; er wordt geen nieuwe invoer geaccepteerd zodra de berekening is begonnen: “Een algoritme heeft nul of meer invoer, d.w.z. hoeveelheden die er aanvankelijk aan worden gegeven voordat het algoritme begint.” Hij onderscheidde algoritmen van willekeurige berekeningen waarbij I / O betrokken kan zijn. Een voorbeeld dat hij gaf van een probleem dat niet algoritmisch is, is de volgende instructie uit een recept: “lichtjes schudden tot het mengsel kruimelig is.” Dit probleem is niet algoritmisch omdat het voor een computer onmogelijk is om te weten hoelang hij moet mixen; dit kan afhankelijk zijn van externe dynamisch veranderende omstandigheden zoals vochtigheid, die niet van tevoren met zekerheid kunnen worden voorspeld.
Hoewel er geen overeenstemming is over de exacte notie van algoritmen, blijft Knuths bespreking van algoritmen definitief.
De eerste programmeertaal op hoog niveau die speciaal werd ontwikkeld om algoritmen te specificeren, was ALGOL (ALGOrithmic Language). Geïntroduceerd in de late jaren 50 en verfijnd in de jaren 60, diende het als een standaard voor de publicatie van algoritmen. Trouw aan de op functies gebaseerde conceptualisering van algoritmen, leverde ALGOL geen constructies voor invoer en uitvoer, aangezien deze bewerkingen buiten de zorg van algoritmen vallen. (Het is niet verrassend dat deze afwezigheid de acceptatie van ALGOL door de industrie voor commerciële toepassingen in de weg stond.)
In de jaren zestig was er een wildgroei aan undergraduate computer science (CS) -programmas. Volgens de Association for Computing Machinery (ACM) is het aantal CS-programmas in de VS toegenomen van 11 in 1964 tot 92 in 1968. Deze toename ging gepaard met intense activiteit om de legitimiteit van deze nieuwe discipline in de ogen van de academicus vast te stellen. gemeenschap. ACM speelde een centrale rol in deze activiteit. In 1965 verkondigde het de rechtvaardiging en beschrijving van CS als een discipline, die als basis diende voor zijn aanbevelingen uit 1968 voor niet-gegradueerde CS-programmas.
In de beschrijving van ACM van CS werd effectieve transformatie van informatie als een centraal punt van zorg genoemd: ” Informatica houdt zich in vrijwel dezelfde zin bezig met informatie als natuurkunde met energie … De computerwetenschapper is geïnteresseerd in het ontdekken van de pragmatische middelen waarmee informatie kan worden getransformeerd. ” Deze beschrijving plaatst algoritmen in het centrum van Computer Science, aangezien zij de “recepten” zijn voor het uitvoeren van deze effectieve transformaties van inputs naar outputs. In feite heeft ACM deze focus op algoritmen expliciet gemaakt in de volgende zin van hun rapport:
“Deze interesse leidt tot onderzoek naar effectieve manieren om informatie weer te geven, effectieve algoritmen om informatie te transformeren, effectieve talen waarmee algoritmen … en effectieve manieren om deze tegen redelijke kosten te bereiken. ”
Het hebben van een centrale zorg voor algoritmen, analoog aan de bezorgdheid over energie in de natuurkunde, hielp om CS te vestigen als een legitieme academische discipline die vergelijkbaar is met fysica. Algoritmen zijn tot op de dag van vandaag centraal gebleven in de informatica.
Het naast elkaar bestaan van de informele (op algoritmen gebaseerde) en de formele (op TM gebaseerde) benaderingen om oplosbare problemen te definiëren, blijft tot op de dag van vandaag bestaan en is te vinden in alle moderne leerboeken over algoritmen of berekenbaarheid. Dit is erg handig gebleken voor computerwetenschappers, door ons in staat te stellen algoritmische berekeningen informeel te beschrijven met behulp van “pseudocode”, in de wetenschap dat een gelijkwaardige Turing Machine kan worden geconstrueerd.
– Een probleem is oplosbaar als het kan worden gespecificeerd door een algoritme. – Een probleem is oplosbaar als er een Turing Machine voor bestaat.
De beslissing van de jaren zestig van theoretici en onderwijzers om algoritmen centraal te stellen in de informatica kwam duidelijk tot uiting in de vroege studieboeken voor niet-gegradueerden. Er was echter geen expliciete standaarddefinitie van een algoritme en verschillende studieboeken kozen ervoor om deze term anders te definiëren. Hoewel sommige leerboeken, zoals die van Knuth, zorgvuldig waren om algoritmen expliciet te beperken tot die welke functies berekenen en daarom gelijkwaardig zijn aan Turing Machines, lieten de meeste theorieboeken deze beperking impliciet maar niet vermeld.
Een vroeg voorbeeld is een leerboek van Hopcroft en Ullman uit 1969, waarvan de latere edities tot op de dag van vandaag worden gebruikt: “Een procedure is een eindige reeks instructies die mechanisch kunnen worden uitgevoerd, zoals een computerprogramma …Een procedure die altijd eindigt, wordt een algoritme genoemd. ”
Deze beschrijving van een algoritme sluit niet-functionele berekeningen zoals het bereiden van voedsel niet expliciet uit. Hun voorbeelden van verschillende problemen maken echter duidelijk dat ze alleen rekening hielden met op functies gebaseerde berekeningen. In feite gebruikten ze ALGOL voor hun voorbeelden, die zelfs geen constructies voor invoer en uitvoer boden.
Sinds eind jaren 60 waren de programmeertalen op hoog niveau die in de praktijk werden gebruikt en onderwezen in CS-programmas niet langer gebonden door de algoritmische beperkingen van het vroege ALGOL. Je zou programmas kunnen schrijven die tijdens de berekening op een continue manier interactie hadden met hun omgeving, zoals besturingssystemen, grafische gebruikersinterfaces of automatische voertuigen en andere robots.
Als reactie hierop zouden hedendaagse programmeerboeken zoals Rice en Rice (1969) verruimde expliciet het begrip algoritmen om niet-functionele problemen op te nemen. Deze benadering, die de centraliteit van algoritmen weerspiegelt zonder ze te beperken tot de berekening van functies, werd typerend voor niet-theoretische leerboeken. Het onderwerp van deze handboeken is de programmeermethodologie in plaats van de computertheorie, en de wiskundige principes die aan onze rekenmodellen ten grondslag liggen, werden ter wille van het praktische terzijde geschoven.
Aan de oppervlakte, de definitie van een algoritme in Rice and Rice en andere soortgelijke leerboeken verschilt niet van Hopcroft en Ullman: “Een algoritme is een recept, een reeks instructies of de specificaties van een proces om iets te doen. Dat iets lost meestal een of ander probleem op. ” Hun voorbeelden van berekenbare problemen zijn echter niet langer op functies gebaseerd, en geven precies het soort berekening toe dat Knuth had verworpen. Twee van die voorbeelden, die zogenaamd door een algoritme kunnen worden opgelost, zijn het maken van aardappelwodka en het vullen van een greppel met zand; Knuth zou ze allebei hebben afgewezen.
Deze leerboeken maakten geen aanspraak op TM-equivalentie voor hun “algoritmen”. De studenten werden zich er echter niet van bewust dat deze notie van algoritmen verschilt van die van Knuth, en dat de reeks problemen die als berekenbaar werden beschouwd, daardoor was vergroot. Door een bredere, meer praktische, conceptualisering van algoritmen (en dus van berekenbare problemen) te combineren met theorieën die beweren dat zeer berekenbare problemen kunnen worden berekend door topmanagers, gaf het algoritme-gerichte CS-curriculum studenten de verkeerde indruk dat deze bredere reeks problemen worden ook opgelost door TMs.
Terwijl de praktische computerwetenschappers al lang de leiding van Rice and Rice hebben gevolgd en het concept van algoritmen hebben verbreed buiten de berekening van functies, heeft de theoretische informatica het wiskundige wereldbeeld behouden dat berekening als functie-gebaseerd, en begrenst ons begrip van een rekenprobleem dienovereenkomstig. Dit geldt in ieder geval op het bachelorniveau. Het resultaat is een tweedeling, waarbij de computerwetenschappelijke gemeenschap algoritmen beschouwt als synoniem met het algemene begrip computergebruik (“wat computers doen”), maar tegelijkertijd als equivalent aan Turing Machines.
Ik dacht Ik moest dit lange antwoord schrijven om mensen bewust te maken van deze tweedeling. Zoals ik aan het begin al zei, is de notie van een algoritme informeel. We kunnen het beschouwen als equivalent aan de berekening van functies (of aan Turing Machines) of we kunnen het beschouwen als alles waarvoor je een programma kunt schrijven, inclusief real-time interactieve programmas zoals besturingssystemen of automatische autos. Maar de twee definities zijn niet gelijk, ondanks de algemene verwarring van het tegendeel.