Como estudante de graduação, acho cada vez mais comum empresas de prestígio (como Google, Facebook, Microsoft, ...) colocar perguntas de algoritmo em seus testes e entrevistas. Algumas startups às quais me inscrevi também perguntaram sobre algoritmos. Será que a fluência dos algoritmos é a coisa mais importante para o desenvolvedor de software nessas empresas?
Se a resposta for sim, quais são os melhores métodos ou recursos para aprender e praticar sobre algoritmos de maneira eficaz? Não consigo me interessar em resolver problemas aparentemente muito complicados encontrados na maioria dos livros ou sites. Embora compreenda facilmente algoritmos básicos (como quicksort, bubblesort, ...), acho imensamente difícil lembrar e reutilizá-los mais tarde.
Obrigado.
P / S: Se você me perguntar do que eu gosto, está criando bons softwares para resolver os problemas dos usuários de forma inovadora. Suponho que isso não significa necessariamente que o software tenha que ser muito complicado.
fonte
Respostas:
Algoritmos são claros
Aqui está a coisa bonita dos algoritmos: o espaço do problema com o qual eles lidam é bem definido, ou seja, seus requisitos não são apenas conhecidos de fato , mas geralmente são formalizados como as métricas da qualidade da solução.
Portanto, se eu disser para você criar um algoritmo, não há muito potencial para problemas de comunicação, e medir seu desempenho é uma tarefa trivial. Ao mesmo tempo, seu desempenho é um indicador bastante bom para sua capacidade de pensar logicamente.
Algoritmos são um filtro eficiente
O problema atual da indústria (e da educação) é a baixa qualidade média dos graduados. Isso foi ilustrado com o teste FizzBuzz , que é:
Aparentemente, a maioria de todos os graduados em Comp Sci não consegue resolver esse problema. Observe que esta é uma pergunta algorítmica, embora, é claro, uma pergunta embaraçosamente simples. Diante disso, recebendo alguém que possa resolver o tipo de problemas apresentados no Google Code Jam ou no Project Euler, você já está gostando do crème-de-la-crème.
Algoritmos são uma pequena parte do desenvolvimento de software
A verdade é que, assim que você trabalha na indústria, não estará usando suas habilidades de algoritmo mais de 1% do tempo.
Antes de começar a escrever o código, você deve primeiro reunir e analisar os requisitos. Então você deve sintetizar seu design com base neles. Então você deve implementar o design. Em seguida, você deve avaliar a implementação em relação aos requisitos originais, iterar os requisitos, iterar o design, iterar a implementação e assim por diante.
Um dos requisitos é um desempenho sensato . Se esse requisito não for atendido, você deve criar um perfil de sua implementação para rastrear os gargalos e otimizar, que às vezes é uma questão de micro-otimização direta (o que é bastante fácil de fazer), mas às vezes é uma questão de usando algoritmos melhores (o que nem sempre é fácil depois). Assim sendo:
Algoritmos são críticos
Quanto melhor a sua compreensão dos algoritmos, maior a chance de você acertar na primeira vez. Caso contrário, é provável que você não tenha apenas um problema que possa ser resolvido com a implementação de um algoritmo melhor, mas também não será capaz de resolvê-lo.
Portanto, embora você quase nunca precise dessa habilidade, ela apresenta um único ponto de falha em sua metodologia de desenvolvimento e, se você não a tiver, só poderá esperar que a necessidade nunca surja ou que alguém salte para corrigi-la. vocês.
O que é realmente importante é entender a complexidade computacional e como mantê-la baixa, como também expliquei em resposta a uma pergunta semelhante . Ou se especializar em coisas em que isso simplesmente não é importante, como o desenvolvimento da GUI, mas quase todo mundo odeia ... por um motivo!
fonte
fizzbuzzse o número fosse divisível por ambos e que muitos escorregaram porque você precisa solicitar modulo de cheques com cuidado.Em geral, programar como trabalho não é sobre algoritmos. Você pode passar anos programando aplicativos CRUD sem exigir habilidades algorítmicas profundas.
Programar como trabalho é sobre:
Comunicação:
Seu código-fonte é um meio de comunicar suas idéias aos seus colegas. Se ninguém pode ler / entender seu código, isso não vale nada.
Um desenvolvedor solitário que não fala com outro desenvolvedor provavelmente começaria a cometer erros no código e acreditaria que sua própria abordagem é a única aceitável.
Você deve saber como se comunicar com as partes interessadas, departamento de controle de qualidade, usuários, designers visuais, DBAs etc.
Como desenvolvedor experiente, você deve ensinar colegas menos experientes que desejam melhorar suas habilidades.
Conhecimento das ferramentas certas: controle de versão, sistema de rastreamento de bugs, IDEs, qual idioma é mais adequado para uma tarefa específica e por que, como usar a análise de código etc.
Amplo conhecimento e cultura: o que são linguagens funcionais? Como os computadores interpretam o código? Por que LOC é uma medida sem sentido? etc.
Conhecimento profundo dos idiomas com os quais você trabalha.
Algoritmos.
A Ciência da Computação, por outro lado, é mais orientada para algoritmos. Se você trabalha como cientista, isso pode não ter nada a ver com o trabalho de desenvolvedor, e você trabalhará mais em como otimizar um algoritmo, como transformar uma representação de dados em outra, etc.
fonte
Penso que perguntas sobre algoritmos em entrevistas são uma das principais maneiras pelas quais as empresas tentam julgar a compreensão do candidato sobre os fundamentos da ciência da computação. Embora essa não seja a única área de habilidade importante para um programador profissional, é uma das principais competências de um bom programador.
Eu acho que a razão pela qual muitas grandes empresas enfatizam os fundamentos de CS em seu processo de entrevista é que é a principal habilidade que é menos desenvolvida depois de se formar e ingressar na força de trabalho. A capacidade prática de programação, as habilidades de design, as práticas de engenharia de software e outras coisas são desenvolvidas principalmente por meio da experiência, enquanto os seus fundamentos de CS são desenvolvidos principalmente no curso de sua educação.
Sobre como praticar o design de algoritmos, Steve Yegge recomenda o Manual de design de algoritmos de Skiena, em seu excelente guia para entrevistas como programador .
fonte
Como um desenvolvedor de software bem-sucedido, autodidata e que fez apenas alguns cursos de ciência da computação na faculdade, direi que os maiores problemas enfrentados pelos negócios atualmente não são a capacidade de todos os seus programadores escreverem um algoritmo de classificação de bolhas da maneira mais eficiente possível. Os verdadeiros problemas que as empresas enfrentam:
Desenvolvedores que não podem aprender e se adaptar rapidamente a novos domínios
Desenvolvedores que não podem interagir socialmente com clientes ou partes interessadas de maneira significativa
Desenvolvedores que não conseguem adivinhar e questionar requisitos de negócios incorretos ou mal pensados
Desenvolvedores que não entendem como testar completamente seu código e recursos
Desenvolvedores que não podem fornecer estimativas significativas em tempo hábil
Desenvolvedores que não podem criar documentação clara e concisa
Desenvolvedores que não podem se auto-iniciar ou se encarregar de uma situação
Nove em cada dez vezes, aposto que quase todas as circunstâncias em que um desenvolvedor se debate em uma empresa é porque falha irremediavelmente em uma das qualidades acima. Esqueça o Google e o Facebook, são casos de exceção e têm necessidade legítima de pessoas que entendem profundamente a ciência da computação.
Negócios reais, embora não lutem com as complexidades da ciência da computação, eles lutam com as complexidades da humanidade. O problema é que é REALMENTE difícil testar as qualidades mencionadas acima. Na maioria das vezes, você deve julgar as pessoas por essas qualidades com base em sua reação intestinal. Isso é difícil se você não possui boas habilidades e intuição de pessoas, é muito mais fácil testar o conhecimento de algoritmos.
fonte
Pessoalmente, vejo algoritmos "padrão" e estruturas de dados como parte do vocabulário de um programador. E muitos dos problemas práticos que você enfrenta como programador geralmente têm uma solução que é (pelo menos parcialmente) expressável nesse vocabulário.
Ter esse vocabulário à sua disposição impede que você tenha que criar suas próprias soluções (reinventar a roda, por assim dizer), permitindo que você trabalhe de maneira mais inteligente e com mais rapidez.
Force-se a completá-los. Você se agradecerá mais tarde. Mesmo que você não se lembre deles detalhadamente (embora com bastante prática você certamente o faça), poder dizer "Lembro-me de resolver algo semelhante usando o algoritmo X ou a estrutura de dados Y" o ajudará tremendamente. Mesmo que exija que você pesquise os detalhes e atualize sua memória.
fonte
Embora você não possa ser um bom programador sem conhecer seus algoritmos, é injusto manter outros aspectos da profissão de programa fora de cena. Por exemplo, disciplina estrita e bom domínio da sua língua nativa são pelo menos tão importantes para ser um bom programador quanto seu conhecimento de algoritmos. Também não se deve subestimar a importância de entender suas ferramentas básicas, como linguagens de programação, sistemas de controle de fontes, ambientes de teste etc.
No entanto, quando se trata de entrevistas, medir sua compreensão de algoritmos é muito mais simples do que medir suas outras habilidades relacionadas ao trabalho como programador. É por isso que os entrevistadores geralmente se concentram em perguntar sobre algoritmos e prestam muita atenção à maneira como você os explica durante a entrevista. Não é porque outras coisas sejam menos importantes, mas porque é difícil avaliar essas outras coisas nos 30 minutos alocados para a entrevista.
fonte
Sim, a programação é principalmente sobre algoritmos.
Mas talvez não no sentido em que você está pensando.
Tenho a impressão de que todos estamos usando diferentes definições de algoritmo. Para ser sincero, é difícil responder a essa pergunta porque algoritmo é um termo vago. Vou usar a definição da Wikipedia para responder a esta pergunta:
Este é o coração e a alma da programação. Ao escrever qualquer código, você está apenas implementando um algoritmo. Se você está escrevendo alguns aplicativos CRUD, está implementando um algoritmo simples. Ser capaz de criar um algoritmo para resolver um problema é o que é a programação. O resto são apenas detalhes.
Não concordo com o pôster anterior que dizia que ter uma compreensão profunda de uma linguagem é mais importante do que entender algoritmos. Qualquer bom programador deve ser capaz de aprender profundamente uma linguagem, mas sem algoritmos, você não pode criar nenhum código sozinho.
fonte
A resposta é totalmente dependente do trabalho que você está realizando. Alguns campos são particularmente mais focados em algoritmos do que outros. Falando nisso, tive o prazer de entrevistar a Amazon várias vezes. Mesmo que a posição tivesse pouco a ver com esses algoritmos complexos, eu me perguntava como fazer uma tarefa ser amortizada em tempo constante.
O que prova uma forte compreensão dos algoritmos fornece uma prova para o seu potencial empregador de que você é um solucionador de problemas adequado. Não é realmente um bom indicador (IMO) de um bom funcionário, mas alguns empregadores usam isso para triagem. Se você está se candidatando a uma posição que exige uma graduação, espera-se que você tenha uma base mais rigorosa em algoritmos.
O que (IMO) é imensamente útil na prática não é memorizar algoritmos específicos, mas através da compreensão de como alguns algoritmos funcionam, existe uma pequena pepita no fundo da sua mente, onde você dirá "Eu já vi isso antes" ou "Eu sei que eu pode fazer isso melhor ", o que gerará um pouco de pesquisa sobre a solução do seu problema.
fonte
Eu sempre acho que a programação é mais orientada a dados do que algoritmos ... mas então, de que serve os dados se você não fizer as coisas ... todas essas manipulações são algoritmos. Então, na verdade, sim, a programação é praticamente inteiramente baseada em algoritmos.
Pode não parecer matemática, e muito trabalho algorítmico que você faria no dia-a-dia é muito simples, como enviar dados entre uma GUI e um programa, mas isso também conta como um algoritmo. A inserção de um elemento em uma caixa de listagem é um algoritmo de inserção padrão que vem com seus próprios problemas, como desempenho e manipulação de estrutura de lista.
fonte
Somente programadores que trabalham para essas empresas podem realmente responder a sua pergunta. Os tipos de algoritmos tratados em, por exemplo, "Introdução aos algoritmos", provavelmente desempenharam um papel em 0,01% da minha vida de programação nos últimos 25 anos. Quando eu preciso de uma estrutura ou tipo de dados, geralmente as bibliotecas ou estruturas fornecidas têm o que eu preciso. Quando preciso de uma FFT super rápida, encontro algo como a biblioteca Intel Math em vez de escrever uma. No entanto, posso entender como o que eles fazem no Google é muito diferente do que eu fiz na minha carreira. O livro de Skiena "O Manual de Design de Algoritmos" foi revelador por causa das histórias de guerra que ele conta. Você pode dizer que ele usa algoritmos em seu trabalho MUITO.
Na minha experiência como consultor de programação independente, o sucesso veio de três coisas: 1. Comunicação eficaz com os clientes; 2. Escrita de código que funciona. 3. Gerenciando a complexidade
Fazer apenas os números 1 e 2 não é suficiente. Se o código não puder ser mantido (por alguém que não seja o programador), ele estará condenado.
O número 3 é a habilidade de programação mais difícil de dominar. Exige que o pensamento seja colocado na arquitetura, design e codificação. Requer dominar a refatoração. Requer uma compreensão dos princípios do SOLID / DRY. Se eu tivesse que contratar um programador que lesse Introdução aos Algoritmos e se dedicasse a dominá-lo ou alguém que lesse O Programador Pragmático e se dedicasse a ser um, eu o contrataria sempre. (Não que eles tenham que se excluir mutuamente).
fonte
Sim.
Ciência da Computação é principalmente algoritmos (por porcentagem).
Não.
Mas essa é a "ciência" dos computadores. A aplicação mais comum da Ciência da Computação é a Engenharia de Software. Engenharia de software não é principalmente algoritmos. É principalmente sobre a arte de criar, a busca da perfeição e está centrada em afetar positivamente a vida das pessoas reais que existem hoje. Embora a Ciência da Computação possa compartilhar algumas das mesmas motivações, está muito longe da Engenharia de Software.
Pergunte a um professor titular de uma importante Universidade de Ciência da Computação qual é a coisa mais crítica a entender sobre programação e eles provavelmente lhe dirão "algoritmos e estruturas de dados"
Pergunte a um desenvolvedor sênior de uma grande empresa de software qual é a coisa mais crítica a entender sobre programação e eles provavelmente dirão a você "aprendendo a encantar os clientes" (implicado em entender agilidade, pensar como um cliente, enviar no prazo e continuamente, fazendo coisas que funcionem , etc)
Pode parecer semântica, mas, pelo meu entendimento, os dois são notavelmente diferentes tanto na prática quanto na teoria.
fonte
Se eu tivesse que escolher uma coisa na ciência da computação como a parte mais importante, escolheria abstrações , não algoritmos.
fonte
Em Ciência da Computação, quais conceitos você aprenderá serão inúteis até mostrá-lo. O problema é a principal preocupação que precisa ser resolvida, portanto o algoritmo é um breve planejamento de como o problema será resolvido em geral. Portanto, é uma grande preocupação no mundo da Ciência da Computação.
Acho que quase todos os aspectos da Ciência da Computação precisam de algoritmo Deixe-me mostrar isso A lista a seguir incluiria várias áreas da Ciência da Computação e quais algoritmos eles usam.
Automata
Construção Powerset. Algoritmo para converter autômato não determinístico em autômato determinístico. Algoritmo de Todd-Coxeter. Procedimento para gerar cosets.
Inteligência artificial
Alpha Beta. Alpha max mais beta min. Amplamente utilizado em jogos de tabuleiro. Algoritmos de formigas. A otimização de colônias de formigas é um conjunto de algoritmos inspirados no comportamento das formigas para resolver um problema, encontrar o melhor caminho entre dois locais. DE (evolução diferencial). Resolva o problema de ajuste polinomial de Chebyshev. Reconhecimento semi-supervisionado de sentenças sarcásticas nas análises de produtos on-line. Algortitmo que reconhece sacarsmos ou ironia em um tweet ou documento online. Um algoritmo desse tipo também será essencial para a programação de robôs humanóides.
Visão computacional
Epítome. Represente uma imagem ou vídeo por um menor. Contando objetos em uma imagem . Usa o algoritmo de rotulagem de componentes conectados para rotular primeiro cada objeto e contar os objetos. Algoritmo O'Carroll. A partir de uma conversão matemática da visão de insetos, esse algoritmo avalia como contornar evitando objetos.
Algorítmos genéticos
Eles usam três operadores. seleção (escolha a solução), reprodução (use as soluções escolhidas para construir outras), substituição (substitua a solução, se melhor).
Seleção proporcional de aptidão. Também conhecida como seleção de roleta, é uma função usada para selecionar soluções. Seleção de truncamento. Outro método para selecionar soluções, ordenadas por condicionamento físico. Seleção de torneios. Selecione a melhor solução por um tipo de torneio. Amostragem estocástica universal. Os indivíduos são mapeados para segmentos contíguos de uma linha, de modo que o segmento de cada indivíduo seja igual em tamanho à sua adequação, exatamente como na seleção de roleta.
Redes neurais
Rede Hopfield. Rede neural artificial recorrente que serve como sistemas de memória endereçável por conteúdo com unidades de limite binário. Eles convergem para um estado estável. Retropropagação. Técnica de aprendizado supervisionado usada para o treinamento de redes neurais artificiais. Mapa auto-organizado (mapa de Kohonen). Redes neurais treinadas usando aprendizado não supervisionado para produzir representação em baixa dimensão (2D, 3D) das amostras de treinamento. Bom para visualizar dados de alta dimensão.
Bioinformática
Needleman-Wunsch. Executa um alinhamento global em duas sequências, para sequências de proteínas ou nucleotídeos. Smith-Waterman. Variação do Needleman-Wunsch.
Compressão
Algoritmos de compactação sem perdas
Transformação Burrows-Wheeler. Pré-processamento útil para melhorar a compactação sem perdas. Desinflar. Compactação de dados usada pelo ZIP. Codificação Delta. Auxílio à compactação de dados nos quais dados sequenciais ocorrem com frequência. Codificação incremental. Codificação delta aplicada a sequências de strings. LZW. (Lempel-Ziv-Welch). Sucessor de LZ78. Cria uma tabela de conversão a partir dos dados para compactar. É usado pelo formato gráfico GIF. LZ77 e 78. A base de outras variações LZ (LZW, LZSS, ...). Ambos são codificadores de dicionário. LZMA. Abreviação de Algoritmo em cadeia de Lempel-Ziv-Markov. LZO. Algoritmo de compactação de dados focado na velocidade. PPM(Previsão por correspondência parcial). Técnica adaptativa de compactação de dados estatísticos baseada em modelagem e previsão de contexto. Codificação Shannon-Fano. Constrói códigos de prefixo com base em um conjunto de símbolos e suas probabilidades. Binário truncado. Uma codificação de entropia normalmente usada para distribuições de probabilidade uniformes com um alfabeto finito. Melhore a codificação binária. Codificação de execução. Compactação primária que substitui uma sequência do mesmo código pelo número de ocorrências. Sequitur. Inferência gramatical incremental em uma string. EZW (Wavelet incorporado de Zerotree). Codificação progressiva para compactar uma imagem em um fluxo de bits com maior precisão. Pode haver compressão com perda também com melhores resultados.
Codificação de entropia Esquema de codificação que atribui códigos aos símbolos, de modo a corresponder os comprimentos dos códigos às probabilidades dos símbolos.
Codificação de Huffman. Compressão simples sem perdas, aproveitando as frequências relativas de caracteres. Codificação adaptativa de Huffman. Técnica de codificação adaptativa baseada na codificação de Huffman. Codificação aritmética. Codificação avançada de entropia. Codificação de intervalo. O mesmo que a codificação aritmética, mas olhou de uma maneira ligeiramente diferente. Codificação unária. Código que representa um número n com n, seguido de um zero. Elias delta, gama, codificação ômega. Código universal que codifica os números inteiros positivos. Codificação de Fibonacci. Código universal que codifica números inteiros positivos em palavras de código binário. Codificação Golomb. Forma de codificação de entropia ideal para alfabetos após distribuições geométricas. Codificação de arroz. Forma de codificação de entropia ideal para alfabetos após distribuições geométricas.
Algoritmos de compressão com perdas
Codificação preditiva linear. Compressão com perdas, representando o envelope espectral de um sinal digital de fala em forma compactada. Algoritmo A-law. Algoritmo de companding padrão. Algoritmo Mu-law. Compressão de sinal analógico padrão ou algoritmo de companding. Compressão fractal. Método usado para comprimir imagens usando fractais. Transforme a codificação. Tipo de compactação de dados para dados como sinais de áudio ou imagens fotográficas. Quantização vetorial. Técnica frequentemente usada na compactação de dados com perda. Compressão Wavelet. Forma de compactação de dados adequada para compactação de imagem e áudio.
Criptografia
Chave secreta (criptografia simétrica)
Use uma chave secreta (ou um par de chaves diretamente relacionadas) para descriptografia e criptografia.
Advanced Encryption Standard (AES) , também conhecido como Rijndael. Blowfish. Projetado por Schneier como um algoritmo de uso geral, destinado a substituir o DE antigo. Data Encryption Standard (DES) , anteriormente DE Algorithm. IDEA (Algoritmo Internacional de Criptografia de Dados) . Anteriormente IPES (Improved PES), outro substituto para o DES. É usado pelo PGP (Pretty Good Privacy). Executa transformações em dados divididos em blocos, usando uma chave. RC4 ou ARC4. Cifra de fluxo amplamente usada em protocolos como SSL para tráfego na Internet e WEP para redes sem fio. Algoritmo de criptografia minúsculo. Fácil de implementar o algoritmo de cifra de bloco usando algumas fórmulas. PES (Proposta de Padrão de Criptografia). Nome mais antigo para IDEA.
Chave pública (criptografia assimétrica)
Use um par de chaves, designadas como chave pública e chave privada. A chave pública criptografa a mensagem, apenas a chave privada permite descriptografá-la.
DSA (algoritmo de assinatura digital). Gere chaves com números primos e aleatórios. Foi usado por agências dos EUA, e agora de domínio público. ElGamal. Baseado no Diffie-Hellman, usado pelo software GNU Privacy Guard, PGP e outros sistemas criptográficos. RSA (Rivest, Shamir, Adleman). Amplamente utilizado em protocolos de comércio eletrônico. Use números primos. Troca de chaves Diffie-Hellman (Merkle) (ou troca de chaves exponencial). Método e algoritmo para compartilhar segredo em um canal de comunicação desprotegido. Usado pela RSA. NTRUEncrypt. Faça uso de anéis de polinômios com multiplicações de convolução.
Funções de resumo da mensagem
Um resumo da mensagem é um código resultante da criptografia de uma string ou dados de qualquer tamanho, processados por uma função hash.
MD5. Usado para verificar imagens ISO de CDs ou DVDs. RIPEMD (resumo das mensagens de avaliação das primitivas de integridade do RACE). Baseado nos princípios do MD4 e similares ao SHA-1. SHA-1 (algoritmo de hash seguro 1). Mais comumente usado do conjunto SHA de funções hash criptográficas relacionadas. Foi projetado pela agência da NSA. HMAC. autenticação de mensagem com chave hash. Tigre (TTH). Geralmente usado em hashes de árvores Tiger.
Criptográfico usando números pseudo-aleatórios Veja. Geradores de números aleatórios
Técnicas em criptografia
Compartilhamento secreto, divisão secreta, divisão de chaves, algoritmos M de N.
Esquema de compartilhamento secreto de Shamir. Esta é uma fórmula baseada na interpolação polinomial. Esquema de compartilhamento secreto de Blakley. É de natureza geométrica, o segredo é um ponto em um espaço m-dimensional.
Outras técnicas e descriptografia
Soma do subconjunto. Dado um conjunto de números inteiros, algum subconjunto soma igual a zero? Usado em criptografia. Algoritmo de Shor. Algoritmo quântico capaz de descriptografar um código com base em funções assimétricas, como RSA.
Geometria
Embalagem de presente. Determinando o casco convexo de um conjunto de pontos. Distância Gilbert-Johnson-Keerthi. Determinando a menor distância entre duas formas convexas. Graham scan. Determinando o casco convexo de um conjunto de pontos no plano. Interseção do segmento de linha. Descobrir se as linhas se cruzam com um algoritmo de linha de varredura. Aponte no polígono. Testa se um determinado ponto está dentro de um determinado. Interseção raio / plano. * Interseção de linha / triângulo. * Caso particular de interseção de raio / plano. Poligonização de superfícies implícitas. Aproximar uma superfície implícita com uma representação poligonal. Triangulação.Método para avaliar a distância até um ponto, de ângulos a outros pontos, cuja distância é conhecida.
Gráficos 3D Surface Tracker Technology. Processo para adicionar imagens nas paredes de um vídeo enquanto as superfícies ocultas são levadas em consideração. Bellman-Ford. Calcula os caminhos mais curtos em um gráfico ponderado (onde alguns dos pesos das arestas podem ser negativos). Algoritmo de Dijkstra. Calcula os caminhos mais curtos em um gráfico com pesos de borda não negativos. Métodos de perturbação. Um algoritmo que calcula os caminhos mais curtos localmente em um gráfico. Floyd-Warshall. Resolve o problema de caminho mais curto de todos os pares em um gráfico direcionado ponderado. Descoberta do ciclo de Floyd. Localiza ciclos nas iterações. Johnson. Todos os pares de algoritmo de caminho mais curto no gráfico direcionado com ponderação esparsa. Kruskal.Localiza uma árvore de abrangência mínima para um gráfico. Prim's. Localiza uma árvore de abrangência mínima para um gráfico. Também chamado de algoritmo DJP, Jarník ou Prim – Jarník. * Boruvka. * Encontra uma árvore de abrangência mínima para um gráfico. Ford-Fulkerson. Calcula o fluxo máximo em um gráfico. Edmonds-Karp. Implementação de Ford-Fulkerson. Interruptor de abrangência mínimo sem bloqueio. Para uma troca telefônica. Woodhouse-Sharp. Localiza uma árvore de abrangência mínima para um gráfico. Baseado em primavera. Algoritmo para desenho de gráfico. Húngaro. Algoritmo para encontrar uma combinação perfeita. Algoritmo de coloração. Algoritmo de coloração de gráfico. Vizinho mais próximo.Encontre o vizinho mais próximo. Classificação topológica. Classifique um gráfico acíclico direcionado de forma que cada nó chegue antes de todos os nós nos quais possui arestas (de acordo com as direções). O algoritmo de ancestrais menos comuns off-line de Tarjan. Calcule os ancestrais comuns mais baixos para pares de nós em uma árvore.
Gráficos
Algoritmo de linha de Bresenham. Usa variáveis de decisão para plotar uma linha reta entre 2 pontos especificados. Paisagem Desenhe um cenário 3D. * Algoritmo de linha DDA. * Usa matemática de ponto flutuante para plotar uma linha reta entre 2 pontos especificados. Preenchimento de inundação. Preenche uma região conectada com uma cor. Restauração de imagem. Restaurar foto, melhorar imagens. Algoritmo de linha de Xiaolin Wu. Antialiasing de linha. Algoritmo do pintor. Detecta partes visíveis de um cenário tridimensional. Traçado de raio. Renderização de imagem realista. Phong sombreamento. Um modelo de iluminação e um método de interpolação em computação gráfica em 3D. Sombreamento Gouraud.Simule os diferentes efeitos da luz e da cor na superfície de um objeto 3D. Renderização de Scanline. Constrói uma imagem movendo uma linha imaginária. Iluminação global. Considera iluminação direta e reflexão de outros objetos. Interpolação. Construindo novos pontos de dados, como no zoom digital. Ressintetizador. Remova um objeto em uma foto e reconstrua o plano de fundo Usado pelo Photoshop e The Gimp. Tutorial de ressintetizador. Algoritmo de interceptação de inclinação. É uma implementação da fórmula de interceptação de inclinação para desenhar uma linha. Interpolação de spline. Reduz o erro com o fenômeno de Runge. Tecnologia de rastreador de superfície 3D. Adicionando imagens ou vídeos nas paredes de um vídeo, superfícies ocultas sendo levadas em consideração.
Listas, matrizes e árvores
Procurando
Pesquisa no dicionário. Veja pesquisa preditiva. Algoritmo de seleção. Localiza o k-ésimo item da lista. Algoritmo de busca binária. Localiza um item em uma lista classificada. Pesquisa pela primeira vez. Atravessa um gráfico nível por nível. Pesquisa em profundidade. Percorre um gráfico ramo por ramo. Melhor primeira pesquisa. Percorre um gráfico na ordem de importância provável usando uma fila de prioridade. Uma pesquisa em árvore. * Caso especial da pesquisa pela primeira vez que usa heurísticas para melhorar a velocidade. Pesquisa de custo uniforme. Uma pesquisa em árvore que localiza a rota de menor custo em que os custos variam. Pesquisa preditiva.Pesquisa binária, que leva em consideração a magnitude do termo de pesquisa versus os valores alto e baixo da pesquisa. Tabela de hash. Associe chaves a itens em uma coleção não classificada, para recuperá-los em um tempo linear. Pesquisa interpolada. Veja pesquisa preditiva.
Classificação
Classificação de árvore binária. Classificação de uma árvore binária, incremental, semelhante à classificação por inserção. Bogosort. Tipo aleatório ineficiente de um cartão de mesa. Tipo de bolha. Para cada par de índices, troque os itens se estiver fora de ordem. Classificação de balde. Divida uma lista em intervalos e classifique-os individualmente. Generaliza a classificação de pigeonhole. Tipo de coquetel (ou bolha bidirecional, agitador, ondulação, transporte, tipo happy hour). A variação da classificação das bolhas, classificada nas duas direções, passa pela lista. Tipo de pente. Variação eficiente do tipo de bolha que elimina "tartarugas", os pequenos valores próximos ao final da lista e utiliza lacunas entre os valores. Contando classificação.Ele usa o intervalo de números na lista A para criar uma matriz B desse comprimento. Os índices em B são usados para contar quantos elementos em A têm um valor menor que i. Gnomo. Semelhante à classificação por inserção, exceto que a movimentação de um elemento para o seu devido local é realizada por uma série de trocas, como na classificação por bolhas. Heapsort. Converta a lista em um heap, continue removendo o maior elemento do heap e adicionando-o ao final da lista. Classificação de inserção. Determine onde o item atual pertence na lista de itens classificados e insira-o lá. Introsort. Ou tipo introspectivo. Ele começa no quicksort e muda para o heapsort em determinado nível de recursão. Mesclar classificação.Classifique a primeira e a segunda metade da lista separadamente e mescle as listas classificadas. Tipo de panqueca. Inverta elementos de algum prefixo de uma sequência. Tipo de buraco de pombo. Preencha uma matriz vazia com todos os elementos de uma matriz a serem classificados, em ordem. Carteiro tipo. Variante hierárquica de classificação de balde, usada pelas agências postais. Ordenação rápida. Divida a lista em duas, com todos os itens da primeira lista antes de todos os itens da segunda lista .; depois classifique as duas listas. Muitas vezes, o método de escolha. Classificação Radix. Classifica chaves associadas a itens, ou números inteiros, processando dígitos. Classificação de seleção. Escolha o menor dos elementos restantes e adicione-o ao final da lista classificada. Tipo de concha.Melhora a classificação de inserção com o uso de intervalos entre valores. Smoothsort. Veja heapsort. Tipo estocástico. Veja bogosort.
e muitos mais...
fonte
Você fez duas perguntas no cabeçalho da pergunta, então eu responderei as duas.
Sim, a Ciência da Computação tem tudo a ver com algoritmos. Bem ... na verdade, isso é um pouco enganador, porque há muitos aspectos na ciência da computação, então vou reformular. A ciência da computação aplicada no mundo do trabalho é predominantemente sobre algoritmos. Empresas como Google, Facebook e todos aqueles lugares malucos em Wall Street que contratam físicos e desenvolvedores querem problemas altamente complexos reduzidos a uma forma simples, o que por si só exige uma profunda compreensão da matemática e do design de algoritmos.
Não, a programação não se resume a algoritmos. Programar é pegar especificações e convertê-las em código que pode ser compilado para execução.
A parte extra da resposta: desenvolvimento de software não é programação e, no entanto, muitos parecem confundir os termos e usá-los de forma intercambiável. A programação é apenas uma função ou técnica, talvez do processo maior de Desenvolvimento de Software. Certamente, o desenvolvimento de software não se resume apenas a algoritmos, trata-se de resolver problemas com software e aplicar processos compatíveis com os negócios para permitir que os problemas sejam resolvidos com eficiência. Embora os processos de desenvolvimento de software - e até a própria programação - possam ser processos algorítmicos em sua natureza, isso não é o mesmo que dizer sobre algoritmos.
fonte