Mi respuesta va a ser un poco cuestionable cuando se trata del aspecto “complicado” de las cosas. Obviamente, los algoritmos “más engañosos” que he intentado descubrir son los que nunca logré descubrir cómo implementar, y nadie más lo ha hecho todavía.
Como realmente no sé cómo adivinar lo que la pregunta considera “difícil”, responderé con el algoritmo que me llevó más tiempo entender, aunque podría considerar que esto es una trampa.
Cuando estaba en octavo grado, estaba estudiando matemáticas de noveno grado por mi cuenta para no tener que dejar atrás a mis amigos para ir a la escuela secundaria. Mi maestra me daría un proyecto y luego se iría a enseñar al resto de la clase.
- En problemas de DP, ¿cómo sabe si usar una matriz / tabla 1D o una matriz / tabla 2D?
- ¿Qué tipo de datos debo usar en C para almacenar datos como a1b2c3? ¿Podría usar una matriz de caracteres para almacenar esto como una cadena?
- ¿Qué vas a aprender y en qué proyecto vas a trabajar este verano como principiante en programación?
- ¿Cuál es el mejor algoritmo de búsqueda en programación?
- ¿Cuáles son algunas de las preguntas de cadena que se hacen comúnmente en una entrevista técnica?
El siguiente tema resultó ser la programación lineal, que generalmente se enseña a ese nivel completamente sin matrices, pero ella solo me dijo que revisara esta explicación y la aplicación Java que demostraba el algoritmo simplex.
Fue mucho a la vez. Realmente no me había familiarizado demasiado con las matrices. La explicación fue muy detallada sobre la transformación del LP en una matriz, seleccionando pivotes, cómo transformar el estado, y así sucesivamente, y después de llevar la tarea a casa y pasar toda la noche jugando con ella y estudiándola, pude menos replicar el comportamiento del algoritmo a mano.
En este punto, realmente sabía muy poco sobre programación de computadoras, así que eso era lo mejor que podía hacer. Y la maestra simplemente dijo: “¡Oh, solo quería que reconocieras cómo usar las matrices y supieras qué era un programa lineal, todo esto era innecesario!”
Entonces, puse el algoritmo durante una década, y mientras tanto aprendí una o dos cosas sobre la idea de algoritmos y programas. Aprendí lo que realmente era un programa lineal. Tomé un par de clases y aprendí álgebra lineal.
Y luego Nemirovski me explicó el algoritmo simplex. Toda la idea intuitiva de ello. Por qué tiende a funcionar bastante bien solo siguiendo los bordes del politopo de nodo a nodo. Por qué es realmente malo en el peor de los casos. Sin embargo, por qué suele ser mejor que el método elipsoide.
Creo que, en este punto, si tuviera que dedicarle un poco de tiempo, podría implementar el algoritmo Simplex con un poco de revisión. Afortunadamente, nunca tendré que hacerlo.
