¿Qué algoritmos / estructuras de datos debo "reconocer" y conocer por nombre? [cerrado]

69

Me gustaría considerarme un programador bastante experimentado. He estado programando por más de 5 años. Sin embargo, mi punto débil es la terminología. Soy autodidacta, así que aunque sé programar, no conozco algunos de los aspectos más formales de la informática. Entonces, ¿qué algoritmos prácticos / estructuras de datos podría reconocer y conocer por nombre?

Tenga en cuenta que no estoy pidiendo una recomendación de libro sobre la implementación de algoritmos. No me importa implementarlos, solo quiero poder reconocer cuándo un algoritmo / estructura de datos sería una buena solución a un problema. Estoy pidiendo más por una lista de algoritmos / estructuras de datos que debería "reconocer". Por ejemplo, sé la solución a un problema como este:

Usted administra un conjunto de casilleros con la etiqueta 0-999. La gente viene a usted para alquilar el casillero y luego regresa para devolverle la llave del casillero. ¿Cómo construiría un software para administrar sabiendo qué casilleros son gratuitos y cuáles están en uso?

La solución sería una cola o pila.

Lo que estoy buscando son cosas como "en qué situación se debe usar un B-Tree: qué algoritmo de búsqueda se debe usar aquí", etc. Y tal vez una introducción rápida de cómo las estructuras de datos más complejas (pero comúnmente utilizadas) / Los algoritmos funcionan.

Intenté mirar la lista de Wikipedia de estructuras de datos y algoritmos, pero creo que es un poco exagerado. Entonces, ¿estoy buscando más cosas esenciales que debo reconocer?

Earlz
fuente
10
Votación para cerrar como "no constructivo". Cualquier respuesta será completamente subjetiva: no hay consenso sobre lo que uno "debería" saber.
Oded
2
¿Qué parte del problema de ese casillero requiere un pedido de entrada / salida? [pista]
Telastyn el
55
@Oded hay absolutamente una lista en la que creo que la mayoría de la gente estará de acuerdo sobre qué estructuras de datos y algoritmos debe conocer un programador bien versado.
David Cowden
66
@Oded ¿No hay consenso? ¿Qué pasa con el programa de estudios de un curso introductorio sobre algoritmos y estructuras de datos en informática? Bastante bien estandarizado y revisado por pares . Un buen punto de partida.
MarkJ
3
Solución alternativa; suponga que cobra por día y tiene un cargo máximo. Adjunte una etiqueta de papel a la llave cuando deje el casillero y escriba el número del día juliano en ella. Cuando devuelva la llave, mire la etiqueta para calcular la renta adeudada. Las etiquetas faltantes o desfiguradas atraen la carga máxima. Las claves no utilizadas se almacenan en una bolsa (ya que no es necesario seleccionar ninguna clave en particular de las teclas gratuitas al dejar un casillero). Tamaño total de la estructura de datos: cero bits. Todas las partes del algoritmo son O (1).
James Youngman

Respuestas:

78

Una respuesta objetiva:

Si bien mi respuesta inicial a esta pregunta se basó en mi experiencia empírica como estudiante CS pronto graduado y mi opinión proyectada sobre el tipo de personas con las que quería trabajar en el campo CS. En realidad, existe una respuesta objetiva (con respecto a las opiniones subjetivas de las sociedades de computación ACM SIGCSE e IEEE). Cada 10 años, los organismos de la ACM y el IEEE cooperan en una publicación conjunta que detalla sugerencias para el plan de estudios universitario de ciencias de la computación basado en el conocimiento profesional del estado de la industria de la computación. Se puede encontrar más información en cs2013.org . El comité publica un informe final que enumera sus recomendaciones curriculares .

Dicho esto, todavía creo que mi lista es bastante buena.

Respuesta original a continuación.


¿Qué debo saber?

Mínimo

Creo que un programador experto debería tener al menos conocimientos de pregrado en Informática. Claro, puede ser efectivo en muchos trabajos con solo un pequeño subconjunto de Ciencias de la Computación debido a la sólida comunidad en la que se asienta CS y al enfoque limitado de la mayoría de los puestos profesionales. Además, muchas personas se especializarán aún más después del estudio de pregrado. Sin embargo, tampoco creo que sean una excusa para no tener conocimiento de los conocimientos básicos de CS.

Para responder a la pregunta del título, esto es lo que un estudiante universitario de CS (la base para un programador experto) debe saber al graduarse:

Estructuras de datos

  • Representación de datos de la máquina
    • Unos, complemento de dos y aritmética relacionada
    • Palabras, punteros, coma flotante
    • Acceso a bits, desplazamiento y manipulación
  • Listas vinculadas
  • Tablas hash (mapas o diccionarios)
  • Matrices
  • Arboles
  • Pilas
  • Colas
  • Gráficos
  • Bases de datos

Algoritmos

  • Clasificación:
    • Bubble Sort (para saber por qué es malo)
    • Tipo de inserción
    • Ordenar fusión
    • Ordenación rápida
    • Clases de estilo Radix, ordenación de conteo y ordenación
    • Heap Sort
    • Bogo y clasificación cuántica (=
  • Buscando:
    • Búsqueda lineal
    • Búsqueda binaria
    • Profundidad primera búsqueda
    • Breadth First Search
  • Manipulación de cuerdas
  • Iteración
  • Transversal del árbol
  • Recorrido de lista
  • Funciones de hash
  • Implementación concreta de una tabla hash, árbol, lista, pila, cola, matriz y conjunto o colección
  • Algoritmos de programación
  • Sistema de archivos transversal y manipulación (en el inodo o nivel equivalente).

Patrones de diseño

  • Modularización
  • Fábrica
  • Constructor
  • Semifallo
  • Adaptador
  • Decorador
  • Peso mosca
  • Observador
  • Iterador
  • Máquina estatal]
  • Controlador de vista de modelo
  • Roscado y patrones de programación paralela

Paradigmas

  • Imperativo
  • Orientado a objetos
  • Funcional
  • Declarativo
  • Programación Estática y Dinámica
  • Marcado de datos

Teoría de la complejidad

  • Espacios Complejos
  • Computabilidad
  • Lenguajes completos de máquina de Turing regular, sin contexto y universal
  • Expresiones regulares
  • Conteo y combinatoria básica

Más allá

Para entrar en lo que está preguntando más adelante en su pregunta, si está familiarizado con lo anterior, debería poder identificar fácilmente el patrón, el algoritmo y la estructura de datos apropiados para un escenario determinado. Sin embargo, debe reconocer que a menudo no existe la mejor solución. A veces es posible que deba elegir el menor de dos males o incluso simplemente elegir entre dos soluciones igualmente viables. Debido a esto, necesita el conocimiento general para poder defender su elección contra sus compañeros.

Aquí hay algunos consejos para algoritmos y estructuras de datos:

  • La búsqueda binaria solo puede (y debe) usarse en datos ordenados.
  • Los tipos de estilo Radix son impresionantes, pero solo cuando tienes clases finitas de cosas ordenadas.
  • Los árboles son buenos para casi cualquier cosa, como lo son las Tablas Hash. La funcionalidad de una tabla hash se puede extrapolar y utilizar para resolver muchos problemas a costa de la eficiencia.
  • Las matrices se pueden usar para respaldar la mayoría de las estructuras de datos de nivel superior. A veces, una "estructura de datos" no es más que una matemática inteligente para acceder a ubicaciones en una matriz.
  • La elección del idioma puede ser la diferencia entre tirar de un cabello o navegar por un problema.
  • La tabla ASCII y una matriz de 128 elementos forman una tabla hash implícita (=
  • Las expresiones regulares pueden resolver muchos problemas, pero no se pueden usar para analizar HTML .
  • A veces, la estructura de datos es tan importante como el algoritmo.

Es posible que algunos de los anteriores no parezcan cerebros, y algunos pueden parecer vagos. Si quieres que entre en más detalles, puedo hacerlo. Pero, mi esperanza es que cuando se encuentre con una pregunta más concreta como, "Diseñe una función que cuente el número de ocurrencias de cada carácter en una Cadena", mire el consejo sobre la tabla ASCII y las matrices de 128 elementos que forman un hash implícito ordenado tablas para la respuesta.

Basado en estas ideas, propondré una respuesta al problema del casillero descrito en su pregunta.


Responda al problema planteado en su pregunta.

Puede que esta no sea la mejor respuesta a su pregunta, pero creo que es interesante y no requiere nada demasiado complejo. Y ciertamente superará la complejidad temporal del uso de una cola o pila que requiere tiempo lineal para determinar si un casillero está libre o no.

Tienes 0-999 armarios. Ahora, debido a que tiene un número fijo de casilleros, puede concebir fácilmente una función de hash sin colisiones en el rango 0-999. Esta función es simplemente h (x) = x mod 1000. Ahora, [conceptualmente] construya una tabla hash con claves enteras y el contenido de una matriz de caracteres de 1000 elementos como sus valores. Si un cliente desea reservar el casillero 78 para su uso, simplemente ponga 78 en la función hash (devuelve 78) y luego agregue ese número al puntero base de la matriz, almacenando un valor verdadero en la ubicación señalada por el valor de desplazamiento . Del mismo modo, si necesita verificar si 78 está en uso, simplemente lea el valor almacenado en esa ubicación y compárelo con verdadero.

Esta solución opera en tiempo constante para búsquedas y almacenamiento en lugar de un almacenamiento y búsqueda de tiempo de registro (n) en el caso de una cola prioritaria respaldada por un árbol binario. La descripción es intencionalmente detallada para que pueda ver los conceptos superiores resumidos en un algoritmo eficiente.

Ahora, puede preguntar, ¿qué pasa si necesito conocer todos los casilleros disponibles, no sería mejor una cola prioritaria? Si hay k casilleros disponibles en la cola de prioridad, iterar sobre todos ellos tomará k pasos. Además, dependiendo de la implementación de su cola prioritaria, es posible que tenga que reconstruir su cola prioritaria a medida que lo mira todo ... lo que tomaría k * log (k): (k <1000) pasos. En la solución de matriz, solo tiene que iterar una matriz de 1000 elementos y verificar cuáles están abiertos. También puede agregar una lista disponible o usada a la implementación para registrar solo k tiempo.

David Cowden
fuente
1
¡Gran respuesta! También me gustaría agregar, que realmente debe confiar en el uso de las funciones / estructuras de datos predefinidas del lenguaje que está utilizando, por ejemplo, estructuras de datos de algoritmos y stl en C ++, o la API de Java para Java.
marktani
1
¡Excelente! Especialmente "Las expresiones regulares pueden resolver muchos problemas, pero no pueden usarse para analizar HTML".
FrustratedWithFormsDesigner
2
La respuesta fue buena, hasta que apareció el "problema". No hay ninguna razón, en absoluto, para usar una cola prioritaria o una tabla hash. Una pila simple es suficiente. Agregue iteración para obtener la lista completa de casilleros gratuitos si lo desea.
Matthieu M.
1
¿Deberíamos agregar una base de datos relacional + SQL, conocimiento del árbol B +, teoría del compilador, conocimiento de la organización del hardware, conocimiento de la teoría del sistema operativo, conocimiento de las redes TCP / IP?
dan_l
1
Soy escéptico sobre los patrones de diseño. Muchos son útiles en algunos tipos de idiomas, mientras que son inútiles y / o innecesarios en otros. También es posible que desee agregar Heurística bajo algoritmos, y las estructuras de datos trie y skip-list. Las estructuras de datos / algoritmos tradicionales alcanzan un límite en el acceso sincrónico, pero pueden ser superados por otros enfoques no tradicionales que utilizan múltiples hilos y concurrencia. La heurística puede disminuir drásticamente el número de búsquedas necesarias, mientras que estructuras como una lista de omisión permitirán escribir en la estructura de datos sin un bloqueo global.
Evan Plaice
6

El Manual de diseño de algoritmos de Steven S. Skiena parece ser la fuente que está buscando. La segunda parte es una lista clasificada de problemas con una revisión de los algoritmos relacionados. Hay una versión web .

Un programador
fuente
3
gran libro, pero no sienta que tiene que dominarlo todo para ser realmente un programador. Lo compré recientemente, y me han pagado para programar desde 1979. (Y sí, lo compré creyendo que podría aprender algo de él.)
Kate Gregory
@KateGregory Compré el libro y realmente no pude entenderlo porque solo conozco lenguajes de alto nivel como Ruby y Javascript (sin árboles binarios, listas enlazadas, etc.) ... finalmente dejé de leerlo.
bigpotato
4

No hay "debería". A. Familiarícese con las clases básicas de complejidad (lineal, logarítmica, etc.) B. Tenga en cuenta que puede hacer casi cualquier cosa con una matriz simple como puede hacerlo con una estructura de datos elegante como un árbol B. El truco para elegir la estructura / algoritmo apropiado radica en equilibrar el rendimiento, el tamaño de entrada esperado y la complejidad de la implementación.

Luego hay cosas abstractas pero inmensamente útiles (aunque la utilidad no es inmediatamente obvia): máquinas de estado, teoría de grafos, teoría de convexidad (programación lineal, etc.).

zvrba
fuente
1
No subestimes la importancia de saber cuándo usar qué. Debido a que esos problemas que resolvió usando una matriz simple volverán y lo morderán justo cuando esté a punto de lanzarse en ese gran cliente y descubrir que su aplicación que funcionó bien durante años se ralentiza a un rastreo solo porque usó un bubbleort en lugar de Una clasificación rápida.
Pieter B