Estrategias para despegarse en la comprensión de TCS

19

Soy un estudiante graduado que está tomando un curso de teoría de la computación y tengo serios problemas para producir contenido una vez que me lo piden. Puedo seguir el libro de texto (Introducción a la teoría de la computación de Michael Sipser) y las conferencias; sin embargo, cuando se me pide que pruebe algo o que presente una descripción formal de una TM específica, simplemente me ahogo.

¿Qué puedo hacer en tales situaciones? Supongo que mi problema es comprender completamente los conceptos abstractos hasta el punto en que realmente pueda usarlos. ¿Existe una forma estructurada de abordar un concepto nuevo y abstracto y, finalmente, desarrollar la intuición?

trigoman
fuente
55
me gana Esta parece una pregunta razonable para este sitio.
Suresh
44
Yo voté para cerrar. El problema principal que veo es que la pregunta no es realmente acerca de la informática; Se trata de cómo aprender informática. Este último no tiene una respuesta objetiva, porque cada persona tendrá su mejor manera. Los tres votos para cerrar están asignados a la razón "demasiado localizada", pero creo que esta pregunta también está fuera de tema, ya que no se trata de informática.
Carl Mummert
1
Creo que esta pregunta tiene mérito y es el tipo de pregunta con la que lucho intensamente. Creo que obtener orientación sobre este tipo de problemas de una comunidad confiable es algo con lo que muchos estudiantes de CS luchan. Sin embargo, entiendo la objeción a la pregunta. Sin embargo, me parece que la pregunta es bastante apropiada para la sección meta de este sitio.
BrotherJack
66
@CarlMummert: Cada pregunta sobre informática es una pregunta sobre cómo aprender informática.
JeffE
2
La pregunta es demasiado amplia en su forma actual. Enfoque su pregunta, por ejemplo, solicite recursos (por ejemplo, libros de problemas) para ayudarlo a mejorar su capacidad de resolver preguntas en el curso, o si tiene un ejemplo específico, enfóquese en ese problema y pregunte acerca de la intuición o los métodos para abordar problemas similares.
Kaveh

Respuestas:

15

La abstracción es básicamente pan y mantequilla en informática, pero desafortunadamente es difícil de enseñar explícitamente.

En mi opinión, comprender los conceptos es más importante que poder calcular o probar cosas mecánicamente. Claro, necesita conocer algunos métodos elementales, pero la carne se encuentra en otra parte.

En primer lugar, debes comprender el contenido hasta cierto punto. Con este fin, he encontrado útil hacer la siguiente pregunta cada vez que algo no está claro para usted:

  • ¿Por qué estamos haciendo esto?
  • ¿Para qué vamos a usar esto?
  • ¿Con qué cosas similares se relaciona esto?
  • ¿Cómo lo explican otras fuentes ?
  • ¿Qué es exactamente lo que no entiendo?

Después de que haya respondido estas preguntas (o descubierto preguntas de seguimiento y las haya tratado de la misma manera) y aún tenga problemas, vaya a sus maestros (o aquí). A estas alturas ya debería ser capaz de formular una pregunta enfocada y formulada con precisión; responder a esas preguntas es el trabajo de sus maestros (y la filosofía de StackExchange).

Aparte de eso, es ejercicio y experiencia. Intente reproducir pruebas después de haberlas leído; Tenga cuidado de no aprenderlos de memoria, pero destile las ideas importantes de ellos. Después de un tiempo, debería poder reproducir todas las pruebas básicas rellenando los espacios entre los pasos principales. Incluso más tarde, comenzará a ver patrones en declaraciones y pruebas. Así es como la gente mira un enunciado y dice "Oh sí, claro, usa el método X con el teorema Y y luego usa Z para obtener lo que quieres". Es el reconocimiento de patrones alimentado por años de entrenamiento. Se paciente.

En cuanto a los ejercicios básicos, ve y encuentra libros de texto con algunos. Fuera de mi cabeza me puedo referir a Matemáticas concretas de Graham, Knuth y Patashnik. Este libro no es solo una valiosa caja de herramientas para informáticos, también contiene muchos ejercicios con soluciones (!). Recuerde intentar resolverlos antes de buscar las respuestas y reproducir las respuestas que tenía que buscar.

Otro libro útil es Introducción a los algoritmos de Cormen, Leiserson, Rivest y Stein. Se incluye un capítulo considerable sobre conceptos básicos matemáticos. También contiene muchos ejercicios; Las soluciones están disponibles a través de la página vinculada (Contenido complementario). También hay una video conferencia de uno de los autores que puede ir muy bien con el libro.

Para conferencias introductorias sobre pruebas, eche un vistazo a Pruebas de álgebra lineal en la Academia Khan . No los he visto, pero espero que sean básicos y útiles. Hay muchas más pruebas sobre Khan Academy; Me imagino que las pruebas de álgebra lineal podrían adaptarse mejor a la informática. No dudes en mirar a los demás también.

Rafael
fuente
77
Estoy de acuerdo en que comprender los conceptos es más importante que la capacidad de calcular o probar cosas. Pero la comprensión es el resultado de la práctica con cálculos y pruebas, no un sustituto de esa práctica.
JeffE
Gracias por la visión de usted. Seguiré tu consejo y trataré de mejorar en base a eso.
trigoman
Para necesidades más básicas, el Libro de Prueba puede ser una referencia valiosa.
Raphael
8

A veces descubro que las personas a las que no les va bien en teoría, simplemente tienen los conceptos básicos incorrectos (en las primeras 1-3 conferencias, pensaron que el material es muy fácil, por lo que no prestaron demasiada atención, pero luego, en la conferencia 5-7 las cosas se aceleran y es demasiado tarde para recapitular).

Como dijo @fbernardo, podría ser una buena idea comenzar desde el principio. NO tan lejos como FLA (no sirve de nada cuando se estudia TC, en mi humilde opinión), pero definitivamente abra Sipser y comience a resolver las preguntas una por una, por su orden. Con la experiencia obtendrá intuición y herramientas básicas que son imprescindibles para conceptos más avanzados.

Si no puede hacer frente a las preguntas básicas de Sipser del primer capítulo (no a los capítulos de autómatas, si estudia en TM), es posible que le falten conceptos aún más fundamentales, como métodos de prueba básicos (inducción, etc.) o conjunto básico. teoría y matemática discreta.

Buena suerte, de todos modos!

Sonó.
fuente
3

Mi único consejo sería que empieces desde el principio. En mi curso también usamos el libro de Sipser, en mi opinión es un buen libro. Pero tenemos un curso antes de TC, llamado FLA (Formal Languages ​​an Automaton) que dio una mejor intuición y experiencia en TC. Entonces, nuevamente, todos aprenden a diferentes ritmos, y usted tiene un libro muy bueno. Cualquier otra pregunta específica siempre puede encontrar ayuda aquí. :)

fbernardo
fuente
2

Hace una pregunta general en su título y luego al menos dos puntos básicos / específicos en la pregunta, y creo que hay buenas respuestas (separadas) para cada una:

  • como probar cosas
  • crear una descripción formal del comportamiento de un TM

Aquí abordamos solo el primer elemento (que es inherentemente amplio y lo merece): su tipo de elefante en la sala de educación STEM (ciencia, tecnología, ingeniería, matemáticas) que se acorta y a menudo se pasa por alto en un grado asombroso . Puede parecer que nadie sabe realmente cómo enseñar a construir pruebas. Este subj comienza en las clases de geometría, trigonometría y cálculo, pero rara vez es un elemento estricto. la mayoría de los maestros lo tratan como opcional. Parece que una clase entera dedicada a "cómo probar cosas" sería una adición o cambio excelente o incluso crítico a la educación STEM.

Aquí hay algunas referencias que encontré en una búsqueda rápida de cómo probar cosas, y creo que hay muchos otros buenos recursos. Hoy en día también es probable que haya muchos videos sobre el tema que podrían aparecer a través de búsquedas, pero no he visto una buena organización integral de videos de tipo "cómo probar cosas".

Una parte clave de la prueba es dominar los conceptos básicos de las matemáticas y usarlo todo como herramientas o piezas de construcción. Por ejemplo, saber qué es un conjunto, qué es una tupla, cuál es la diferencia / similitud, cuándo usaría uno pero no el otro, etc.

Otro enfoque es tratarlo como un simulacro. Practique muchas pruebas por su cuenta, comenzando de fácil a difícil (ojalá supiera de más libros como este, parece que no hay muchos).

vzn
fuente
1
Agregue el clásico "Cómo resolverlo" de Pólya. También es útil (especialmente para los graduados) buscar escritura matemática, por ejemplo, Knuth et al "Escritura matemática". Esta es una habilidad que a menudo se da por sentado.
vonbrand