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?
Respuestas:
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
Algoritmos
Patrones de diseño
Paradigmas
Teoría de la complejidad
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:
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.
fuente
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 .
fuente
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.).
fuente
El MIT publica notas de clase, videos, tareas y material de examen gratuitos para Introducción a los algoritmos . Los títulos de las conferencias enumeran los algoritmos / estructuras de datos cubiertos.
Este es un consenso revisado por pares sobre lo que debe saber. Probablemente también sea un gran recurso de aprendizaje.
fuente