Existe-t-il un langage "naturel" indécidable? par "naturel", j'entends un langage défini directement par les propriétés des chaînes, et non via des machines et leurs équivalents. En d'autres termes, si le langage ressemble à où est un TM, DFA (ou regular-exp), PDA (ou grammaire), etc., alors n'est...
Il y a eu beaucoup de battage médiatique sur les compilateurs JIT pour des langages comme Java, Ruby et Python. En quoi les compilateurs JIT sont-ils différents des compilateurs C / C ++, et pourquoi les compilateurs sont-ils écrits pour Java, Ruby ou Python appelés compilateurs JIT, alors que les...
Dans une question précédente, il y avait une définition des arbres à poids équilibré et une question concernant les arbres rouge-noir. Cette question est de poser la même question, mais pour les arbres AVL . La question est, étant donné la définition d' arbres à μμ\mu équilibré comme dans l'autre...
Je comprends la théorie derrière les réseaux bayésiens et je me demande ce qu'il faut pour en construire un en pratique. Disons pour cet exemple, que j'ai un réseau bayésien (dirigé) de 100 variables aléatoires discrètes; chaque variable peut prendre jusqu'à 10 valeurs. Est-ce que je stocke tous...
Cette question a été migrée à partir de la bourse théorique de l'informatique, car elle peut être répondue sur la bourse de la science informatique. Migré il y a 7 ans . Je recherche des théories mathématiques qui traitent de la description des langages formels (ensemble de chaînes) en général et...
Soit g=(V,E)G=(V,E)G=(V,E) un graphe complet, pondéré et non orienté. Nous construisons un deuxième graphe en ajoutant un à un les arêtes de à . Nous ajoutons des arêtes à au total.E E ′ Θ ( | V | ) G ′g′= ( V, E′)g′=(V,E′)G'=(V, E')EEEE′E′E'Θ ( | V| )Θ(|V|)\Theta(|V|)g′g′G' Chaque fois que nous...
Étant donné une grammaire sans contexte G, il existe un automate N non déterministe à refoulement qui accepte exactement le langage que G accepte. (et vice versa) Il peut également exister un automate déterministe à refoulement qui accepte exactement le langage que G accepte également. Cela dépend...
Les algorithmes de tri génériques prennent généralement un ensemble de données à trier et une fonction de comparaison qui peut comparer deux éléments individuels. Si le comparateur est une relation d'ordre¹, la sortie de l'algorithme est une liste / tableau trié. Je me demande si les algorithmes de...
Une machine de Turing qui revient à un état rencontré précédemment avec sa tête de lecture / écriture sur la même cellule de la même bande exacte sera prise en boucle. Une telle machine ne s'arrête pas. Quelqu'un peut-il donner un exemple d'une machine sans arrêt qui ne boucle...
J'ai étudié quelque chose sur la complexité de Kolmogorov , lu des articles et des livres de Vitanyi et Li et utilisé le concept de la distance de compression normalisée pour vérifier la stilométrie des auteurs (identifier comment chaque auteur écrit des textes et des documents de groupe par leur...
En lisant la réponse d' Uday Reddy à Quelle est la relation entre les foncteurs en SML et la théorie des catégories? États Uday La théorie des catégories ne sait pas encore comment gérer les fonctions d'ordre supérieur. Un jour, ce sera le cas. Comme je pensais que la théorie des catégories pouvait...
La programmation fonctionnelle utilise des structures de données persistantes et des objets immuables. Ma question est pourquoi est-il crucial d'avoir de telles structures de données ici? Je veux comprendre à un bas niveau ce qui se passerait si la structure des données n'était pas persistante? Le...
Selon cette page , l'algorithme de Dijkstra est simplement BFS avec une file d'attente prioritaire. Est-ce vraiment aussi simple que cela? Je crois que
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...
Ce que je veux faire, c'est transformer un problème mathématique que j'ai en un problème de satiabilité booléenne (SAT), puis le résoudre à l'aide d'un solveur SAT. Je me demande si quelqu'un connaît un manuel, un guide ou quelque chose qui m'aidera à convertir mon problème en une instance SAT....
En matière de conception d'algorithmes, on utilise souvent les techniques suivantes: Programmation dynamique La stratégie gourmande Diviser et conquérir Alors que pour les deux premières méthodes, il existe des fondements théoriques bien connus, à savoir le principe de l'optimalité de Bellman et la...
Cette question a été migrée depuis Stack Overflow car il est possible d'y répondre sur Computer Science Stack Exchange. Migré il y a 5 ans . J'apprends toujours la programmation fonctionnelle (avec f #) et j'ai récemment commencé à lire sur les expressions de calcul. Je ne comprends toujours pas...
J'aimerais commencer la question en disant que je suis programmeur et que je n'ai pas beaucoup d'expérience en théorie de la complexité. Une chose que j'ai remarquée est que bien que de nombreux problèmes soient NP-complets, lorsqu'ils sont étendus à des problèmes d'optimisation, certains sont...
Il est bien connu que l'inférence de type Hindley-Milner (le -calculus simplement typé avec polymorphisme) a une inférence de type décidable: vous pouvez reconstruire des types de principe pour n'importe quel programme sans aucune annotation.λλ\lambda L'ajout de classes de style Haskell semble...
Peut-être que ma compréhension limitée du sujet est incorrecte, mais c'est ce que je comprends jusqu'à présent: La programmation fonctionnelle est basée sur Lambda Calculus, formulée par Alonzo Church. La programmation impérative est basée sur le modèle de machine Turing, fabriqué par Alan Turing,...