Algoritme

En algoritme er en endelig og utvetydig række instruktioner og operationer, der gør det muligt at løse en klasse af problemer.

Ordet algoritme kommer fra navnet på en matematiker perser fra IX th  århundrede, Al-Khwarizmi (arabisk: الخوارزمي ).

Feltet, der studerer algoritmer , kaldes algoritmer . Algoritmer findes i dag i mange applikationer såsom betjening af computere, kryptografi , routing af information , planlægning og optimal udnyttelse af ressourcer, billedbehandling , tekstbehandling , bioinformatik osv.

Generel definition

En algoritme er en generel metode til løsning af en type problem. Det siges at være korrekt, når det for hver forekomst af problemet ender med at producere det korrekte output, det vil sige det løser det stillede problem.

Effektiviteten af ​​en algoritme måles især ved:

• dets beregningstid
• dets forbrug af RAM (forudsat at hver instruktion har en konstant udførelsestid),
• nøjagtigheden af ​​de opnåede resultater (f.eks. ved anvendelse af probabilistiske metoder )
• dets skalerbarhed (dets evne til at blive paralleliseret effektivt),
• etc.

Computere, der kører disse algoritmer, er ikke uendeligt hurtige, da maskintid forbliver en begrænset ressource på trods af en konstant stigning i computerens ydelse. En algoritme vil derfor siges at være effektiv, hvis den sparsomt bruger de ressourcer, den har til rådighed, det vil sige CPU- tid , RAM og (aspekt af nyere forskning) elforbrug. Analysen af ​​den algoritmiske kompleksitet gør det muligt at forudsige udviklingen i beregningstiden, der er nødvendig for at bringe en algoritme til dens betegnelse i henhold til mængden af ​​data, der skal behandles.

Nogle relaterede definitioner

Donald Knuth (1938-) angiver, som en forudsætning for en algoritme, fem egenskaber:

• Finitude: ”En algoritme skal altid slutte efter et endeligt antal trin. "
• Præcis definition: “Hvert trin i en algoritme skal defineres nøjagtigt, de handlinger, der skal transponeres, skal specificeres strengt og uden tvetydighed for hvert tilfælde. "
• Indlæg: "mængder, der gives til den, før en algoritme begynder." Disse poster er taget fra et specificeret sæt objekter ” .
• Outputs: "størrelser, der har et specificeret forhold til inputene" .
• Effektivitet: "alle operationer, som algoritmen skal udføre, skal være tilstrækkeligt basale til, at de i princippet kan udføres i en begrænset periode af en mand, der bruger et papir og en blyant" .

George Boolos (1940-1996), filosof og matematiker, tilbyder følgende definition:

• “Eksplicitte instruktioner til bestemmelse af det nte medlem af et sæt, for n et vilkårligt stort heltal. Sådanne instruktioner gives meget eksplicit i en form, der kan bruges af en beregningsmaskine eller af et menneske, der er i stand til at oversætte meget elementære operationer til symboler. "

Gérard Berry (1948-), forsker inden for datalogi, giver følgende generelle definition af offentligheden:

• ”En algoritme er simpelthen en måde at beskrive i detaljer, hvordan man fortsætter med at gøre noget. Det viser sig, at mange mekaniske handlinger, sandsynligvis alle, egner sig godt til en sådan udtørring. Målet er at evakuere tanken om beregning for at gøre den eksekverbar af en digital maskine (computer ...). Vi arbejder derfor kun med en digital refleksion af det virkelige system, som algoritmen interagerer med. "

Numeriske algoritmer

Algoritmer er objekter, der historisk er dedikeret til at løse aritmetiske problemer, såsom multiplikation af to tal. De blev formaliseret meget senere med fremkomsten af matematisk logik og fremkomsten af ​​maskinerne, der gjorde det muligt at implementere dem, nemlig computere.

Ikke-numeriske algoritmer

De fleste algoritmer er ikke digitale.

Vi kan skelne mellem:

• af generelle algoritmer, der gælder for enhver digital eller ikke-digital data: for eksempel algoritmer relateret til kryptering , eller aktiverer butikken eller transmitterer dem;
• af algoritmer dedikeret til en bestemt datatype (for eksempel dem, der er forbundet med billedbehandling ).

Se også: Liste over generelle emner om algoritmer  ( fr )

Algoritmer i hverdagen

Algoritmer griber ind i hverdagen.

• En madlavningsopskrift kan reduceres til en algoritme, hvis dens specifikation kan reduceres til de bestanddele:
  • forretter (ingredienser, brugt udstyr);
  • enkle elementære instruktioner (stegning, flambéing, bruning, braising, blanchering osv.), hvis udførelse i en nøjagtig rækkefølge fører til det ønskede resultat;
  • et resultat: den tilberedte skål.
  Men madlavningsopskrifter præsenteres generelt ikke strengt i en utvetydig form: det er sædvanligt at bruge vage udtryk, der giver kunstneren frihed til påskønnelse, mens en ikke-sandsynlig algoritme, der er streng for sensu, skal være præcis og utvetydig.
• Den vævning , især da det var automatiseret ved Jacquard væven er en aktivitet, der kan siges algoritmisk.
• Et puslespil , som Rubiks terning , kan løses systematisk ved hjælp af en algoritme, der mekaniserer dens opløsning.
• I sport svarer udførelsen af ​​sekvenser, der reagerer på formålene med angreb, forsvar, progression, med algoritmer (i en ret løs forstand af udtrykket). Se især den taktiske artikel (fodbold) .
• I sygepleje er klinisk vurdering som en algoritme. Klinisk vurdering henviser til alle de kognitive og metakognitive processer, der fører til sygeplejediagnose . Det involverer tanke- og beslutningsprocesser med det formål at forbedre de menneskers sundhedstilstand og trivsel, som plejere støtter.
• En juridisk kode , der beskriver et sæt procedurer, der gælder for et sæt sager, er en algoritme.

Anmeldelser

I hverdagen har der i de senere år fundet sted et skift i mening i begrebet "algoritme", som bliver både mere reduktiv, da de i det væsentlige er algoritmer til styring af big data og på den anden side mere universelle i den forstand. at det griber ind i alle områder af daglig adfærd. Familien med algoritmer udfører beregninger ud fra store datamasser ( big data ). De foretager klassifikationer, vælger information og udleder en profil, generelt af forbruget, som derefter bruges eller udnyttes kommercielt. Konsekvenserne er talrige og påvirker en lang række områder. Men individuelle og kollektive friheder kan i sidste ende bringes i fare, som den amerikanske matematiker Cathy O'Neil viser i bogen Weapons of Math Destruction , udgivet i 2016 og udgivet på fransk i 2018 under titlen Algorithms: the time bomb (udgivet af Les Arènes) .

”I dag træffer matematiske modeller og algoritmer vigtige beslutninger, tjener til at klassificere og kategorisere mennesker og institutioner og påvirker dybt staternes funktion uden nogen ekstern kontrol. Og med ukontrollerbare kanteffekter. […] Dette er en magt, der bruges mod mennesker. Og hvorfor fungerer det? Fordi folk ikke kender matematik, fordi de er skræmte. Det var denne forestilling om magt og politik, der fik mig til at indse, at jeg allerede havde set dette et eller andet sted. Den eneste forskel mellem risikomodellerne i finans og denne merværdimodel inden for datavidenskab er, at i det første tilfælde i 2008 så alle katastrofen forbundet med finanskrisen. Men i tilfælde af lærere ser ingen fiasko. Det sker på et individuelt niveau. Folk fyres lydløst, de ydmyges, de skammer sig over sig selv. "

I denne bog advarer forfatteren læseren om de store beslutninger, som vi i dag delegerer til algoritmer på så forskellige områder som uddannelse, sundhed, beskæftigelse og retfærdighed, under påskud af at de er neutrale og objektive, mens de faktisk giver anledning til "særdeles subjektive valg, meninger, endog fordomme indsat i matematiske ligninger".

Opaciteten af ​​algoritmerne er en af ​​hovedårsagerne til denne kritik. Bedre information om deres specifikke driftsform ville gøre det muligt at afklare den "sociale kontrakt mellem internetbrugere og computere". Beskrivelsen for hver algoritme af sit eget informationsklassificeringsprincip hjælper brugeren til bedre at forstå de valg, der tilbydes af algoritmen, og de opnåede resultater.

Etik i algoritmer

Filosofferne Wendell Wallach og Colin Allen har rejst spørgsmål relateret til programmørernes implementering af moralske regler i kunstig intelligensalgoritmer  : "I dag nærmer [automatiske] systemer sig et niveau af kompleksitet, der efter vores mening kræver, at de selv træffer moralske beslutninger. […]. Dette vil udvide cirklen af ​​moralske agenser ud over mennesker til kunstigt intelligente systemer, som vi vil kalde kunstige moralske agenter ” . I sin bog Moral to robots: en introduktion til algoritmernes etik fremhæver Martin Gibert programmeringens rolle i robottens etik ved mere specifikt at beskæftige sig med de moralske spørgsmål knyttet til konstruktionen af ​​algoritmer. Han definerer en algoritme som "intet andet end en række instruktioner - eller regler - for at nå et givet mål" . Ethikken i algoritmer ville derfor stille et spørgsmål: "Hvilke regler skal implementeres i robotter, og hvordan man gør det?" " . Gibert understreger især tvetydigheden af ​​disse kunstige moralske agenter:

”Kunstige moralske agenter (AMA) er imidlertid ikke moralske agenter i udtrykets stærkeste forstand. I modsætning til mennesker synes de ikke at være ansvarlige [sic] for deres handlinger. De behøver dog ikke være at tage moralsk meningsfulde beslutninger og rejse en lang række spørgsmål inden for algoritmeetik. "

Noter og referencer

1. Begrebet Problemet kan ses i en bred forstand, kan det være en opgave, der skal udføres, såsom sortering objekter, tildele ressourcer, transmission af information, oversætte en tekst osv Den modtager data ( posterne ), for eksempel de objekter, der skal sorteres, beskrivelsen af ​​de ressourcer, der skal tildeles, behovene, der skal dækkes, en tekst, der skal oversættes, den information, der skal overføres, og modtagerens adresse osv., og muligvis leverer data ( output ), for eksempel sorterede objekter, ressourcebehovsforeninger, en transmissionsrapport, tekstoversættelse osv.
2. Patrice Hernert, Algorithms , Paris, Presses Universitaires de France, koll.  "Hvad ved jeg? ",2002, 128  s. ( ISBN  978-2-13-053180-7 , OCLC  300211244 ) , s.  5.
3. Især i operativsystemer systemer og kompilering
4. (en) Donald E. Knuth, Algorithms , Stanford, CSLI Publications,2011, 510  s. ( ISBN  978-1-57586-620-8 ).
5. Boolos og Jeffrey 1974,1999: 19
6. Et kort resumé af historien om computing, pædagogisk web-serie .
7. Philippe Flajolet, Étienne Parizot, “Hvad er en algoritme? » , Interstices.fr, 2004.
8. Se artiklen Jeanette M. Wing , "  Computational thinking  ", Communications of the ACM , vol.  49, nr .  3,2006, s.  33 ( DOI  10.1145 / 1118178.1118215 , læs online )oversat til fransk som computertanke og bogen af ​​Gilles Dowek, Metamorphoses of calculus: an forbløffende matematikhistorie , Paris, Édition Le Pommier, coll.  "Tests",2007, 223  s. ( ISBN  978-2-7465-0324-3 ).
9. Hervé Dette molekylære gastronomikursus, bind 1: Videnskab, teknologi, teknik ... kulinarisk: hvilke forhold? , (2009) Éditions Quae / Belin.
10. Laurent Théry , "  Løsning af Mini-Rubiks terning  ", mellemrum ,24. december 2009( læs online )
11. Marc Nagels, "  Clinical reasoning : a strange attractor  " , på 17marsconseil.fr ,14. juli 2016(adgang til 17. juli 2016 )
12. Dominique Cardon, Hvad drømmer algoritmer om: vores liv i big data-tiden , Édition du Seuil, koll.  "Idérepublikken",2015, 108  s. ( ISBN  978-2-02-127996-2 ).
13. Symposium "Governance algoritmer" af en st februar 2016.
14. Francis Donnat, kunstig intelligens, en trussel mod privatlivets fred? , Beføjelser anmeldelse nr. 170, tærskel,september 2019, 210  s. ( ISBN  978-2-02-140678-8 ) , s. 95
15. Udgivelse af 17.11.2018, Cathy O'Neil: "Algoritmer skaber deres egen virkelighed" [1]
16. "  " Algoritmer er et våben for social dominans "  ", Bibliobs ,2. december 2018( læs online , hørt den 3. december 2018 )
17. Dominique Cardon, lærredet, som vi vil have , Bernard Stiegler, s. 23-43
18. Karine Mauvilly, cyber-minimalisme , Seuil,2019( ISBN  2021402614 ) , s.  209
19. Wendell Wallach, Colin Allen, “  Moral Machines: Teaching Robots Right from Wrong  ”, Oxford University Press ,2010
20. Gibert, Martin , Moral to Robots: An Introduction to the Ethics of Algorithms ( ISBN  978-2-89759-517-3 , 2-89759-517-5 og 978-2-89759-518- 0 , OCLC  1146545412 ).

Tillæg

Relaterede artikler

• Analyse af kompleksiteten af ​​algoritmer
• Algoritmisk
• Korrektion af en algoritme
• Algoritmisk bias

eksterne links

• Hvad er en algoritme? af Philippe Flajolet og Étienne Parizot på onlinejournalen Interstices
• Definition af udtrykket "algoritme" af forskere