Jag ska ge samma svar som jag gav förra gången denna fråga kom upp.

Förstå först att det inte finns någon bra formell definition av ”algoritm” i skrivande stund. Nyckelordet här är ”formellt”.

Det finns dock smarta människor som arbetar med det.

Vad vi vet är att vad en ”algoritm” är, den sitter någonstans mellan ”matematisk funktion” och ”datorprogram”.

En matematisk funktion är formell uppfattning om en mappning från ingångar till utgångar. Så, till exempel, är ”sortera” en kartläggning mellan en sekvens av beställbara artiklar och en sekvens av beställningsbara artiklar av samma typ, som mappar varje sekvens till sin ordnade sekvens. Denna funktion kan implementeras med hjälp av olika algoritmer (t.ex. sammanslagningssortering, högsortering). Varje algoritm kan i sin tur vara implementeras med hjälp av olika program (till och med givet samma programmeringsspråk).

Så det bästa greppet vi har om vad en ”algoritm” är, är att det är någon form av ekvivalensklass på program, där två program är likvärdiga om de gör ”i huvudsak samma sak”. Alla två program som implementerar samma algoritm måste beräkna samma funktion, men det motsatta är inte sant.

På samma sätt finns det en ekvivalensklass mellan algoritmer, där två algoritmer är ekvivalenta om de beräknar samma matematiska funktion .

Den svåra delen av allt detta är att försöka fånga vad vi menar med ”i princip samma sak”.

Det finns några uppenbara saker som vi bör inkludera. Till exempel är två program i huvudsak desamma om de bara skiljer sig åt med variabla namnändringar. De flesta modeller av programmeringsspråk har ursprungliga begrepp om ”ekvivalens” (t.ex. beta-reduktion och eta-omvandling i lambdakalkyl), så vi borde också kasta dem. . Algoritmer bildar en kategori på grund av att de är kvotkategorin för program. Några intressanta ekvivalensförhållanden är kända för att ge upphov till intressanta kategoristrukturer; till exempel är kategorin primitiva rekursiva algoritmer ett universellt objekt i kategorikategorin. När du ser en intressant struktur så vet du att denna förfrågan kommer att vara användbar.

Kommentarer

• Tack för ditt exakta svar, bara en annan fråga. Om vi överväger något program, oavsett vad det gör, får de fortfarande några ingångar och följer några instruktioner och ger några resultat när de körs. De kanske till och med inte ’ löser något problem (som vi kallar), men det är fortfarande en kartläggning. kan de vara kända algoritmer, menar jag något program?
• Om jag ’ läser dig korrekt, så ’ frågar om en formell definition av en ” -algoritm ” bör eller inte bör ha det förbehållet att den måste vara ” användbart ”. Jag skulle säga ” nej ”, om bara för att det ’ är omöjligt att formalisera det uppfattning.
• ledsen! min engelska är inte bra, då säger du ” nej ” till vad? du erkänner att det ’ är omöjligt att formalisera nyttan av ett program, och bara per definition är något program en algoritm? eller säger du det ’ är nödvändigt att vi anser nytta bredvid algoritmen?
• Jag tror inte ’ att en formell definition av en ” -algoritm ” bör kräva att det är användbart, eftersom ” användbart ” kan ’ definieras inte formellt.
• Ditt svar är det mest användbara i denna tråd +1. Jag tror att ” i princip samma sak ” menar du ” semantiskt ekvivalent ”. Jag tror också att alla program i huvudsak är algoritmer (som OP säger), eftersom alla program är implementeringar som kartlägger en del input till viss output, även om den här kartläggningen är implicit. Som du sade beror allt på perspektivet.

I slutändan är skillnaden perspektiv . Ett program är ett program: en sekvens av uttalanden på något språk, kanske ett programmeringsspråk eller instruktioner på maskinnivå. Algoritmer beskrivs vanligtvis på en högre nivå än maskininstruktioner eller programmeringsspråk, men hur hög en nivå är ganska flexibel. Under vissa omständigheter är ”Sortera matrisen, titta sedan på $ k $ th-elementet” en perfekt bra beskrivning av en algoritm för att hitta $ k $ th största objekt i en matris; under andra omständigheter kanske du vill specificera mycket mer detaljerad om hur sorteringen sker.

Som du säger är en algoritm ungefär som ”en process eller en uppsättning regler som ska följas vid beräkningar eller andra problem -lösningsåtgärder, särskilt av en dator. ” Så, bokstavligen sett, är varje program en algoritm. Vanligtvis talar vi dock om program som implementerar algoritmer. När vi beskriver en algoritm undviker vi vanligtvis den låga detaljnivån om exakt hur saker implementeras, förutsatt att en kompetent programmerare skulle kunna implementera den i det språk de väljer.

Kommentarer

• Jag tror att den exakta algoritmen är relaterad till matematikkoncept, lambda-calculus eller Turing-maskin, men vet fortfarande inte ’ vad är det abstraktionsspråk? matematik eller ett naturligt språk med många suddiga uttalanden
• @Ahmad Algoritm är ett informellt begrepp. Den har ingen formell definition. På sätt och vis är det ’ som ett matematiskt bevis, vilket skiljer sig från ett formellt bevis i ett formellt bevissystem. Vi tror att informella bevis kan ” utarbetas ” till formella bevis i valfritt (tillräckligt starkt) formellt bevissystem, precis som alla algoritm kan implementeras fullständigt i vilket programmeringsspråk som helst (Turing-komplett).

Algoritmer i Turing -komplett tänkesätt specificeras vanligtvis av in- och utdata. Verkliga program gör mer; de

• kommunicerar med användaren,
• kommunicerar med andra maskiner,
• reagerar på miljön,
• avslutas inte och är fortfarande användbara,

och mer. Dessa saker beaktas vanligtvis inte i algoritmer eller beräkningsteori, men är väsentliga för de flesta program.

Kommentarer

• Detta är en mycket bra poäng. Men menar du något som ” vanligtvis anges som ett medel för att mappa inmatning till utdata ”? Att bara specificera ingången och utgången är ’ inte tillräckligt: t.ex., sammanslagningssort och snabbsort producerar samma utdata från alla ingångar men betraktas inte ’ för att vara samma algoritm.
• @ DavidRicherby Jag tänkte på specifikation i PL-mening; vi anger ’ inget annat, så algoritmer kanske inte gör något annat. Självklart måste vi ge mer än specifikationen för att beskriva en konkret algoritm.
• Bra poäng, men om vi erkänner att i slutändan är något program en algoritm, donerar jag inte ’ vet inte hur de frågor du behandlat mäts om en algoritm. Kanske ett AI-ämne ?!
• Vem skulle erkänna det och varför? Och vad menar du med mått här? (Och jag ser verkligen inte ’ AI-vinkeln här.)
• @Raphael Jag kan erkänna det (genom att titta på syntaksen ser alla program ut, de är sekvenser av instruktioner eller kartläggning av input to output), jag vet bara inte ’ hur andra funktioner i ett program (de du adresserade) kan extraheras från den definitionen. till exempel skillnaden mellan snabbsortering och MATLAB eller Windows Media Player !!

• En algoritm är ett systematiskt tillvägagångssätt för att lösa ett specifikt problem.

• Ett program är en uppsättning instruktioner som en dator ska följa.

Ett program behöver därför inte ens lösa ett problem.Jag är säker på att vi alla kan tänka på flera program som har orsakat fler problem än de har löst. Ett program kan vara en implementering av många algoritmer, eller en algoritm kan implementeras genom att lappa ihop många program. Ett program kan till och med inte innehålla algoritmer. Till exempel kan det tomma programmet som helt enkelt avslutas, eller kanske till och med en Hello World, betraktas som ett program utan algoritm.

Eftersom en algoritm löser ett specifikt problem är det fokuserat på ett specifikt helkoncept. En algoritm tillhandahåller därför abstrakta steg för att bearbeta en uppsättning relaterad information till en annan uppsättning härledd information. Ett program kräver inte att dess beståndsdelar alls är begreppsmässigt relaterade. Till exempel kan ett program ha ett påskägg, men en sak som kallas en algoritm borde inte. Du kan ha ett virus eller trojan som lurar i ett program, men inte i en algoritm. Det närmaste en algoritm kan komma detta skulle vara ungefär som en bakdörr i en krypteringsalgoritm, där den planerade bristen är en del av informationsförhållandet som fastställts av algoritmen.

Och slutligen, ett program som det är kort för ett datorprogram, kräver tautologiskt en dator. En algoritm gör det inte. Om jag systematiskt separerar skjortor, byxor och strumpor från min tvätt innan jag lägger bort dem är detta en algoritm. Den behandlar relaterade in- och utgångar, kan beskrivas i ett flödesschema och har beräkningsbara konsekvenser när det gäller effektivitet (till exempel antalet klädesplagg som måste jämföras för att hitta matchande strumpor).

En algoritm är ett koncept eller en idé. Det är en formell metod för att lösa ett problem. Algoritmer kan uttryckas eller implementeras på en mängd olika programmeringsspråk (vanligtvis kan nästan vilket språk som helst implementera vilken algoritm som helst). För några exempel bör du läsa igenom Sorteringsalgoritmer i Wikipedia.

Ett datorprogram är en specifik instruktionssekvens i ett specifikt programmeringsspråk. . Ett program kan innehålla implementeringen av många algoritmer. Excel är ett program, men det är sorteringsfunktioner som är en manifestation av en algoritm.

En algoritm är en fristående steg för steg uppsättning operationer som ska utföras för att lösa ett specifikt problem eller en klass av problem.

Ett datorprogram är en sekvens av instruktioner som följer reglerna för ett specifikt programmeringsspråk, skrivna för att utföra en viss uppgift med en dator.

Algoritmer är allmänna och måste översättas till en specifikt programmeringsspråk (implementerat).

Kommentarer

• Men hela poängen med frågan är att ett program (antingen dess källkod eller den kompilerade binära ) är ” en fristående steg för steg uppsättning operationer som ska utföras för att lösa ett specifikt problem eller en klass av problem. ”
• Men det är inte ’ t. Ett program är inte det Använd operationer, men en implementering av dem: något som utför dem i ett visst sammanhang. T.ex. Unix sort -verktyget är inte en sorteringsalgoritm, det använder en sorteringsalgoritm.

En algoritm uttrycker vår idé eller lösning för specifika problem steg för steg. det är bara problemlösning och mänskligt förståeligt tillvägagångssätt, inte för datorsystem

Programmet är steg för steg instruktioner som implementeras för att lösa problem med datorsystem. det måste vara förståeligt för inte bara programmeraren också datorn.

Kommentarer

• Välkommen till Stack Science Exchange. Läs cs.stackexchange.com/tour.if du har ännu inte gjort det.

De andra svaren här, tror jag, saknar en viktig punkt. Definitionen av ”algoritm” som jag lärde mig inkluderade kravet att proceduren stoppas på alla ingångar . Naturligtvis gör det ”program” till en bredare klass av procedurer än ”algoritm”, eftersom vissa program stannar vid alla ingångar och andra inte.

Kommentarer

• Detta är inte universellt. Definitionen som jag lärde mig inkluderade inte ’ det kravet.

Här är ett par sätt att dra gränsen mellan en algoritm och ett program:

Meningsfullt syfte

Program skrivs med ett syfte och representerar ett försök att uppnå en mål. Algoritmer kan ses som verktyg för att uppnå det målet.

Exempelvis en skruvmejsel är en algoritm för att ändra tillståndet hos en skruv men skruvmejseln själv har inte ett syfte att göra det.Syftet är i huvudet på skruvmejseloperatören som håller programmet som att sätta upp hyllor.

Affärslogik

Denna punkt hänför sig starkt till syftet med ett program. Eftersom program har syften har de oundvikligen bitar av verklig värld i sig som specifika datum, mätningar, tekniker, namn etc.

Algoritmer å andra sidan innehåller varken affärslogik eller bitar av verkliga världen och istället för att arbeta på specifika värden fungerar på variabler.

t.ex. i den meningen kan du jämföra en matematisk funktion som f(x) = x^2 som är abstrakt och fungerar på variabler till ett matlagningsrecept som innehåller exakta värden (minst en för referens).

Resultat

Denna punkt hänför sig starkt till programmets affärslogik. En agent (som en webbläsaranvändare) förbrukar resultatet av ett program, inte resultatet av en algoritm.

Exempelvis konsumenten av ett matlagningsrecept konsumerar kakan, inte resultatet av vispgrädde eller ugn.

Kommentarer

• Det kanske är bättre att säga att Skruvmejseln har inte ’ inte avsikten att vrida skruvarna? På vardagsspråket skulle vi säkert säga att en skruvmejsel har syftet att vrida skruvar: att vrida skruvar är exakt det som det var designat att göra.
• Jag ’ jag är inte säker på vad du menar med ” affärslogik ” (många program har inget att göra med företag) eller genom att säga att en algoritm ” varken innehåller affärslogik eller bitar från den verkliga världen ”. Till exempel kunde jag mycket väl formulera en kortaste algoritm när det gäller städer och vägar snarare än hörn och kanter. Innehåller ’ algoritmen då ” … bitar av den verkliga världen ” ?
• @ DavidRicherby, du har rätt, min formulering är tvetydig. Vad jag menade är ett meningsfullt syfte. Att vrida skruvar för att vrida skruvar är meningslöst lika bra som att sortera en matris som aldrig används. Med affärslogik menar jag all programlogik förutom verktygslogik och teknik stack panna, dvs. all logik som faktiskt implementerar syftet med programmet, dvs. affärslogiken med att baka en kaka är att blanda ingredienser och baka och inkluderar inte att lära sig att blanda eller baka ( som återanvänds logik i detta fall).
• @DavidRicherby, som för bitar av verklig värld , menar jag aktualisering dvs att ett program till skillnad från en algoritm måste kommunicera på något sätt med den fysiska världen. En algoritm kan å andra sidan vara ett rent matematiskt begrepp.

I är ganska säker på att andra svar är tillräckligt bra för att ta ledningen men här ser jag skillnaden mellan en algoritm och ett program

• En algoritm består helt enkelt av de steg (maskinoberoende) som krävs för att lösa ett problem.

• Ett program är en instruktionsuppsättning för en specifik typ av maskin för att utöva en algoritm .

Till exempel.

Låt oss säga att du har en algoritm som har ett steg för nå till en viss plats innan du gör något annat steg. Nu hur detta steg för att nås är inte exakt definierat. Du kan välja att gå eller springa eller ta en buss för att göra det men det beror på hur du väljer att genomföra det (vilket är ditt prog ram).

Du kan säga att en algoritm är en abstraktion av ett program, dvs. saknar exakta detaljer men lägger ut en plan för att göra något .