Algoritmus

Algoritmus je konečná a jednoznačné řady pokynů a operací, které umožňují řešit řadu problémů.

Slovo algoritmus pochází z názvu matematik Peršan od IX th  století, Al-Khwarizmi (arabsky: الخوارزمي ).

Pole, které studuje algoritmy, se nazývá algoritmy . Algoritmy jsou dnes nalézt v mnoha aplikacích, jako je například provoz počítačů, kryptografie , o směrování z informací , o plánování a optimální využívání zdrojů, zpracování obrazu , na zpracování textu , v bio -informatics atd

Obecná definice

Algoritmus je obecná metoda řešení jednoho typu problému. Říká se, že je správné, když pro každou instanci problému skončí s produkcí správného výstupu, to znamená, že vyřeší nastolený problém.

Účinnost algoritmu se měří zejména:

• jeho doba výpočtu,
• jeho spotřeba RAM (za předpokladu, že každá instrukce má konstantní dobu provádění),
• přesnost získaných výsledků (například pomocí pravděpodobnostních metod ),
• jeho škálovatelnost (schopnost efektivně paralelizovat),
• atd.

Počítače, které používají tyto algoritmy, nejsou nekonečně rychlé, protože strojový čas zůstává omezeným prostředkem, a to navzdory neustálému zvyšování výkonu počítače. Algoritmus bude proto považován za efektivní, pokud zdroje, které má k dispozici, využívá šetrně, to znamená čas CPU , RAM a (aspekt nedávného výzkumu) spotřeba elektrické energie. Analýza složitosti algoritmu umožňuje předpovědět vývoj ve výpočetním čase nezbytném k dosažení algoritmu podle jeho termínu podle množství zpracovávaných dat.

Některé související definice

Donald Knuth (1938-) uvádí jako předpoklad algoritmu pět vlastností:

• Finitude: „Algoritmus musí vždy skončit po konečném počtu kroků. "
• Přesná definice: „Každý krok algoritmu musí být přesně definován, akce, které mají být transponovány, musí být přesně a přesně stanoveny pro každý případ. "
• Záznamy: „množství, které mu bylo přiděleno před zahájením algoritmu.“ Tyto položky jsou převzaty ze zadané sady objektů “ .
• Výstupy: "veličiny, které mají specifický vztah se vstupy" .
• Účinnost: „všechny operace, které musí algoritmus provádět, musí být dostatečně základní, aby je bylo možné v zásadě provádět v konečném čase pomocí papíru a tužky“ .

George Boolos (1940-1996), filozof a matematik, nabízí následující definici:

• "Výslovné pokyny pro určení n-tého členu množiny, pro n libovolně velké celé číslo." Takové pokyny jsou dány velmi výslovně, ve formě, kterou může použít počítací stroj nebo člověk, který je schopen převést velmi základní operace na symboly. "

Gérard Berry (1948-), výzkumný pracovník v oblasti počítačových věd, uvádí následující obecnou definici veřejnosti:

• "Algoritmus je jednoduše způsob, jak velmi podrobně popsat, jak něco udělat." Ukazuje se, že spousta mechanických akcí, pravděpodobně všechny, se k takovéto dekoraci hodí. Cílem je evakuovat myšlenku výpočtu, aby byl proveditelný digitálním strojem (počítačem…). Pracujeme tedy pouze s digitálním odrazem skutečného systému, se kterým algoritmus interaguje. "

Numerické algoritmy

Algoritmy jsou objekty historicky vyhrazené pro řešení aritmetických problémů, jako je například násobení dvou čísel. Byly formovány mnohem později s příchodem matematické logiky a vznikem strojů, které umožnily jejich implementaci, konkrétně počítačů.

Numerické algoritmy

Většina algoritmů není digitální.

Můžeme rozlišit:

• o obecných algoritmů použitelných pro digitální nebo non-digitálních dat: například algoritmy vztahující se k šifrování nebo povolit úložiště nebo předávat je;
• z algoritmů určených pro určitý typ dat (například těch, které souvisejí se zpracováním obrazu ).

Viz také: Seznam obecných témat o algoritmech  ( fr )

Algoritmy v každodenním životě

Algoritmy zasahují do každodenního života.

• Vaření recept může být snížena na algoritmu, jehož specifikace je možno redukovat na hlavních prvků:
  • předkrmy (přísady, použité vybavení);
  • jednoduché základní pokyny (smažení, flambování, zhnědnutí, dušení, blanšírování atd.), jejichž provedení v přesném pořadí vede k požadovanému výsledku;
  • jeden výsledek: připravené jídlo.
  Recepty na vaření však obecně nejsou předkládány důsledně v jednoznačné podobě: je obvyklé používat neurčité výrazy, které umělci ponechávají svobodu ocenění, zatímco nepravděpodobný algoritmus stricto sensu musí být přesný a jednoznačný.
• Tkaní , zejména proto, že byl automatizován pomocí žakárovém stavu je činnost, která může být, že algoritmické.
• Puzzle , stejně jako Rubikovy kostky , mohou být řešeny systematicky algoritmu, který mechanizes své usnesení.
• Ve sportu provádění sekvencí reagujících na účely útoku, obrany, postupu odpovídá algoritmům (v poněkud volném smyslu termínu). Viz zejména taktický článek (fotbal) .
• V ošetřovatelství je klinický úsudek jako algoritmus. Klinický úsudek se týká všech kognitivních a metakognitivních procesů, které vedou k ošetřovatelské diagnóze . Zahrnuje procesy myšlení a rozhodování s cílem zlepšit zdravotní stav a pohodu lidí, které pečovatelé podporují.
• Zákoník , který popisuje soubor postupů použitelné na sadu případech je algoritmus.

Recenze

V každodenním životě došlo v posledních letech k významovému posunu v konceptu „algoritmu“, který se stává více redukčním, protože jsou to v zásadě algoritmy pro správu velkých dat , a na druhé straně univerzálnější ve smyslu že zasahuje do všech oblastí každodenního chování. Dotyčná rodina algoritmů provádí výpočty z velkých objemů dat ( big data ). Dělají klasifikace, vybírají informace a odvozují profil, obvykle spotřeby, který se pak používá nebo komerčně využívá. Důsledků je mnoho a ovlivňují širokou škálu oblastí. Individuální a kolektivní svobody však mohou být nakonec ohroženy, jak ukazuje americká matematička Cathy O'Neil v knize Weapons of Math Destruction , vydané v roce 2016 a vydané ve francouzštině v roce 2018 pod názvem Algorithms: the time bomb (vydané Les Arènes) .

"Dnes matematické modely a algoritmy dělají zásadní rozhodnutí, slouží ke klasifikaci a kategorizaci lidí a institucí, hluboce ovlivňují fungování států bez jakékoli vnější kontroly." A s nekontrolovatelnými hranovými efekty. […] Toto je síla použitá proti lidem. A proč to funguje? Protože lidé nevědí matematiku, protože jsou zastrašováni. Právě tato představa moci a politiky mě přiměla si uvědomit, že jsem to už někde viděl. Jediný rozdíl mezi rizikovými modely ve financích a tímto modelem nadhodnoty v datové vědě spočívá v tom, že v prvním případě v roce 2008 všichni viděli katastrofu spojenou s finanční krizí. Ale v případě učitelů nikdo nevidí neúspěch. Děje se to na individuální úrovni. Lidé jsou tiše propuštěni, jsou poníženi, stydí se za sebe. "

V této knize autor upozorňuje čtenáře na hlavní rozhodnutí, která dnes delegujeme na algoritmy v oblastech, jako jsou vzdělávání, zdraví, zaměstnanost a spravedlnost, pod záminkou, že jsou neutrální a objektivní, zatímco ve skutečnosti vedou „mimořádně subjektivní volby, názory, dokonce předsudky vložené do matematických rovnic“.

Neprůhlednost algoritmů je jedním z hlavních důvodů těchto kritik. Lepší informace o jejich konkrétním režimu provozu by umožnily vyjasnit „sociální smlouvu mezi uživateli internetu a počítači“. Popis každého algoritmu jeho vlastního principu klasifikace informací pomáhá uživateli lépe porozumět možnostem nabízeným algoritmem a získaným výsledkům.

Etika algoritmů

Filozofové Wendell Wallach a Colin Allen nastolili otázky týkající se implementace morálních pravidel v algoritmech umělé inteligence programátory  : „Dnešní [automatické] systémy se blíží úrovni složitosti, která podle našeho názoru vyžaduje, aby samy činily morální rozhodnutí. […]. Tím se rozšíří okruh morálních agentů mimo člověka na uměle inteligentní systémy, které budeme nazývat umělci morálními agenty “ . Martin Gibert ve své knize Moral to robots: an Introduction to the Ethics of Algorithms ( Moral to Robots: an Introduction to the Ethics of Algorithms) zdůrazňuje úlohu programování v etice robotů, konkrétněji se zabývá morálními problémy spojenými s konstrukcí algoritmů. Definuje algoritmus jako „nic víc než řadu pokynů - nebo pravidel - k dosažení daného cíle“ . Etika algoritmů by si proto kladla otázku: „Jaká pravidla implementovat do robotů a jak na to?“ " . Gibert zdůrazňuje zejména dvojznačnost těchto umělých morálních činitelů:

„Umělí morální agenti (AMA) však nejsou morálními agenty v nejsilnějším smyslu tohoto pojmu. Na rozdíl od lidí, se nezdají být odpovědná [sic] za své činy. Nemusí však být, aby činili morálně smysluplná rozhodnutí a vznášeli celou řadu otázek v etice algoritmu. "

Poznámky a odkazy

1. Pojem problému lze vidět v širokém smyslu, může to být úkol, který má být proveden, jako je třídění objektů, přiřazování zdrojů, přenos informací, překlad textu atd. Přijímá data ( záznamy ), například objekty, které mají být tříděny, popis zdrojů, které mají být přiřazeny, potřeby, které je třeba pokrýt, text, který má být přeložen, informace, které mají být přeneseny, adresa příjemce atd., a případně poskytuje data ( výstup ), například seřazené objekty, přidružení potřebných zdrojů, zprávu o přenosu, překlad textu atd.
2. Patrice Hernert, Algorithms , Paris, Presses Universitaires de France, kol.  "Co já vím? ",2002, 128  s. ( ISBN  978-2-13-053180-7 , OCLC  300211244 ) , s.  5.
3. Zejména v operačních systémech a kompilaci
4. (en) Donald E. Knuth, Algorithms , Stanford, CSLI Publications,2011, 510  s. ( ISBN  978-1-57586-620-8 ).
5. Boolos a Jeffrey 1974,1999: 19
6. Krátké shrnutí historie výpočetní techniky, vzdělávací webové série .
7. Philippe Flajolet, Étienne Parizot, „Co je to algoritmus? » , Interstices.fr, 2004.
8. Viz článek Jeanette M. Wing , „  Výpočetní myšlení  “, Komunikace ACM , sv.  49, n o  3,2006, str.  33 ( DOI  10.1145 / 1118178.1118215 , číst online )přeloženo do francouzštiny jako Počítačové myšlení a kniha Gillese Doweka Proměny počtu: úžasná historie matematiky , Paříž, Édition Le Pommier, kol.  "Testy",2007, 223  s. ( ISBN  978-2-7465-0324-3 ).
9. Hervé Tento kurz molekulární gastronomie, svazek 1: Věda, technologie, technika ... kulinářské: jaké vztahy? , (2009) Éditions Quae / Belin.
10. Laurent Théry , „  Řešení Mini-Rubikovy kostky  “, Interstices ,24. prosince 2009( číst online )
11. Marc Nagels, „  Klinické uvažování: zvláštní atraktor  “ , na 17marsconseil.fr ,14. července 2016(zpřístupněno 17. července 2016 )
12. Dominique Cardon, O čem sní algoritmy: naše životy ve věku velkých dat , Édition du Seuil, kol.  "Republic of Ideas",2015, 108  s. ( ISBN  978-2-02-127996-2 ).
13. sympozium „Správa algoritmy“ z 1. st února 2016.
14. Francis Donnat, umělá inteligence, ohrožení soukromí? , Powers Review č. 170, Prahová hodnota,září 2019, 210  s. ( ISBN  978-2-02-140678-8 ) , str. 95
15. Vydání ze dne 17.11.2018, Cathy O'Neil: „Algoritmy vytvářejí vlastní realitu“ [1]
16. "  " Algoritmy jsou zbraní sociální nadvlády "  ", Bibliobs ,2. prosince 2018( číst online , konzultováno 3. prosince 2018 )
17. Dominique Cardon, plátno, které chceme , Bernard Stiegler, str. 23–43
18. Karine Mauvilly, Cyber-minimalismus , Seuil,2019( ISBN  2021402614 ) , s.  209
19. Wendell Wallach, Colin Allen, „  Morální stroje: učit roboty špatně  “, 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 a 978-2-89759-518-0 , OCLC)  1146545412 ).

Dodatky

Související články

• Analýza složitosti algoritmů
• Algoritmický
• Oprava algoritmu
• Algoritmické zkreslení

externí odkazy

• Co je to algoritmus? autorů: Philippe Flajolet a Étienne Parizot v online časopise Interstices
• Definice pojmu „algoritmus“ učenci