Ik ga hetzelfde antwoord geven als de vorige keer dat deze vraag opkwam.

Begrijp allereerst dat er op het moment van schrijven geen goede formele definitie van “algoritme” bestaat. Het sleutelwoord hier is “formeel”.

Er zijn echter slimme mensen die eraan werken.

Wat we weten is dat wat een “algoritme” ook is, het ergens tussen “wiskundige functie” en “computerprogramma” zit.

Een wiskundige functie is formeel begrip van een afbeelding van invoer naar uitvoer. Zo is sorteren bijvoorbeeld een afbeelding tussen een reeks bestelbare items en een reeks bestelbare artikelen van hetzelfde type, die elke reeks toewijst aan de geordende volgorde. Deze functie zou worden geïmplementeerd met behulp van verschillende algoritmen (bijv. merge sort, heap sort). Elk algoritme zou op zijn beurt geïmplementeerd met verschillende programmas (zelfs met dezelfde programmeertaal).

Dus de beste manier die we hebben met wat een algoritme is, is dat het een soort equivalentieklasse is voor programmas, waarbij twee programmas zijn equivalent als ze “in wezen hetzelfde” doen. Twee programmas die hetzelfde algoritme implementeren, moeten dezelfde functie berekenen, maar het omgekeerde is niet waar.

Evenzo is er een equivalentieklasse tussen algoritmen, waarbij twee algoritmen equivalent zijn als ze dezelfde wiskundige functie berekenen .

Het moeilijkste bij dit alles is om te proberen vast te leggen wat we bedoelen met “in wezen hetzelfde”.

Er zijn enkele voor de hand liggende dingen die we zouden moeten opnemen. Twee programmas zijn bijvoorbeeld in wezen hetzelfde als ze alleen verschillen door variabele hernoemingen. De meeste modellen van programmeertalen hebben native noties van “equivalentie” (bijv. Bèta-reductie en eta-conversie in lambda-calculus), dus we zouden die ook moeten gebruiken.

Welke equivalentierelatie we ook kiezen, dit geeft ons enige structuur . Algoritmen vormen een categorie vanwege het feit dat ze de quotiëntcategorie van programmas zijn. Het is bekend dat enkele interessante equivalentierelaties aanleiding geven tot interessante categorische structuren; de categorie van primitieve recursieve algoritmen is bijvoorbeeld een universeel object in de categorie categorieën. Elke keer dat je een dergelijke interessante structuur ziet, weet je dat deze onderzoekslijn waarschijnlijk nuttig zal zijn.

Opmerkingen

• Bedankt voor je precieze antwoord, gewoon een andere vraag. Als we een programma overwegen, ongeacht wat het doet, krijgen ze nog steeds wat invoer en volgen ze enkele instructies, en geven ze enkele resultaten terwijl ze worden uitgevoerd. Ze kunnen zelfs ‘ geen enkel probleem oplossen (zoals we noemen), maar het is nog steeds een mapping. zouden ze een bekend algoritme kunnen zijn, ik bedoel elk programma?
• Als ik je ‘ m je correct lees, ‘ opnieuw vragen of een formele definitie van een ” algoritme ” wel of niet de voorwaarde moet bevatten dat het nuttig “. Ik zou ” nee ” zeggen, al was het maar omdat het ‘ s onmogelijk is om dat te formaliseren idee.
• sorry! mijn Engels is niet goed, dan zeg je ” nee ” waarop? je geeft toe dat het ‘ onmogelijk is om het nut van een programma te formaliseren, en dat elk programma per definitie een algoritme is? of je zegt dat het ‘ nodig is dat we naast het algoritme ook het nut beschouwen?
• Ik denk niet ‘ dat een formele definitie van een ” algoritme ” zou moeten vereisen dat het nuttig is, omdat ” nuttig ” kan ‘ t formeel worden gedefinieerd.
• Uw antwoord is het nuttigst in deze thread +1. Ik denk dat door ” in wezen hetzelfde “, je bedoelt ” semantisch equivalent “. Ik denk ook dat alle programmas in wezen algoritmen zijn (zoals OP zegt), aangezien alle programmas implementaties zijn die een bepaalde input aan een bepaalde output toewijzen, zelfs als deze mapping impliciet is. Zoals je zei, hangt het allemaal af van het perspectief.

Uiteindelijk is het verschil er een van perspectief . Een programma is een programma: een reeks uitspraken in een bepaalde taal, misschien een programmeertaal of instructies op machineniveau. Algoritmen worden meestal op een hoger niveau beschreven dan machine-instructies of programmeertaalverklaringen, maar hoe hoog een niveau is, is nogal flexibel. In sommige omstandigheden is bijvoorbeeld “Sorteer de array en kijk dan naar het $ k $ th element” een prima beschrijving van een algoritme voor het vinden van het $ k $ th grootste object in een array; in andere omstandigheden wilt u misschien veel meer details specificeren over hoe het sorteren plaatsvindt.

Zoals u zegt, is een algoritme zoiets als een proces of een reeks regels die moeten worden gevolgd in berekeningen of een ander probleem -oplossende operaties, vooral door een computer. ” Dus letterlijk gesproken is elk programma een algoritme. Meestal spreken we echter van programmas die algoritmen implementeren . Meestal vermijden we bij het beschrijven van een algoritme de details op laag niveau van hoe dingen precies worden geïmplementeerd, ervan uitgaande dat een bekwame programmeur het zou kunnen implementeren in de taal van hun keuze.

Opmerkingen

• Ik denk dat de precieze algoritme gerelateerd is aan het wiskundeconcept, lambda-calculus of Turing-machine, ‘ weet ik niet wat dat is abstractie taal? wiskunde of een natuurlijke taal met veel vage uitspraken
• @Ahmad Algorithm is een informeel concept. Het heeft geen formele definitie. In zekere zin is het ‘ een wiskundig bewijs, dat verschilt van een formeel bewijs in een formeel bewijssysteem. Wij zijn van mening dat informele bewijzen ” kunnen worden ingevuld ” tot formele bewijzen in elk gekozen (sterk genoeg) formeel bewijssysteem, net als elk ander algoritme kan volledig worden geïmplementeerd in elke (Turing-complete) programmeertaal.

Algoritmen in de Turing -complete mindset wordt meestal gespecificeerd door input en output. Echte programmas doen meer; zij

• communiceren met de gebruiker,
• communiceren met andere machines,
• reageren op de omgeving,
• beëindigen niet en zijn nog steeds nuttig,

en meer. Deze dingen worden meestal niet in algoritmen of berekeningen overwogen, maar zijn essentieel voor de meeste programmas.

Opmerkingen

• Dit is een heel goed punt. Maar bedoel je zoiets als “, meestal gespecificeerd als een middel om invoer toe te wijzen aan uitvoer “? Het specificeren van de invoer en uitvoer is niet ‘ t genoeg: mergesort en quicksort produceren bijvoorbeeld dezelfde uitvoer van elke invoer, maar worden ‘ niet beschouwd hetzelfde algoritme zijn.
• @DavidRicherby Ik dacht aan specificatie in de PL-zin; we specificeren geen ‘ iets anders, dus algoritmen mogen niets anders doen. Natuurlijk moeten we meer geven dan de specificatie om een concreet algoritme te beschrijven.
• Goede punten, maar als we toegeven dat elk programma uiteindelijk een algoritme is, dan ‘ weet niet hoe de zaken die je hebt aangepakt, gemeten worden over een algoritme. Misschien een AI-onderwerp ?!
• Wie zou dat toegeven, en waarom? En wat bedoel je hier met meten? (En ik ‘ zie hier zeker de AI-invalshoek niet.)
• @Raphael Ik geef het toe (door naar de syntaxis te kijken, zien alle programmas er hetzelfde uit, het zijn reeksen instructies, of mapping van input naar output), ik weet gewoon niet ‘ hoe andere features van een programma (die je hebt aangesproken) uit die definitie kunnen worden gehaald. bijvoorbeeld het verschil tussen quick-sort en MATLAB of Windows Media Player !!

• Een algoritme is een systematische benadering om een specifiek probleem op te lossen.

• Een programma is een reeks instructies die een computer moet volgen.

Een programma hoeft dus niet eens een probleem op te lossen.Ik weet zeker dat we allemaal verschillende programmas kunnen bedenken die meer problemen hebben veroorzaakt dan ze hebben opgelost. Een programma kan een implementatie zijn van veel algoritmen, of een algoritme kan worden geïmplementeerd door veel programmas aan elkaar te koppelen. Een programma kan zelfs geen algoritmen bevatten. Het lege programma dat eenvoudigweg wordt afgesloten, of misschien zelfs een Hallo Wereld, kan worden beschouwd als een programma zonder algoritme.

Aangezien een algoritme een specifiek probleem oplost, is het gericht op een specifiek geheel concept. Een algoritme biedt daarom abstracte stappen voor het verwerken van een set gerelateerde informatie in een andere set afgeleide informatie. Een programma vereist niet dat de onderdelen ervan conceptueel verwant zijn. Een programma kan bijvoorbeeld een paasei hebben, maar iets dat goed een algoritme wordt genoemd, zou dat niet moeten doen. Er kan een virus of trojan in een programma op de loer liggen, maar niet in een algoritme. Een algoritme kan hier het dichtst bij komen, zoiets als een achterdeur in een coderingsalgoritme, waar de geplande fout deel uitmaakt van de informatierelatie die door het algoritme tot stand is gebracht.

En tot slot, een programma zoals het is afkorting voor een computerprogramma, vereist tautologisch een computer. Een algoritme doet dat niet. Als ik de shirts, broeken en sokken systematisch van mijn wasgoed scheid voordat ik ze opberg, is dit een algoritme. Het behandelt gerelateerde inputs en outputs, kan worden beschreven in een stroomschema en heeft berekenbare consequenties in termen van efficiëntie (bijvoorbeeld het aantal kledingstukken dat moet worden vergeleken om bijpassende sokken te vinden).

Een algoritme is een concept of idee. Het is een formele benadering om een probleem op te lossen. Algoritmen kunnen worden uitgedrukt of geïmplementeerd in verschillende programmeertalen (meestal kan bijna elke taal elk algoritme implementeren). Voor sommige voorbeelden moet je de Sorting Algorithms in Wikipedia doorlezen.

Een computerprogramma is een specifieke reeks instructies in een specifieke programmeertaal . Een programma kan de implementatie van veel algoritmen bevatten. Excel is een programma, maar de sorteermogelijkheden zijn de manifestatie van een algoritme.

Een algoritme is een op zichzelf staande stapsgewijze reeks bewerkingen die moet worden uitgevoerd om een specifiek probleem of een klasse van problemen op te lossen.

Een computerprogramma is een reeks van instructies die voldoen aan de regels van een specifieke programmeertaal, geschreven om een specifieke taak uit te voeren met een computer.

Algoritmen zijn algemeen en moeten worden vertaald in een specifieke programmeertaal (geïmplementeerd).

Opmerkingen

• Maar het punt van de vraag is dat een programma (ofwel de broncode of het gecompileerde binaire bestand) ) is ” een op zichzelf staande stapsgewijze reeks bewerkingen die moeten worden uitgevoerd om een specifiek probleem of een specifieke probleemklasse op te lossen. ”
• Maar het is niet ‘ t. Een programma is niet het ose operaties, maar een implementatie ervan: iets dat ze uitvoert in een bepaalde context. Bijv. het Unix sort hulpprogramma is geen sorteeralgoritme, het gebruikt een sorteeralgoritme.

Een algoritme drukt ons idee of onze oplossing voor een specifiek probleem uit in een stapsgewijze benadering. het is alleen het oplossen van problemen en een voor mensen begrijpelijke benadering, niet voor computersystemen

Programma is stapsgewijze instructies die geïmplementeerd zijn voor het oplossen van problemen door een computersysteem. Het moet begrijpelijk zijn, niet alleen door de programmeur, maar ook door de computer.

Reacties

• Welkom bij Computer Science Stack Exchange. Lees cs.stackexchange.com/tour.if als je dit nog niet hebt gedaan.

De andere antwoorden hier, denk ik, missen een belangrijk punt. De definitie van “algoritme” die mij werd geleerd, omvatte de vereiste dat de procedure stopt op alle invoer . Dat maakt natuurlijk “programma” een bredere klasse van procedures dan “algoritme”, aangezien sommige programmas op alle invoer stoppen en andere niet.

Opmerkingen

• Dit is niet universeel. De definitie die mij werd geleerd, bevatte niet ‘ die vereiste.

Hier zijn een paar manieren om de grens te trekken tussen een algoritme en een programma:

Betekenisvol doel

Programmas zijn geschreven met een doel en vertegenwoordigen een poging om een doel. Algoritmen kunnen worden gezien als hulpmiddelen om dat doel te bereiken.

Bijv. een schroevendraaier is een algoritme om de toestand van een schroef te wijzigen, maar de schroevendraaier zelf heeft daar geen doel voor.Het doel zit in het hoofd van de schroevendraaieroperator die het programma vasthoudt zoals het ophangen van planken.

Bedrijfslogica

Dit punt heeft sterk betrekking op het doel van een programma. Omdat programmas doelen hebben, bevatten ze onvermijdelijk stukjes echte wereld, zoals specifieke datums, metingen, technologieën, namen enz.

Algoritmen bevatten daarentegen geen bedrijfslogica of stukjes echte wereld en in plaats van te werken op specifieke waarden werken op variabelen.

Bijv. in die zin kun je een wiskundige functie zoals f(x) = x^2, die abstract is en op variabelen werkt, vergelijken met een kookrecept dat precieze waarden bevat (tenminste één ter referentie).

Resultaat

Dit punt heeft sterk betrekking op de bedrijfslogica van een programma. Een agent (zoals een webbrowsergebruiker) verbruikt het resultaat van een programma en niet het resultaat van een algoritme.

Bijv. de consument van een kookrecept consumeert de cake niet het resultaat van slagroom of het opwarmen van de oven.

Opmerkingen

• Misschien is het beter om dat te zeggen de schroevendraaier niet ‘ de bedoeling heeft om schroeven te draaien? In alledaags Engels zouden we zeker zeggen dat een schroevendraaier wel het doel heeft om schroeven te draaien: schroeven draaien is precies waarvoor hij is ontworpen.
• Ook, I ‘ m niet zeker wat u bedoelt met ” bedrijfslogica ” (veel programmas hebben niets te doen met zaken) of door te zeggen dat een algoritme ” geen bedrijfslogica of bits van de echte wereld bevat “. Ik zou bijvoorbeeld heel goed een algoritme met de kortste weg kunnen formuleren in termen van steden en wegen in plaats van hoekpunten en randen. Bevat het algoritme niet ‘ en bevat ” … bits van de echte wereld ” ?
• @DavidRicherby, je hebt gelijk, mijn bewoordingen zijn dubbelzinnig. Wat ik bedoelde is een zinvol doel. Schroeven draaien om schroeven te draaien is zinloos net zo goed als het sorteren van een array die nooit wordt gebruikt. Met bedrijfslogica bedoel ik alle programmagelogica behalve de nutslogica en technologiestapel boilerplate, dwz alle logica die het doel van het programma daadwerkelijk implementeert, dwz de bedrijfslogica van het bakken van een cake is het mengen van ingrediënten en bakken en omvat niet leren mixen of bakken ( wat in dit geval hergebruikte utility-logica is).
• @DavidRicherby, wat betreft bits van de echte wereld , bedoel ik actualisatie, dat wil zeggen dat een programma in tegenstelling tot een algoritme op de een of andere manier moet communiceren met de fysieke wereld. Een algoritme kan daarentegen een puur wiskundig concept zijn.

I ben er vrij zeker van dat andere antwoorden goed genoeg zijn om het voortouw te nemen, maar hier is hoe ik het verschil zie tussen een algoritme en een programma

• Een algoritme bestaat simpelweg uit de stappen (machineonafhankelijk) die moeten worden gevolgd om een probleem op te lossen.

• Een programma is een instructieset voor een specifiek type machine om een algoritme in praktijk te brengen .

Bijvoorbeeld.

Stel dat u een algoritme heeft dat een stap heeft voor het bereiken van een bepaalde plaats voordat u een andere stap doet Hoe deze stap van het bereiken zal worden uitgevoerd, is niet precies gedefinieerd U kunt ervoor kiezen om te lopen of rennen of een bus te nemen om het te doen, maar dat hangt af van hoe u ervoor kiest om het te implementeren (dat is je prog ram).

Je kunt zeggen dat een algoritme een abstractie is van een programma, dat wil zeggen dat je de exacte details mist, maar een plan opstelt om iets te doen .