algorithm - sort - ¿Cómo “entiendes” cuando se trata de pruebas?
quicksort peor caso (7)
Comenzaré con mi respuesta admitiendo que, como estudiante de CS, me fue muy difícil entender una forma formal de pensar, y nunca es fácil, a menos que tenga talento para ello.
Me temo que no hay mejor respuesta que practicar y estudiar .
Una forma matemática y algorítmica formal de pensar y visualizar problemas es una habilidad que primero exige una comprensión muy profunda de los temas con los que está tratando. Segundo, requiere que usted tenga un buen conocimiento de las pruebas existentes. Trata de imaginarte a ti mismo como algunos de los grandes científicos que inventaron los algoritmos que estás estudiando. Comprende cómo habrías tratado de abordar ese problema específico. Luego veremos cómo demostraron la corrección de su algoritmo.
Solo puedo recomendar el mejor libro de texto sobre este tema, que es Introducción a los algoritmos de CLRS . Si lo haces de principio a fin, incluyendo cada ejercicio, mejorarás tus habilidades.
Cuando comenzamos a involucrarnos en el diseño de algoritmos y en temas informáticos más discretos, terminamos teniendo que probar cosas todo el tiempo. Cada vez que veo a alguien preguntar cómo llegar a ser realmente bueno en las pruebas, la respuesta común (y posiblemente perezosa) es "práctica".
Practicar está bien si tienes lo básico, pero ¿cómo te metes en la mente para las pruebas matemáticas? ¿Cuándo hizo clic la inducción? ¿Qué recursos son los mejores para enseñar estos temas? ¿Qué temas básicos deben investigarse antes de dedicarse a la redacción de pruebas?
La práctica es realmente la única manera, pero puede ayudarse también leyendo pruebas. No tocaré la práctica porque los otros respondedores han cubierto todo lo que puedo pensar, así que solo hablaré de lo que quiero decir con la lectura.
A los libros de texto les gusta mucho escribir las pruebas "importantes". Es muy bonito, porque a menudo son declaraciones muy poderosas y son realmente elegantes. Pero así como no debes aprender a ser un gimnasta de clase mundial desde el día 1 al emular a un atleta olímpico (ya que, probablemente, te romperás la columna vertebral), no deberías leer pruebas realmente importantes (al principio). Lo que encontré fue útil al leer pruebas más pequeñas, generalmente de las tareas devueltas (supongo que eres un estudiante) o, ocasionalmente, un libro de texto que alienta.
La razón por la que creo que la lectura de las pruebas es útil es porque hay un pequeño conjunto de "trucos" o "ideas" que constituyen enormes trozos de pruebas de trabajo escolar, e incluso más avanzadas. Las cualidades de la estructura de los datos y las relaciones de recurrencia generalmente involucran pensamiento relacionado con la prueba por inducción , las pruebas que involucran computabilidad con máquinas de estados finitos a veces usan el principio de casillero , y más raramente la idea de diagonalización (muy poco frecuente, no se preocupe por eso). Y, por supuesto, casi todas las demás pruebas usan prueba por contradicción . Estoy seguro de que hay otras herramientas útiles que han pasado por mi mente, pero espero que se te ocurra.
Averiguar cuándo, cómo y por qué abordaría un problema con un método u otro particular es lo que requiere práctica y experiencia. Le sugiero que lea las pruebas además de la práctica porque a menudo puede mostrarle formas creativas de usar un método de prueba que ya ha encontrado.
Como nota final, trate de recordar cuándo aprendió a programar por primera vez. ¿Cómo te mejoraste? Probar cosas y programar cosas no son muy diferentes, en mi opinión. :)
La práctica y el estudio tienen perfecto sentido, de acuerdo. Algunos trucos, que me parecieron útiles:
- Tome notas de todo lo que estudia (solo he intentado leer libros; se pasa una gran cantidad de material).
- Además del punto anterior: haga todas (o la mayoría) las pruebas por su cuenta, use las notas de lectura / lectura como guía; muchas pruebas contienen frases como "podemos ver ahora, ese XXX". Y XXX no es siempre una conclusión trivial.
- Hacer ejercicios por ejemplo, en el libro CLRS hay docenas de ejercicios. Los ejercicios son una buena manera de obtener las ideas detrás de los algoritmos / pruebas correctas.
- Si desea comprender mejor los aspectos internos del algoritmo, considere participar en concursos de programación en línea como el de UVa''s .
Me temo que "practicar" realmente es la mejor respuesta aquí.
Es muy similar a la programación: una vez que lo aprendes, encuentras patrones que resuelven los problemas particularmente bien y puedes crear una imagen del diseño de alto nivel de sistemas novedosos que nunca habías implementado antes. Sin embargo, los programadores neófitos no son conscientes de los patrones: piratean el código hasta que tropiezan accidentalmente con alguna solución que parece "funcionar".
Cuando se le presenta un problema para probar, generalmente puede identificar propiedades ("¿Tengo un conjunto de objetos distintos?", "¿Estoy generando permutaciones?", "¿Estoy buscando minimizar / maximizar algún valor?", Etc. ). Tarde o temprano, las pruebas se agruparán en un grupo vagamente similar, donde las técnicas utilizadas para resolver un problema pueden aplicarse fácilmente a variaciones novedosas.
Lectura recomendada:
- El manual de diseño de algoritmos de Steven Skiena.
No están siendo perezosos, la práctica es la única manera. Tome clases en las que tenga que hacer pruebas y busque en línea notas de clase y exámenes antiguos con respuestas de otras universidades que revisen pruebas.
No tengo idea. Probablemente de la misma manera en que te vuelves bueno componiendo música.
Cuando trato de probar algo, no estoy siguiendo una estrategia fija, solo pienso en el problema. Luego [tiempo indefinido] más tarde, mi mente devuelve un resultado y brinco para anotarlo.
Pero practicar definitivamente ayuda. Cuando comencé a tratar de probar afirmaciones extremadamente simples, como las leyes de DeMorgan, estaba completamente desesperanzado. Así que me senté e hice los cincuenta o más problemas de ejemplo opcionales en una hoja de trabajo que nos dieron. Ahora se siente natural probar algo.
Te metes en la mente para hacer pruebas matemáticas al convertirte en matemático. No me refiero a la última afirmación de forma tautológica, pero me doy cuenta de que una prueba matemática, tal como se publicó en una revista matemática, es algo así como un artefacto retórico; es decir, es una prueba porque un grupo de matemáticos está de acuerdo en que es una prueba. Idealmente, todos los argumentos de la prueba podrían reducirse a la lógica simbólica, pero no es así como se hace en la práctica. El fracaso total de las pruebas generadas por computadora para hacer matemáticas valiosas proporciona alguna evidencia de esto.
Me meto en la mente al hacer pruebas y hacer que sean aceptadas por otros matemáticos. Estoy de acuerdo con los demás en que la "práctica" es esencial. Usted no hace pruebas a menos que lo intente, lo intente y lo intente. A menudo la luz amanece lentamente.
Los mejores recursos son, por supuesto, otros matemáticos y pruebas de lectura. Hay muy pocos, si es que alguno, puede hacer verdaderas pruebas matemáticas sin ser parte de la comunidad matemática.