Les machines de Turing ont un alphabet de symboles formel, une description basée sur les règles d'état et de transition de la façon dont un calcul est effectué. Le modèle d'acteur est parfois mentionné comme un modèle de calcul plus puissant que les machines de Turing (pas dans ce qu'il peut...
Je recherche un texte de référence sur la théorie des graphes appliquée et les algorithmes de graphes. Existe-t-il un texte standard utilisé dans la plupart des programmes informatiques? Sinon, quels sont les textes les plus respectés dans le domaine? J'ai Cormen et
Je suis particulièrement intéressé par les solutions au problème que la recherche encapsulée peut dépendre de l'ordre d'évaluation. Selon [1], la recherche encapsulée dans PAKCS dépend de l'ordre d'évaluation, tandis que dans MCC, elle ne le fait pas, mais son utilisation nécessite la connaissance...
Considérez le problème suivant: Soit une constante. On nous donne un tableau -ary de et . Soit .kkkkkkUNEré1× … ×rékAd1×…×dkA_{d_1\times\ldots\times d_k}000111N=∏ki = 1réjeN=∏i=1kdiN = \prod_{i=1}^k d_i Nous voulons créer une structure de données en prétraitant pour effectuer le type d'opérations...
Je recherche des applications pratiques des machines à états finis comme les machines DFA, NFA, Moore, Mealy ... Il serait utile que quelqu'un pointe vers des exemples du noyau Linux. Je sais que DFA est utilisé dans la correspondance de chaînes comme l'algorithme KMP. Quelle est la signification...
Considérez le problème d'univers suivant . Le problème de l'univers. Étant donné un ensemble fini pour une classe de langages, et un automate acceptant le langage L , décidez si L = \ Sigma ^ * .ΣΣ\SigmaLLLL=Σ∗L=Σ∗L=\Sigma^* Dans [1], il est indiqué et prouvé que le problème de l'univers est...
Ces diapositives de cours esquissent une preuve queL = {unenbn∣ n ≥ 0 } ∪ {unenb2 n∣ n ≥ 0 }L={anbn∣n≥0}∪{anb2n∣n≥0}L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \} ne peut être accepté par aucun automate déterministe à refoulement. Malheureusement, les diapositives ne donnent...
Je suis un doctorant débutant. étudiant en informatique, et j'essaie de comprendre certains articles classiques de théorie des jeux, tels que ceux de Nash, Kalai et Smorodinsky. Mais j'ai du mal à comprendre les parties mathématiques. Il semble que ces articles ont été écrits par des...
Récemment, j'ai été confronté à un problème qui m'a conduit aux questions suivantes: Existe-t-il un bon algorithme pour énumérer toutes les correspondances maximales / parfaites dans un graphique général? Existe-t-il un bon algorithme pour trouver toutes les correspondances maximales / parfaites...
Je suis un programmeur autodidacte et je code depuis 8 ans. Grâce à cette expérience, je connais déjà très bien les principes de programmation (tels que les instructions if, les classes, le polymorphisme, etc.). Cependant, je n'ai jamais appris "l'informatique", seulement la programmation. Quelles...
La classe de Nick (NC) est la classe de problèmes qui peuvent être résolus en temps poly-log en utilisant un nombre polynomial de processeurs. Je veux en savoir plus sur l'analogue exponentiel, qui couvrirait les problèmes qui peuvent être résolus en temps polynomial en utilisant un nombre...
Il y a eu beaucoup de recherches sur les algorithmes d'exclusion mutuelle - par exemple, beaucoup d'entre eux sont présentés dans des manuels classiques tels que The Art of Multiprocessor Programming , où un chapitre entier leur est consacré. Je me demande quelles sont les situations pratiques où...
Existe-t-il des applications réelles du problème de l'arbre de Steiner (STP)? Je comprends que la conception de la puce VSLI est une bonne application du STP. Y a-t-il d'autres exemples de problèmes réels que les gens peuvent suggérer qui pourraient être formulés en termes de STP? Contexte: Je...
Existe-t-il des problèmes dont la décidabilité est inconnue, mais il est certain que les problèmes sont moins difficiles que le problème
Je n'ai pas pu trouver de graphique décrivant ou de texte répondant à la question suivante: Existe-t-il une relation directe entre la complexité d'un algorithme (tel que le meilleur / pire cas de tri rapide) et la classe d'automates qui peuvent implémenter l'algorithme. Par exemple, existe-t-il une...
Question: Existe-t-il des textes d'introduction en langage formel ou en théorie du langage de programmation qui discutent de la façon de l'appliquer à l'étude de la notation optimale? En particulier, je suis intéressé à savoir quels sont les langages de pile, les arbres d'analyse et les indices, et...
Cette grammaire est récursive: Expression ::= AdditionExpression AdditionExpression ::= MultiplicationExpression | AdditionExpression '+' MultiplicationExpression | AdditionExpression '-' MultiplicationExpression MultiplicationExpression ::= Term | MultiplicationExpression '*' Term |...
Je suis nouveau dans la théorie de la complexité et je veux savoir ce qu'est la théorie de la complexité structurelle? quels problèmes les théoriciens tentent-ils de résoudre dans ce domaine et quel est son avenir? Du wikipedia: La théorie de la complexité structurelle ou simplement la complexité...