El momento ‘eureka’ real de encontrar la solución fue satisfactorio. Mi supervisor ya sospechaba que se podía encontrar un algoritmo más rápido que el existente, y había estado leyendo los trabajos de investigación existentes y trabajando para comprender las matemáticas por un tiempo, pero en el momento en que me di cuenta de que entendía cómo hacerlo. llegó cuando estaba manejando mi bicicleta a casa desde la universidad y tuve una repentina explosión de inspiración. Llegué a casa, comencé a dibujar algunas visualizaciones crudas, y sí, esto iba a funcionar.
Decidí que la forma obvia de verificar si mi idea era correcta sería simplemente programarlo en C ++ y probarlo. Yo mismo programé cada parte del algoritmo: mi solución requería usar un árbol AVL como estructura de datos, que implementé desde cero por alguna razón. Esta también fue una parte muy satisfactoria de la experiencia porque pude realizar experimentos que mostraban cuánto más rápido era el algoritmo en la práctica, en lugar de solo en teoría.
Entonces comenzó el trabajo duro. Tuve que escribir un trabajo de investigación sobre esto, así que pasé mucho tiempo jugando con LaTeX para escribir las ecuaciones matemáticas detalladas e intentar que las imágenes terminaran donde las quería. Esto fue seguido por aún más tiempo dedicado a revisar el documento, por lo que sería claro y de la longitud correcta para ser presentado a una conferencia. En realidad, escribir las cosas fue mi parte menos favorita de inventar un algoritmo, aunque también es la parte más importante.
- ¿Qué criterios se utilizan para contar un buen algoritmo?
- ¿Cuál es la diferencia principal entre algoritmo y pseudocódigo?
- ¿Cuántas veces se realiza la comparación [código] i> = n [/ código] en el siguiente programa? [código] int i = 200, n = 110; main () {while (i> = n) {i = i-1; n = n + 1;}} [/ código]
- ¿Cuál es la forma más rápida de encontrar divisores de enteros grandes?
- ¿Cuál es el algoritmo de tiempo polinómico de peor caso de más rápido crecimiento utilizado en la práctica?
Luego, inmediatamente después de hacer eso, hice mi tesis de maestría sobre la generalización del algoritmo a más de 2 dimensiones, y pude experimentar esto de nuevo. Un momento divertido durante mi tesis de maestría fue cuando le estaba contando a mi supervisor cómo planeaba generalizar el algoritmo para trabajar en dimensiones superiores, pero no estaba logrando explicarlo claramente, así que terminamos construyendo una visualización tridimensional fuera de legos en su oficina. En cierto modo, eso significa que inventar mi propio algoritmo fue como jugar con legos. Bastante divertido, y puedes construir cosas.
