Questions sur les méthodes et techniques générales pour prouver plusieurs théorèmes. Lorsque vous demandez la preuve d'une seule déclaration, utilisez plutôt des balises relatives à l'objet de la preuve.
Il y a beaucoup de questions sur la façon d'analyser le temps d' exécution des algorithmes (voir, par exemple, l' exécution d'analyse et d'analyse de l' algorithme ). Beaucoup sont similaires, par exemple ceux qui demandent une analyse des coûts des boucles imbriquées ou des algorithmes de division...
J'ai entendu parler de l'induction (structurelle). Il vous permet de construire des structures finies à partir de plus petites et vous donne des principes de preuve pour raisonner sur de telles structures. L'idée est assez claire. Mais qu'en est-il de la coinduction? Comment ça marche? Comment...
Il existe de nombreuses méthodes pour prouver qu'une langue n'est pas régulière , mais que dois-je faire pour prouver qu'une langue est régulière? Par exemple, si on me donne que est régulier, comment puis - je prouver que les éléments suivants L ' est régulière, aussi?LLLL′L′L' L′: = { W ∈ L : u v...
Dans la théorie de la calculabilité et de la complexité (et peut-être dans d'autres domaines), les réductions sont omniprésentes. Il en existe de nombreuses sortes, mais le principe reste le même: montrez qu'un problème est au moins aussi complexe qu'un autre problème en mappant des instances de à...
Je prévois d'enseigner un cours d'hiver sur un nombre variable de sujets, dont l'un sera les compilateurs. Maintenant, je suis tombé sur ce problème en pensant aux affectations à donner tout au long du trimestre, mais cela m'a déconcerté, je pourrais donc l'utiliser à titre d'exemple. public class...
Je comprends la preuve de l'indécidabilité du problème d'arrêt (donnée par exemple dans le manuel de Papadimitriou), basée sur la diagonalisation. Bien que la preuve soit convaincante (j'en comprends chaque étape), elle n'est pas intuitive pour moi en ce sens que je ne vois pas comment quelqu'un la...
Lorsque j'expliquais la preuve de Baker-Gill-Solovay qu'il existe un oracle avec lequel nous pouvons avoir, , et un oracle avec lequel nous pouvons avoir à un ami, une question s'est posée pour savoir pourquoi de telles techniques sont mal adaptées pour prouver le problème , et je n'ai pas pu...
J'ai un algorithme gourmand que je soupçonne peut-être correct, mais je ne suis pas sûr. Comment vérifier si c'est correct? Quelles sont les techniques à utiliser pour prouver un algorithme gourmand correct? Existe-t-il des modèles ou des techniques communs? J'espère que cela deviendra une question...
Chaque problème indécidable que je connais tombe dans l'une des catégories suivantes: Problèmes indécidables en raison de la diagonalisation (auto-référence indirecte). Ces problèmes, comme le problème d'arrêt, sont indécidables car vous pourriez utiliser un prétendu décideur pour le langage pour...
Je prends un cours de complexité et j'ai du mal à trouver des réductions entre les problèmes de PNJ. Comment puis-je trouver des réductions entre les problèmes? Y a-t-il une astuce générale que je peux utiliser? Comment dois-je aborder un problème qui me demande de prouver qu'un problème est un...
Il existe de nombreuses techniques pour prouver qu'une langue n'est pas sans contexte, mais comment puis-je prouver qu'une langue est sans contexte? Quelles techniques existe-t-il pour le prouver? De toute évidence, une façon consiste à présenter une grammaire sans contexte pour la langue....
Mon problème est de savoir comment prouver qu'une grammaire est sans ambiguïté? J'ai la grammaire suivante: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if }...
Compte tenu de tout problème de calcul, la tâche de trouver des limites inférieures pour un tel calcul est-elle vraiment possible? Je suppose que cela se résume à la façon dont une seule étape de calcul est définie et quel modèle nous utilisons pour la preuve, mais étant donné que, prouvons-nous...
J'ai deux façons de produire une liste d'articles dans un ordre aléatoire et je voudrais déterminer s'ils sont également équitables (sans biais). La première méthode que j'utilise est de construire la liste complète des éléments puis de faire un shuffle dessus (disons un shuffle de Fisher-Yates)....
La logique constructiviste est un système qui supprime la loi du milieu exclu, ainsi que la double négation, en tant qu'axiomes. C'est décrit sur Wikipedia ici et ici . En particulier, le système ne permet pas de preuve par contradiction. Je me demande, quelqu'un sait-il comment cela affecte les...
Spécifier des langues formelles en donnant des grammaires formelles est une tâche fréquente: nous avons besoin de grammaires non seulement pour décrire les langues, mais aussi pour les analyser, ou même pour faire une science appropriée . Dans tous les cas, il est important que la grammaire soit...
Je cherche des explications sur la façon dont on pourrait prouver que deux modèles de calcul sont équivalents. J'ai lu des livres sur le sujet, sauf que les preuves d'équivalence sont omises. J'ai une idée de base sur ce que cela signifie pour deux modèles de calcul d'être équivalents (la vue des...
En mathématiques, il existe de nombreuses preuves d'existence non constructives, nous savons donc qu'un certain objet existe bien que nous ne sachions pas comment le trouver. Je recherche des résultats similaires en informatique. En particulier: y a-t-il un problème que nous pouvons prouver qu'il...
Avant de lire L'Art de la programmation informatique (TAOCP) , je n'ai pas approfondi ces questions. J'utiliserais un pseudo-code pour décrire des algorithmes, les comprendre et estimer le temps d'exécution uniquement sur les ordres de croissance. Le TAOCP change complètement d'avis. TAOCP utilise...
Le théorème maître est un bel outil pour résoudre certains types de récurrences . Cependant, nous masquons souvent une partie intégrante lors de son application. Par exemple, lors de l'analyse de Mergesort, nous sommes heureusement passés de T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad...