Algoritmos e complexidade
Um algoritmo é um procedimento específico para resolver um problema computacional bem definido. O desenvolvimento e a análise de algoritmos são fundamentais para todos os aspectos da ciência da computação: inteligência artificial, bancos de dados, gráficos, redes, sistemas operacionais, segurança e assim por diante. Algoritmo o desenvolvimento é mais do que apenas programação. Requer uma compreensão do alternativas disponível para resolver um problema computacional, incluindo o hardware, rede, linguagem de programação e restrições de desempenho que acompanham qualquer solução particular. Também requer a compreensão do que significa para um algoritmo estar correto no sentido de que ele resolve completa e eficientemente o problema em questão.
Uma noção associada é o projeto de uma estrutura de dados específica que permite que um algoritmo seja executado com eficiência. A importância das estruturas de dados decorre do fato de que a memória principal de um computador (onde os dados são armazenados) é linear, consistindo em uma sequência de células de memória numeradas em série 0, 1, 2,…. Assim, a estrutura de dados mais simples é uma matriz linear, na qual adjacente elementos são numerados com índices inteiros consecutivos e o valor de um elemento é acessado por seu índice único. Uma matriz pode ser usada, por exemplo, para armazenar uma lista de nomes, e métodos eficientes são necessários para pesquisar e recuperar com eficiência um nome específico da matriz. Por exemplo, a classificação da lista em ordem alfabética permite a utilização da chamada técnica de pesquisa binária, na qual o restante da lista a ser pesquisada em cada etapa é cortado pela metade. Essa técnica de pesquisa é semelhante à pesquisa de um nome específico em uma lista telefônica. Saber que o livro está em ordem alfabética permite ir rapidamente para uma página que está próxima da página que contém o nome desejado. Vários algoritmos foram desenvolvidos para classificar e pesquisar listas de dados de forma eficiente.
Embora os itens de dados sejam armazenados consecutivamente na memória, eles podem ser ligados entre si por ponteiros (essencialmente, endereços de memória armazenados com um item para indicar onde o próximo item ou itens na estrutura são encontrados) para que os dados possam ser organizados de maneiras semelhantes a aqueles em que eles serão acessados. A estrutura mais simples é chamada de lista vinculada, na qual os itens armazenados de forma não contígua podem ser acessados em uma ordem pré-especificada, seguindo os ponteiros de um item da lista para o próximo. A lista pode ser circular, com o último item apontando para o primeiro, ou cada elemento pode ter ponteiros em ambas as direções para formar uma lista duplamente vinculada. Algoritmos foram desenvolvidos para manipular com eficiência essas listas, procurando, inserindo e removendo itens.
Os ponteiros também fornecem a capacidade de implemento estruturas de dados mais complexas. Um gráfico, por exemplo, é um conjunto de nós (itens) e links (conhecidos como arestas) que conectam pares de itens. Esse gráfico pode representar um conjunto de cidades e as rodovias que as unem, o layout dos elementos do circuito e os fios de conexão em um chip de memória ou a configuração das pessoas interagindo por meio de uma rede social. Os algoritmos de gráfico típicos incluem estratégias de travessia de gráfico, como seguir os links de um nó a outro (talvez procurando um nó com uma propriedade específica) de forma que cada nó seja visitado apenas uma vez. Um problema relacionado é a determinação do caminho mais curto entre dois nós dados em um grafo arbitrário. ( Ver teoria dos grafos.) Um problema de interesse prático em algoritmos de rede, por exemplo, é determinar quantos links quebrados podem ser tolerados antes que as comunicações comecem a falhar. Da mesma forma, no projeto de um chip de integração em escala muito grande (VLSI), é importante saber se o gráfico que representa um circuito é plano, ou seja, se ele pode ser desenhado em duas dimensões sem que nenhum link se cruze (fios se tocando).
A complexidade (computacional) de um algoritmo é uma medida da quantidade de recursos de computação (tempo e espaço) que um algoritmo específico consome quando é executado. Os cientistas da computação usam medidas matemáticas de complexidade que permitem prever, antes de escrever o código, a velocidade de execução de um algoritmo e de quanta memória ele exigirá. Essas previsões são guias importantes para programadores implementando e seleção de algoritmos para aplicações do mundo real.
A complexidade computacional é um continuum , em que alguns algoritmos requerem tempo linear (ou seja, o tempo necessário aumenta diretamente com o número de itens ou nós na lista, gráfico ou rede sendo processado), enquanto outros requerem tempo quadrático ou mesmo exponencial para serem concluídos (isto é, o tempo necessário aumenta com o número de itens ao quadrado ou com o exponencial desse número). No final deste continuum estão os mares turvos de problemas intratáveis - aqueles cujas soluções não podem ser eficientemente implementado . Para esses problemas, os cientistas da computação procuram encontrar heurística algoritmos que quase podem resolver o problema e ser executados em um período de tempo razoável.
Ainda mais longe estão aqueles problemas algorítmicos que podem ser declarados, mas não são solucionáveis; isto é, pode-se provar que nenhum programa pode ser escrito para resolver o problema. Um exemplo clássico de um problema algorítmico insolúvel é o problema da parada, que afirma que nenhum programa pode ser escrito que possa prever se qualquer outro programa será interrompido após um número finito de etapas. A impossibilidade de resolver o problema da parada tem impacto prático imediato no desenvolvimento de software. Por exemplo, seria frívolo para tentar desenvolver uma ferramenta de software que prevê se outro programa em desenvolvimento tem um infinito loop nele (embora ter essa ferramenta seja imensamente benéfico).
Compartilhar:
