Bästa svaret
Det finns inget svar på detta.
Låt oss hitta svar på detta problemuttalande:
F. Hur hittar jag någon algoritm som fungerar bättre?
A. Vanligaste sätten att jämföra algoritmer:
1) Tidskomplexitet
2) Rymdkomplexitet
3) Lösningskvalitet (kanske inte vara tillämplig om den föreslår att exakt lösa ett problem). Den här kan vara en stor faktor om vi pratar om approximationsalgoritmer.
4) Enkel implementering / anpassning av algoritmen. Vissa algoritmer kan ha mycket overhead att implementera korrekt. Det finns ibland mer lämpliga algoritmer för din applikation. Till exempel i parallell beräkning kommer de flesta att hitta Bellman-Ford mer användbar än Dijkstras algoritm på grund av hur Bellman-Ford fungerar.
Men tid och komplexitet är inte * alltid * önskvärd funktion att maximera; Jag kommer att ge två exempel.
Det ena är ”numerisk stabilitet” , en funktion av algoritmer i både linjär algebra och i differentialekvationer. Vi kommer att spendera både mer algoritmisk tid och mer algoritmisk komplexitet på algoritmer som är mer numeriskt stabila. I linjär algebra orsakas instabilitet i allmänhet när en algoritm stöter på siffror som är för nära noll eller oändlighet eller båda, på grund av den slutliga representationen av tal kan upplösningen gå förlorad. I allmänhet orsakar detta väldigt lite olika siffror, bara ett fåtal epsiloner som skiljer sig från varandra (där epsilon är det minsta antalet som kan läggas till en, på en maskin och får ett resultat! = 1), för att producera stora skillnader i svaret. Så till exempel spenderar vi mycket tid och rymdkomplexitet genom att ”svänga” i LU-faktoriseringen för att få en stabil algoritm; utan att svänga är LU inte stabil. På samma sätt har vi algoritmer som inte gör annat än att ”konditionera” matriser för att undvika instabilitet.
Ett andra exempel är ”robusthet” i dess tekniska statistiska betydelse. Robusthet betyder ett mått eller en algoritm som * inte * är känslig för avvikare. Så till exempel, när jag passar en minsta kvadratlinje till en uppsättning punkter, kan linjen snedställas kraftigt med ett enda extremt stort värde. Även om jag har 99 par siffror som bildar en perfekt 45 graders linje, om jag lägger till ett enda avvikande par för vilket Y-värdet är hundra gånger vad det ”borde” vara att falla på samma linje, kommer den monterade linjen att skev från 45 graders linjen. Algoritmen kommer att ”ge upp” den perfekta passformen för 99 poäng för att bättre representera den avgörande punkten. Det är * inte * robust.
En robust strategi med minst kvadrat är istället för att hitta linjen som minimerar summan av kvadratfel som skapats genom att använda den linjen, att hitta linjen som minimerar * medianen av de kvadratfel som skapats med den raden. I exemplet är den linjen 45-graderslinjen, och medianen av de kvadrerade felen är noll, och outlier-punkten (och faktiskt upp till 98 galna outliers) skulle ignoreras helt. Linjen med 45 grader skulle hittas.
Liknande robusta algoritmer finns för att anpassa statistiska kurvor, hitta former etc. De är dock dyra i tid, ibland allvarligt. Men tidskostnaden är värt det eftersom robust statistik effektivt är immun mot ”buller” i signaler, där minst kvadratiska felmetoder inte är. Den verkliga världen är full av både buller och outliers, några av dem orsakade av mänskliga eller maskinfel, särskilt i pixelbilder eller samplat ljud. Under sådana omständigheter kan en mer kostnadskrävande robust algoritm hitta signaler i en bullrig miljö där snabbare algoritmer ger svar som är så skadade av brus att de är värdelösa eller till och med farliga om de accepteras.
I vissa fall är tiden och rymdkomplexitet är inte alls lika viktigt som att hitta ett svar som mest sannolikt kommer att modellera den verkliga signalen trots brus och nedbrytning av signalen.
Svar
Algoritmer har sitt ursprung i matematiken som ”recept” för att utföra funktionsbaserad beräkning, som kan följas mekaniskt. I den funktionsbaserade matematiska världsbilden måste alla ingångar specificeras i början av beräkningen, som fortsätter på ett slutet sätt. Begreppet en algoritm är i sig informellt, eftersom en algoritmisk beskrivning inte är begränsad till ett enda språk eller formalism.
Det kanske äldsta exemplet är Euclids algoritm för att hitta gemensamma delare. Algoritmer fångar vad det betyder för en beräkning att vara ”effektiv”. Precis som matematiska formler berättar algoritmer hur vi beräknar ett värde; till skillnad från dem kan algoritmer involvera det vi nu kallar slingor eller grenar.
Algoritmens roll: Med tanke på något begränsat ingångsvärde x, beskriver en algoritm stegen för att effektivt omvandla det till ett utgångsvärde y, där y är f (x) för någon rekursiv funktion f.
Algoritmer antogs av de tidiga datavetenskaparna på 1950-talet, som skapade sambandet mellan algoritmer och Turing Machines (TMs, en formell beräkningsmodell från 1936), vilket motsvarar deras uttrycksförmåga.
Knuths berömda och inflytelserika lärobok, ”The Art of Computer Programming, Vol. 1” i slutet av 1960-talet populariserade centrala algoritmer inom datavetenskap. I sin definition av algoritmer överensstämde Knuth med de matematiska funktionsbaserade grunderna för beräkningsteorin. ”Det finns många andra väsentligen ekvivalenta sätt att formulera konceptet med en effektiv beräkningsmetod (till exempel med hjälp av TM: er).”
Knuth angav uttryckligen att algoritmer är stängda; ingen ny ingång accepteras när beräkningen har börjat: ”En algoritm har noll eller fler ingångar, dvs kvantiteter som ges till den initialt innan algoritmen börjar.” Han skilde algoritmer från godtycklig beräkning som kan involvera I / O. Ett exempel som han gav om ett problem som inte är algoritmiskt är följande instruktion från ett recept: ”kasta lätt tills blandningen är smulig.” Det här problemet är inte algoritmiskt eftersom det är omöjligt för en dator att veta hur länge man ska blanda; detta kan bero på externa dynamiskt förändrade förhållanden som fukt, som inte kan förutsägas med säkerhet i förväg.
Även om det inte finns någon överenskommelse om det exakta begreppet algoritmer, förblir Knuths diskussion om algoritmer definitiv.
Det första programmeringsspråket på hög nivå som utvecklades uttryckligen för att specificera algoritmer var ALGOL (ALGOrithmic Language). Det introducerades i slutet av 50-talet och förfinades genom 1960-talet och fungerade som en standard för publicering av algoritmer. I enlighet med den funktionsbaserade konceptualiseringen av algoritmer tillhandahöll ALGOL inga konstruktioner för in- och utdata, med tanke på dessa operationer utanför algoritmernas intresse. (Inte överraskande hindrade denna frånvaro branschens antagande av ALGOL för kommersiella applikationer.)
1960-talet såg en spridning av grundläggande datavetenskapsprogram (CS). Enligt Association for Computing Machinery (ACM) ökade antalet CS-program i USA från 11 år 1964 till 92 1968. Denna ökning åtföljdes av intensiv aktivitet för att skapa legitimiteten för denna nya disciplin i akademiens ögon gemenskap. ACM spelade en central roll i denna aktivitet. 1965 förklarade det rättfärdigandet och beskrivningen av CS som en disciplin, som fungerade som en grund för sina rekommendationer från 1968 för CS-program på grundnivå
ACM: s beskrivning av CS identifierade effektiv transformation av information som ett centralt problem: “ Datavetenskap handlar om information i ungefär samma bemärkelse som fysik handlar om energi … Datavetenskapsmannen är intresserad av att upptäcka de pragmatiska medel genom vilka information kan omvandlas. ” Denna beskrivning placerar algoritmer i centrum för datavetenskap, eftersom de är ”recept” för att utföra dessa effektiva omvandlingar av ingångar till utgångar. Faktum är att ACM gjorde detta fokus på algoritmer uttryckligt i nästa mening i sin rapport:
“Detta intresse leder till undersökning av effektiva sätt att representera information, effektiva algoritmer för att transformera information, effektiva språk att uttrycka algoritmer … och effektiva sätt att åstadkomma dessa till rimlig kostnad. ”
Att ha en central algoritmisk oro, som är analog med problemet med energi i fysik, hjälpte till att etablera CS som en legitim akademisk disciplin i nivå med fysik. Algoritmer har förblivit centrala i datavetenskap fram till i dag.
Samexistensen mellan det informella (algoritmbaserade) och de formella (TM-baserade) tillvägagångssätten för att definiera lösbara problem kvarstår fram till i dag och kan hittas i alla moderna läroböcker om algoritmer eller beräkningsbarhet. Detta har visat sig vara mycket bekvämt för datavetare genom att låta oss beskriva algoritmisk beräkning informellt med hjälp av ”pseudokod”, med vetskapen om att en motsvarande Turing Machine kan konstrueras.
– Ett problem är lösbart om det kan vara specificeras av en algoritm. – Ett problem kan lösas om det finns en Turing-maskin för den.
1960-talets beslut av teoretiker och lärare att placera algoritmer i centrum för CS återspeglades tydligt i tidiga grundböcker. Det fanns dock ingen uttrycklig standarddefinition av en algoritm och olika läroböcker valde att definiera denna term annorlunda. Medan vissa läroböcker som den av Knuth var noga med att uttryckligen begränsa algoritmer till de som beräknar funktioner och därför är likvärdiga med Turing Machines, lämnade de flesta teoriböcker denna begränsning underförstådd men osatt.
Ett tidigt exempel är ett lärobok av Hopcroft och Ullman från 1969, vars senare utgåvor används till denna dag: ”Ett förfarande är en ändlig sekvens av instruktioner som kan utföras mekaniskt, till exempel ett datorprogram …En procedur som alltid avslutas kallas en algoritm. ”
Denna beskrivning av algoritmer utesluter inte uttryckligen icke-funktionell beräkning som att laga mat. Deras exempel på olika problem gör det dock klart att de bara övervägde funktionsbaserad beräkning. I själva verket använde de ALGOL för sina exempel, som inte ens erbjöd några konstruktioner för inmatning och utdata. bunden av de algoritmiska begränsningarna av tidig ALGOL. Du kan skriva program som interagerade med sin miljö på ett kontinuerligt sätt under hela beräkningen, som operativsystem, grafiska användargränssnitt eller automatiska fordon och andra robotar.
Som svar, samtida programmeringsläroböcker som ris och Rice (1969) utvidgade uttrycket algoritmer uttryckligen till att inkludera icke-funktionella problem. Detta tillvägagångssätt, som återspeglar algoritmernas centrala läge utan att begränsa dem till beräkning av funktioner, blev typiskt för icke-teoriska läroböcker. Ämnet för dessa läroböcker är programmeringsmetodik snarare än beräkningsteorin, och de matematiska principerna som ligger till grund för våra beräkningsmodeller kastades åt sidan för att göra det praktiskt.
På ytan, definitionen av en algoritm i Rice and Rice och andra sådana läroböcker skiljer sig inte från Hopcroft och Ullman: ”En algoritm är ett recept, en uppsättning instruktioner eller specifikationerna för en process för att göra något. Att något vanligtvis löser ett slags problem. ” Deras exempel på beräknbara problem är dock inte längre funktionsbaserade, och erkänner bara den typ av beräkning som Knuth avvisade. Två sådana exempel, som förmodligen kan lösas med en algoritm, är att göra potatisvodka och fylla ett dike med sand; Knuth skulle ha avvisat dem båda.
Dessa läroböcker gjorde inga påståenden om TM-ekvivalens för deras ”algoritmer”. Studenterna blev dock inte medvetna om att denna uppfattning om algoritmer skiljer sig från Knuth, och att den uppsättning problem som anses beräknbara därmed hade utvidgats. Genom att para ihop en bredare, mer praktisk, konceptualisering av algoritmer (och därmed beräkningsbara problem) med teorier som hävdar att mycket beräknbara problem kan beräknas av TM: er, lämnade den algoritmfokuserade CS-läroplanen eleverna det felaktiga intrycket att denna bredare uppsättning problem skulle kunna kan även lösas av TM: er.
Även om de praktiska datavetenskapsmännen för länge sedan har följt ris och ris och utvidgat konceptet med algoritmer bortom beräkningen av funktioner, har teoretisk datavetenskap behållit den matematiska världsbilden som ramar in beräkning som funktionsbaserad och avgränsar vår uppfattning om ett beräkningsproblem i enlighet därmed. Detta gäller åtminstone på grundnivå. Resultatet är en dikotomi, där datavetenskapssamhället tänker på algoritmer som synonyma med det allmänna begreppet beräkning (”vad datorer gör”) samtidigt som de är likvärdiga med Turing Machines.
Jag tänkte Jag var tvungen att skriva detta långa svar för att göra människor medvetna om denna dikotomi. Som jag sa i början är begreppet en algoritm informellt. Vi kan tänka på det som likvärdigt med beräkningen av funktioner (eller Turing Machines) eller vi kan tänka på det som något du kan skriva ett program för, inklusive interaktiva program i realtid som operativsystem eller automatbilar. Men de två definitionerna är inte likvärdiga, trots den vanliga förvirringen mot det motsatta.