Stratégies pour se décoller de la compréhension du SDC

Je suis un étudiant diplômé suivant un cours de théorie du calcul et j'ai de la difficulté à produire du contenu une fois qu'on me le demande. Je suis en mesure de suivre le manuel (Introduction à la théorie du calcul de Michael Sipser) et les conférences; Cependant, lorsqu'on me demande de prouver quelque chose ou de proposer une description formelle d'une MT spécifique, je m'étouffe.

Que puis-je faire dans de telles situations? Je suppose que mon problème est de comprendre pleinement les concepts abstraits au point que je peux réellement les utiliser. Existe-t-il une manière structurée d'aborder un nouveau concept abstrait et éventuellement de construire une intuition?

L'abstraction est à peu près du pain et du beurre en informatique, mais malheureusement, il est difficile d'enseigner explicitement.

À mon avis, la compréhension des concepts est plus importante que la capacité de calculer ou de prouver mécaniquement des choses. Bien sûr, vous devez connaître vos méthodes élémentaires, mais la viande se trouve ailleurs.

Tout d'abord, vous devez saisir le contenu dans une certaine mesure. À cette fin, j'ai trouvé utile de poser la question suivante chaque fois que quelque chose n'est pas clair pour vous:

• Pourquoi on fait ça?
• Pourquoi allons-nous l'utiliser?
• Qu'est - ce que les choses semblables est le lien?
• Comment d' autres sources l' expliquent-elles?
• Qu'est- ce que je ne comprends pas exactement ?

Après avoir répondu à ces questions (ou découvert des questions de suivi et les avoir traitées de la même manière) et que vous avez toujours des problèmes, allez voir vos professeurs (ou ici). Vous devriez maintenant être en mesure de formuler une question ciblée et formulée avec précision; répondre à ces questions est le travail de vos enseignants (et la philosophie de StackExchange).

À part cela, c'est de l'exercice et de l'expérience. Essayez de reproduire les épreuves après les avoir lues; veillez à ne pas les apprendre par cœur mais distillez-en les idées importantes. Après un certain temps, vous devriez être en mesure de reproduire toutes les épreuves de base en remplissant les espaces entre les étapes principales. Même plus tard, vous commencerez à voir des modèles dans les déclarations et les preuves. C'est ainsi que les gens regardent une déclaration et disent "Oh oui, bien sûr, utilisez la méthode X avec le théorème Y et utilisez simplement Z pour obtenir ce que vous voulez.". C'est une reconnaissance des formes alimentée par des années de formation. Sois patient.

Quant aux exercices de base, allez chercher des manuels avec certains. Du haut de ma tête, je peux me référer à Concrete Mathematics de Graham, Knuth et Patashnik. Ce livre n'est pas seulement une précieuse boîte à outils pour les informaticiens, il contient également de nombreux exercices avec des solutions (!). N'oubliez pas de tenter de les résoudre avant de rechercher les réponses et de reproduire les réponses que vous avez dû rechercher.

Un autre livre utile est Introduction aux algorithmes de Cormen, Leiserson, Rivest et Stein. Inclus est un chapitre important sur les bases mathématiques. Il contient également de nombreux exercices; les solutions sont disponibles via la page liée (Contenu supplémentaire). Il y a aussi une conférence vidéo par l'un des auteurs qui peut bien aller avec le livre.

Pour les conférences d'introduction concernant les preuves, jetez un œil aux preuves d'algèbre linéaire sur Khan Academy . Je ne les ai pas regardés, mais j'espère qu'ils sont à la fois basiques et utiles. Il y a beaucoup plus de preuves sur Khan Academy; Je pense simplement que les preuves d'algèbre linéaire pourraient convenir le mieux à l'informatique. N'hésitez pas non plus à regarder les autres.

Je découvre parfois que les gens qui ne réussissent pas bien en théorie ont juste les bases erronées (sur les 1 à 3 premières conférences, ils pensaient que le matériel était très facile, donc ils n'y ont pas prêté trop d'attention, mais ensuite, à la conférence 5-7, les choses s'accélèrent et il est trop tard pour récapituler).

Comme l'a dit @fbernardo, ce pourrait être une bonne idée de recommencer depuis le début. PAS aussi loin que FLA (cela ne sert à rien lorsque vous étudiez TC, IMHO), mais ouvrez Sipser et commencez à résoudre les questions une par une, selon leur ordre. Avec l'expérience, vous obtiendrez l'intuition et les outils de base qui sont impératifs pour les concepts plus avancés.

Si vous ne pouvez pas répondre aux questions de base de Sipser du premier chapitre (pas aux chapitres des automates, si vous étudiez les MT), alors vous pourriez manquer de concepts encore plus fondamentaux, tels que les méthodes de preuve de base (induction, etc.) ou l'ensemble de base - théorie et mathématiques discrètes.

Bonne chance quand même!

Mon seul conseil serait de recommencer depuis le début. Dans mon cours, nous utilisons aussi le livre de Sipser, c'est un bon livre à mon avis. Mais nous avons un cours avant TC, nommé FLA (Formal Languages ​​an Automaton) qui a donné une meilleure intuition et un meilleur contexte sur TC. Donc, encore une fois, tout le monde apprend à des rythmes différents, et vous avez un très bon livre. Pour toute autre question spécifique, vous pouvez toujours trouver de l'aide ici. :)

Vous posez une question générale dans votre titre, puis au moins deux points de base / spécifiques dans la question, et je pense qu'il y a de bonnes réponses (distinctes) à chacune:

• comment prouver des trucs
• créer une description formelle du comportement d'une MT

Ici, abordant uniquement le 1er élément (qui est intrinsèquement large et le mérite) - son genre d'éléphant dans la salle de l'enseignement des STEM (science, technologie, ingénierie, mathématiques) qui obtient une courte durée et est souvent passé sous silence à un degré stupéfiant . Il peut sembler que personne ne sache vraiment comment apprendre à construire des preuves. Ce sujet commence dans les classes de géométrie, de trigonométrie et de calcul, mais en est rarement un élément strict. la plupart des enseignants la considèrent comme facultative. Il semble qu'une classe entière consacrée à «comment prouver des choses» serait un excellent ou même un changement ou un changement critique dans l'enseignement des STEM.

Voici quelques références que j'ai trouvées sur une recherche rapide pour prouver des choses, et je pense qu'il existe de nombreuses autres bonnes ressources. De nos jours, il y a aussi probablement beaucoup de vidéos sur le sujet qui pourraient être tournées via des recherches, mais je n'ai pas vu une belle organisation complète de vidéos de type "comment prouver des choses".

Un élément clé de la démonstration est de maîtriser les bases des mathématiques et de tout utiliser comme outils ou éléments de construction. Par exemple, savoir ce qu'est un ensemble, ce qu'est un tuple, quelle est la différence / similitude, quand vous utiliseriez l'un mais pas l'autre, etc.

Une autre approche consiste à le traiter comme une perceuse. Faites de nombreuses épreuves par vous-même, de facile à difficile (j'aurais aimé avoir plus de livres comme celui-ci, il ne semble pas y en avoir beaucoup).

• Book of Proof de Richard Hammack - excellente référence en ligne gratuite qui présente la distribution de base des personnages et des techniques, etc.

• Comment le prouver, une approche structurée par Velleman

• Preuves et réfutations par Imre Lakatos - un vieux classique sur le sujet qui met l'accent sur l'approche itérative et évolutive de la preuve

• Preuves et théorèmes pour les nuls - une page Web de la série de livres pour les nuls

• Comment faire des preuves mathématiques, wikihow