Algoritmo

Um algoritmo é uma série finita e inequívoca de instruções e operações que permitem resolver uma classe de problemas.

A palavra algoritmo vem do nome de um matemático persa do IX th  século, Al-Khwarizmi (em árabe: الخوارزمي ).

O campo que estuda algoritmos é denominado algoritmo . Hoje, os algoritmos são encontrados em muitas aplicações, como operação de computadores, criptografia , roteamento de informações , planejamento e uso otimizado de recursos, processamento de imagens , processamento de texto , bioinformática , etc.

Definição geral

Um algoritmo é um método geral para resolver um tipo de problema. Diz-se que está correto quando, a cada instância do problema, termina produzindo o resultado correto, ou seja, resolve o problema proposto.

A eficiência de um algoritmo é medida em particular por:

• seu tempo de cálculo,
• seu consumo de RAM (assumindo que cada instrução tem um tempo de execução constante),
• a precisão dos resultados obtidos (por exemplo, com o uso de métodos probabilísticos ),
• sua escalabilidade (sua capacidade de ser eficientemente paralelizada)
• etc.

Os computadores que executam esses algoritmos não são infinitamente rápidos, pois o tempo da máquina continua sendo um recurso finito, apesar do aumento constante no desempenho do computador. Um algoritmo será, portanto, considerado eficiente se usar os recursos à sua disposição com moderação, ou seja, o tempo de CPU , RAM e (aspecto de pesquisa recente) consumo elétrico. A análise da complexidade algorítmica permite prever a evolução no tempo de computação necessária para levar um algoritmo ao seu termo, de acordo com a quantidade de dados a ser processada.

Algumas definições relacionadas

Donald Knuth (1938-) lista, como pré-requisito de um algoritmo, cinco propriedades:

• Finitude: “Um algoritmo deve sempre terminar após um número finito de etapas. "
• Definição precisa: “Cada etapa de um algoritmo deve ser definida com precisão, as ações a serem transpostas devem ser especificadas com rigor e sem ambigüidades para cada caso. "
• Entradas: "quantidades fornecidas a ele antes do início de um algoritmo." Essas entradas são retiradas de um conjunto específico de objetos ” .
• Saídas: "quantidades tendo uma relação específica com as entradas" .
• Eficiência: “todas as operações que o algoritmo deve realizar devem ser suficientemente básicas para poderem ser realizadas em princípio em um período finito por um homem usando um papel e um lápis” .

George Boolos (1940-1996), filósofo e matemático, oferece a seguinte definição:

• “Instruções explícitas para determinar o enésimo membro de um conjunto, para n um inteiro arbitrariamente grande. Essas instruções são dadas de forma muito explícita, em uma forma que pode ser usada por uma máquina de calcular ou por um ser humano capaz de traduzir operações muito elementares em símbolos. "

Gérard Berry (1948-), pesquisador em ciência da computação, dá a seguinte definição de público geral:

• “Um algoritmo é simplesmente uma maneira de descrever detalhadamente como proceder para fazer algo. Acontece que muitas ações mecânicas, provavelmente todas elas, se prestam bem a essa decorticação. O objetivo é evacuar o pensamento do cálculo, para torná-lo executável por uma máquina digital (computador ...). Portanto, trabalhamos apenas com uma reflexão digital do sistema real com o qual o algoritmo interage. "

Algoritmos numéricos

Algoritmos são objetos historicamente dedicados a resolver problemas aritméticos, como a multiplicação de dois números. Eles foram formalizados muito mais tarde com o advento da lógica matemática e o surgimento das máquinas que os tornaram possível implementá-los, nomeadamente os computadores.

Algoritmos não numéricos

A maioria dos algoritmos não é digital.

Podemos distinguir:

• de algoritmos gerais aplicáveis ​​a quaisquer dados digitais ou não digitais: por exemplo, os algoritmos relacionados à criptografia , ou permitem armazená-los ou transmiti-los;
• de algoritmos dedicados a um determinado tipo de dados (por exemplo, aqueles associados ao processamento de imagem ).

Veja também: Lista de tópicos gerais sobre algoritmos  ( fr )

Algoritmos na vida cotidiana

Algoritmos intervêm na vida cotidiana.

• Uma receita culinária pode ser reduzida a um algoritmo se sua especificação puder ser reduzida aos elementos constituintes:
  • entradas (ingredientes, equipamentos usados);
  • instruções elementares simples (fritar, flambear, dourar, refogar, escaldar, etc.), cuja execução em uma ordem precisa leva ao resultado desejado;
  • um resultado: o prato preparado.
  No entanto, as receitas culinárias geralmente não são apresentadas de forma rigorosa de forma inequívoca: é costume usar termos vagos, deixando o artista uma liberdade de apreciação, enquanto um algoritmo não probabilístico stricto sensu deve ser preciso e inequívoco.
• A tecelagem , principalmente porque foi automatizada pelo tear Jacquard, é uma atividade que pode ser dita algorítmica.
• Um quebra-cabeça , como o Cubo de Rubik , pode ser resolvido sistematicamente por um algoritmo que mecaniza sua resolução.
• No esporte, a execução de sequências respondendo aos propósitos de ataque, defesa, progressão, corresponde a algoritmos (em um sentido bastante amplo do termo). Veja em particular o artigo tático (futebol) .
• Na enfermagem , o julgamento clínico é como um algoritmo. O julgamento clínico se refere a todos os processos cognitivos e metacognitivos que levam a um diagnóstico de enfermagem . Envolve processos de reflexão e tomada de decisão com o objetivo de melhorar o estado de saúde e bem-estar das pessoas que os cuidadores apoiam.
• Um código legal , que descreve um conjunto de procedimentos aplicáveis ​​a um conjunto de casos, é um algoritmo.

Avaliações

Na vida cotidiana, uma mudança de significado ocorreu nos últimos anos no conceito de um “algoritmo” que está se tornando mais redutivo, pois são essencialmente algoritmos de gerenciamento de big data , e por outro lado, mais universal no sentido que intervém em todas as áreas do comportamento diário. A família de algoritmos em questão realiza cálculos a partir de grandes massas de dados ( big data ). Fazem classificações, selecionam informações e deduzem um perfil, geralmente de consumo, que é então utilizado ou explorado comercialmente. As implicações são numerosas e afetam uma ampla variedade de campos. Mas as liberdades individuais e coletivas podem acabar sendo ameaçadas, como mostra a matemática americana Cathy O'Neil no livro Weapons of Math Destruction , publicado em 2016 e lançado em francês em 2018 sob o título Algorithms: the time bomb (publicado por Les Arènes) .

“Hoje, os modelos matemáticos e algoritmos tomam decisões importantes, servem para classificar e categorizar pessoas e instituições, influenciam profundamente o funcionamento dos Estados sem nenhum controle externo. E com efeitos de borda incontroláveis. [...] Esse é um poder usado contra as pessoas. E por que isso funciona? Porque as pessoas não sabem matemática, porque se sentem intimidadas. Foi essa noção de poder e política que me fez perceber que já tinha visto isso em algum lugar. A única diferença entre os modelos de risco em finanças e esse modelo de mais-valia em data science é que, no primeiro caso, em 2008, todos viram a catástrofe ligada à crise financeira. Mas, no caso dos professores, ninguém vê fracasso. Isso acontece em um nível individual. As pessoas são despedidas silenciosamente, são humilhadas, têm vergonha de si mesmas. "

Neste livro, o autor alerta o leitor para as grandes decisões que hoje delegamos a algoritmos em campos tão diversos como educação, saúde, emprego e justiça, a pretexto de que são neutros e objetivos, quando, de facto, dão origem às "escolhas eminentemente subjetivas, opiniões, até preconceitos inseridos em equações matemáticas".

A opacidade dos algoritmos é um dos principais motivos dessas críticas. Uma melhor informação sobre o seu modo específico de funcionamento permitiria clarificar o "contrato social entre os utilizadores da Internet e os computadores". A descrição de cada algoritmo de seu próprio princípio de classificação da informação ajuda o usuário a entender melhor as escolhas oferecidas pelo algoritmo e os resultados obtidos.

Ética dos algoritmos

Os filósofos Wendell Wallach e Colin Allen levantaram questões relacionadas à implementação por programadores de regras morais em algoritmos de inteligência artificial  : "Hoje, os sistemas [automáticos] estão se aproximando de um nível de complexidade que, em nossa opinião, exige que eles próprios tomem decisões morais […]. Isso ampliará o círculo de agentes morais além dos humanos para sistemas artificialmente inteligentes, que chamaremos de agentes morais artificiais ” . Em seu livro Moral to robots: uma introdução à ética dos algoritmos , Martin Gibert destaca o papel da programação na ética dos robôs, tratando mais especificamente das questões morais ligadas à construção de algoritmos. Ele define um algoritmo como "nada mais do que uma série de instruções - ou regras - para atingir um determinado objetivo" . A ética dos algoritmos, portanto, colocaria uma questão: "Quais regras implementar em robôs e como fazê-lo?" " . Gibert destaca em particular a ambigüidade desses agentes morais artificiais:

“Os agentes morais artificiais (AMA) não são, no entanto, agentes morais no sentido mais forte do termo. Ao contrário dos humanos, eles não parecem ser responsáveis [sic] por suas ações. Eles não precisam ser, no entanto, para tomar decisões moralmente significativas e levantar uma série de questões na ética do algoritmo. "

Notas e referências

1. A noção de problema pode ser vista em um sentido amplo, pode ser uma tarefa a ser realizada, como ordenar objetos, atribuir recursos, transmitir informações, traduzir um texto, etc. Ele recebe dados (as entradas ), por exemplo, os objetos a serem classificados, a descrição dos recursos a serem atribuídos, as necessidades a serem cobertas, um texto a ser traduzido, as informações a serem transmitidas e o endereço do destinatário, etc. e possivelmente fornece dados (a saída ), por exemplo, objetos classificados, associações de necessidade de recursos, um relatório de transmissão, tradução de texto, etc.
2. Patrice Hernert, Algorithms , Paris, Presses Universitaires de France, col.  "O que eu sei? ",2002, 128  p. ( ISBN  978-2-13-053180-7 , OCLC  300211244 ) , p.  5.
3. Especialmente em sistemas operacionais e compilação
4. (en) Donald E. Knuth, Algorithms , Stanford, CSLI Publications,2011, 510  p. ( ISBN  978-1-57586-620-8 ).
5. Boolos e Jeffrey 1974,1999: 19
6. Um breve resumo da história da computação, séries educacionais na web .
7. Philippe Flajolet, Étienne Parizot, “O que é um algoritmo? » , Interstices.fr, 2004.
8. Ver o artigo Jeanette M. Wing , "  Computational thinking  ", Communications of the ACM , vol.  49, n o  3,2006, p.  33 ( DOI  10.1145 / 1118178.1118215 , leia online )traduzido para o francês como pensamento do computador e o livro de Gilles Dowek, As metamorfoses do cálculo: uma história surpreendente da matemática , Paris, Édition Le Pommier, coll.  "Testes",2007, 223  p. ( ISBN  978-2-7465-0324-3 ).
9. Hervé Este curso de gastronomia molecular, volume 1: Ciência, tecnologia, técnica ... culinária: que relações? , (2009) Éditions Quae / Belin.
10. Laurent Théry , "  Solving the Mini-Rubik's Cube  ", Interstices ,24 de dezembro de 2009( leia online )
11. Marc Nagels, "  Raciocínio clínico: um atrator estranho  " , em 17marsconseil.fr ,14 de julho de 2016(acessado em 17 de julho de 2016 )
12. Dominique Cardon, O que são os algoritmos que sonham: nossas vidas na era do big data , Édition du Seuil, coll.  "A República das Idéias",2015, 108  p. ( ISBN  978-2-02-127996-2 ).
13. Simpósio "Algoritmos de governança" de 1 ° de fevereiro de 2016.
14. Francis Donnat, Inteligência artificial, uma ameaça à privacidade? , Revisão de Poderes n ° 170, Limiar,setembro de 2019, 210  p. ( ISBN  978-2-02-140678-8 ) , p. 95
15. Lançamento de 17.11.2018, Cathy O'Neil: "Algoritmos criam sua própria realidade" [1]
16. "  " Os algoritmos são uma arma de dominação social "  ", Bibliobs ,2 de dezembro de 2018( leia online , consultado em 3 de dezembro de 2018 )
17. Dominique Cardon, A tela que queremos , Bernard Stiegler, p23-43
18. Karine Mauvilly, Cyber-minimalismo , Seuil,2019( ISBN  2021402614 ) , p.  209
19. Wendell Wallach, Colin Allen, "  Moral Machines: Teaching Robots Right from Wrong  ", Oxford University Press ,2010
20. Gibert, Martin , Moral para Robots: Uma Introdução à Ética de Algoritmos ( ISBN  978-2-89759-517-3 , 2-89759-517-5 e 978-2-89759-518- 0 , OCLC  1146545412 ).

Apêndices

Artigos relacionados

• Análise da complexidade dos algoritmos
• Algorítmico
• Correção de um algoritmo
• Viés algorítmico

links externos

• O que é um algoritmo? por Philippe Flajolet e Étienne Parizot no jornal online Interstices
• Definição do termo "algoritmo" por estudiosos