Quais algoritmos / estruturas de dados devo "reconhecer" e saber pelo nome? [fechadas]

69

Eu gostaria de me considerar um programador bastante experiente. Estou programando há mais de 5 anos. Meu ponto fraco é terminologia. Sou autodidata, portanto, embora saiba programar, não conheço alguns dos aspectos mais formais da ciência da computação. Então, quais são os algoritmos práticos / estruturas de dados que eu pude reconhecer e conhecer pelo nome?

Observe que não estou pedindo uma recomendação de livro sobre a implementação de algoritmos. Não me importo em implementá-las, só quero poder reconhecer quando uma estrutura de algoritmo / dados seria uma boa solução para um problema. Estou pedindo mais uma lista de algoritmos / estruturas de dados que eu deveria "reconhecer". Por exemplo, eu sei a solução para um problema como este:

Você gerencia um conjunto de armários marcados com 0-999. As pessoas vêm até você para alugar o armário e depois retornam para devolver a chave do armário. Como você criaria um software para gerenciar sabendo quais armários são gratuitos e quais são usados?

A solução seria uma fila ou pilha.

O que estou procurando são coisas como "em que situação uma árvore B deve ser usada - qual algoritmo de pesquisa deve ser usado aqui" etc. etc. E talvez uma rápida introdução de como os dados mais complexos (mas comumente usados) estruturam / algoritmos funcionam.

Tentei examinar a lista de estruturas de dados e algoritmos da Wikipedia, mas acho que isso é um pouco exagerado. Então, estou procurando mais quais são as coisas essenciais que devo reconhecer?

Earlz
fonte
10
A votação para fechar como "não construtiva". Qualquer resposta será inteiramente subjetiva - não há consenso sobre o que se "deveria" saber.
Oded
2
Que parte desse problema no armário exige pedidos de entrada / saída? [dica!]
Telastyn 4/12/12
5
@ Oded há absolutamente uma lista com a qual eu acho que a maioria das pessoas concorda em quais estruturas de dados e algoritmos um programador bem versado deve conhecer.
David Cowden
6
@Oded Não há consenso? E o currículo de um curso introdutório sobre algoritmos e estruturas de dados em ciência da computação? Bastante bem padronizado e revisado por pares . Um bom ponto de partida.
MarkJ
3
Solução alternativa; presuma que você cobra por dia e tem uma cobrança máxima. Anexe uma etiqueta de papel à chave quando deixar o armário e escreva o número do dia juliano. Quando a chave for retornada, observe a tag para calcular o aluguel devido. Tags ausentes ou desfiguradas atraem a carga máxima. As chaves não utilizadas são armazenadas em uma bolsa (já que não é necessário selecionar nenhuma chave específica das chaves livres ao deixar um armário). Tamanho total da estrutura de dados: zero bits. Todas as partes do algoritmo são O (1).
James Youngman

Respostas:

78

Uma resposta objetiva:

Embora minha resposta inicial a essa pergunta tenha sido baseada em minha experiência empírica como estudante de Ciências da Computação e em minha opinião projetada sobre o tipo de pessoas com quem eu queria trabalhar na área de Ciências da Computação. Na verdade, existe uma resposta objetiva (com relação às opiniões subjetivas das sociedades de computação ACM SIGCSE e IEEE). A cada 10 anos, os órgãos da ACM e do IEEE cooperam em uma publicação conjunta que detalha sugestões para o currículo de graduação em ciências da computação com base no conhecimento profissional do estado da indústria da computação. Mais informações podem ser encontradas em cs2013.org . O comitê publica um relatório final listando sua recomendação curricular .

Dito isto, ainda acho que minha lista é muito boa.

Resposta original abaixo.


O que devo saber?

Mínimo

Eu acho que um programador adepto deve ter pelo menos conhecimento de graduação em Ciência da Computação. Certamente, você pode ser eficaz em muitos trabalhos com apenas um pequeno subconjunto de Ciência da Computação, devido à sólida comunidade que o CS assenta e o foco restrito da maioria das posições profissionais. Além disso, muitas pessoas se especializarão após o curso de graduação. No entanto, também não acho que seja uma desculpa para não conhecer o conhecimento básico de CS.

Para responder à pergunta do título, eis o que um estudante de graduação em CS (a base para um programador experiente) deve saber ao se formar:

Estruturas de dados

  • Representação de Dados da Máquina
    • Uns, complemento de dois e aritmética relacionada
    • Palavras, ponteiros, ponto flutuante
    • Acesso, deslocamento e manipulação de bits
  • Listas Vinculadas
  • Tabelas Hash (mapas ou dicionários)
  • Matrizes
  • Árvores
  • Pilhas
  • Filas
  • Gráficos
  • Bases de dados

Algoritmos

  • Ordenação:
    • Classificação por bolhas (para saber por que é ruim)
    • Classificação de inserção
    • Mesclar Classificação
    • Ordenação rápida
    • Classificações de estilo Radix, Classificação de contagem e Classificação de balde
    • Heap Sort
    • Classificação Bogo e Quantum (=
  • Procurando:
    • Pesquisa Linear
    • Pesquisa binária
    • Primeira pesquisa de profundidade
    • Primeira Pesquisa de Largura
  • Manipulação de String
  • Iteração
  • Árvore Traversal
  • List Traversal
  • Funções de hash
  • Implementação concreta de uma tabela de hash, árvore, lista, pilha, fila, matriz e conjunto ou coleção
  • Algoritmos de agendamento
  • Transversal e manipulação do sistema de arquivos (no nível do inode ou equivalente).

Padrões de design

  • Modularização
  • Fábrica
  • Construtor
  • Singleton
  • Adaptador
  • Decorador
  • Flyweight
  • Observador
  • Iterador
  • Estado [Máquina]
  • Model View Controller
  • Padrões de programação de encadeamento e paralelo

Paradigmas

  • Imperativo
  • Orientado a Objeto
  • Funcional
  • Declarativo
  • Programação estática e dinâmica
  • Marcação de dados

Teoria da complexidade

  • Espaços de complexidade
  • Computabilidade
  • Linguagens completas regulares, sem contexto e com máquina universal de Turing
  • Expressões regulares
  • Contagem e Combinatória Básica

Além

Para entrar no que você está perguntando mais adiante na sua pergunta, se você estiver familiarizado com o exposto acima, poderá identificar facilmente o padrão, o algoritmo e a estrutura de dados apropriados para um determinado cenário. No entanto, você deve reconhecer que geralmente não existe a melhor solução. Às vezes, pode ser necessário escolher o menor dos dois males ou simplesmente escolher entre duas soluções igualmente viáveis. Por isso, você precisa do conhecimento geral para poder defender sua escolha contra seus colegas.

Aqui estão algumas dicas para algoritmos e estruturas de dados:

  • A Pesquisa binária pode apenas (e deve) ser usada em dados classificados.
  • As classificações de estilo Radix são impressionantes, mas somente quando você tem classes finitas de coisas sendo classificadas.
  • As árvores são boas para quase tudo, assim como as Tabelas Hash. A funcionalidade de uma tabela de hash pode ser extrapolada e usada para resolver muitos problemas com o custo de eficiência.
  • Matrizes podem ser usadas para fazer backup da maioria das estruturas de dados de nível superior. Às vezes, uma "estrutura de dados" não passa de uma matemática inteligente para acessar locais em uma matriz.
  • A escolha do idioma pode ser a diferença entre arrancar os cabelos ou navegar por um problema.
  • A tabela ASCII e uma matriz de 128 elementos formam uma tabela de hash implícita (=
  • Expressões regulares podem resolver muitos problemas, mas não podem ser usadas para analisar HTML .
  • Às vezes, a estrutura de dados é tão importante quanto o algoritmo.

Algumas das opções acima podem parecer sem cérebro, e outras podem parecer vagas. Se você quiser que eu entre em mais detalhes, eu posso. Mas, minha esperança é que, ao encontrar uma pergunta mais concreta, como "Design de uma função que conte o número de ocorrências de cada caractere em uma String", você veja a dica sobre a tabela ASCII e as 128 matrizes de elementos que formam um hash implícito puro tabelas para a resposta.

Com base nessas idéias, proponho uma resposta ao problema do armário descrito em sua pergunta.


Responda ao problema colocado na sua pergunta.

Talvez essa não seja a melhor resposta para sua pergunta, mas acho que é interessante e não exige nada muito complexo. E certamente superará a complexidade de tempo do uso de uma fila ou pilha que requer tempo linear para determinar se um armário está livre ou não.

Você tem 0-999 armários. Agora, como você possui um número fixo de armários, é possível conceber facilmente uma função de hash sem colisões no intervalo de 0 a 999. Essa função é simplesmente h (x) = x mod 1000. Agora, [conceitualmente] construa uma tabela de hash com chaves inteiras e o conteúdo de uma matriz de caracteres de 1000 elementos como seus valores. Se um cliente quiser reservar o armário 78 para uso, basta colocar 78 na função hash (retornar 78) e, em seguida, adicionar esse número ao ponteiro base da matriz - armazenando um valor verdadeiro no local apontado pelo valor de deslocamento . Da mesma forma, se você precisar verificar se 78 está em uso, basta ler o valor armazenado nesse local e verificar se é verdadeiro.

Essa solução opera em tempo constante para pesquisas e armazenamento, em oposição a um armazenamento e pesquisa de tempo de log (n) no caso de uma fila prioritária apoiada por uma árvore binária. A descrição é intencionalmente detalhada, para que você possa ver os conceitos superiores sendo resumidos em um algoritmo eficiente.

Agora, você pode perguntar: e se eu precisar conhecer todos os armários disponíveis, uma fila prioritária não seria melhor? Se houver k cacifos disponíveis na fila de prioridade, a iteração sobre todos eles executará k etapas. Além disso, dependendo da implementação da fila de prioridade, talvez seja necessário reconstruir sua fila de prioridade ao analisar tudo .. o que levaria a etapas k * log (k): (k <1000). Na solução de matriz, você só precisa iterar uma matriz de 1000 elementos e verificar quais estão abertas. Você também pode adicionar uma lista disponível ou usada à implementação para verificar apenas o tempo k.

David Cowden
fonte
11
Ótima resposta! Eu também gostaria de acrescentar que você realmente deve ter certeza de usar as funções / estruturas de dados predefinidas da linguagem que está usando, por exemplo, estruturas de dados de algoritmos e stl em C ++ ou a API Java para Java.
marktani
11
Excelente! Especialmente "Expressões regulares podem resolver muitos problemas, mas não podem ser usadas para analisar HTML."
FrustratedWithFormsDesigner
2
A resposta foi boa, até o "problema" aparecer. Não há motivo para usar uma fila prioritária ou tabela de hash. Uma pilha simples é suficiente. Adicione iteração para obter a lista completa de armários gratuitos, se desejar.
Matthieu M.
11
devemos adicionar banco de dados relacional + SQL, conhecimento de árvore B +, teoria de compiladores, organização de hardware de conhecimento, conhecimento de teoria de sistemas operacionais, conhecimento de redes TCP / IP?
31512 dan_l
11
Sou cético em relação aos padrões de design. Muitos são úteis em alguns tipos de idiomas, enquanto inúteis e / ou desnecessários em outros. Você também pode adicionar Heurística em algoritmos e estruturas de dados trie e skip-list. As estruturas tradicionais de algoritmos / dados atingem um limite no acesso síncrono, mas podem ser superadas por outras abordagens não tradicionais usando vários threads e simultaneidade. As heurísticas podem diminuir drasticamente o número de pesquisas necessárias, enquanto estruturas como uma lista de ignorados permitirão que a estrutura de dados seja gravada sem um bloqueio global.
Evan Solha
6

O Manual de Design de Algoritmos de Steven S. Skiena parece ser a fonte que você está pesquisando. A segunda parte é uma lista classificada de problemas com uma revisão dos algoritmos relacionados. Existe uma versão web .

AProgrammer
fonte
3
ótimo livro, mas não pense que você precisa dominar tudo para realmente ser um programador. Eu só comprei recentemente, e eu fui pago para o programa desde 1979. (E sim, eu comprei-o acreditar que eu poderia aprender alguma coisa com ele.)
Kate Gregory
@KateGregory Comprei o livro e realmente não consegui entender porque só conheço linguagens de alto nível como Ruby e Javascript (sem árvores binárias, listas vinculadas etc.) ... acabei desistindo de lê-lo.
bigpotato
4

Não há "deveria". A. Familiarize-se com as classes básicas de complexidade (linear, logarítmica, etc.) B. Perceba que você pode fazer praticamente qualquer coisa com uma matriz simples, assim como uma estrutura de dados sofisticada, como uma árvore B. O truque na escolha da estrutura / algoritmo apropriado está no equilíbrio do desempenho, tamanho esperado da entrada e complexidade da implementação.

Depois, há coisas abstratas, mas imensamente úteis (embora a utilidade não seja imediatamente óbvia): máquinas de estados, teoria dos grafos, teoria da convexidade (programação linear, etc.).

zvrba
fonte
11
Não subestime a importância de saber quando usar o quê. Como os problemas que você resolveu usando uma matriz simples voltarão e morderão você quando estiver prestes a se envolver nesse grande cliente e descobrir que seu aplicativo que funcionou bem por anos diminui a velocidade de rastreamento apenas porque você usou uma bolha em vez de um quicksort.
Pieter B
3

O MIT publica notas de aula, vídeos, tarefas e material de exame gratuitos para Introdução aos Algoritmos . Os títulos das palestras listam os algoritmos / estruturas de dados cobertos.

Este é um consenso revisado por pares sobre o que você deve saber. Provavelmente, também é um ótimo recurso de aprendizado.

MarkJ
fonte