Dans le livre d'Andrew W. Appel, Modern Compiler Implementation in ML , il dit au chapitre 17 que la théorie de la calculabilité montre qu'il sera toujours possible d'inventer de nouvelles transformations d'optimisation et procède pour prouver qu'un compilateur entièrement optimisé résoudra le...
Certains algorithmes complexes ( union-find ) ont la fonction Ackermann inverse presque constante qui apparaît dans la complexité temporelle asymptotique, et sont optimales dans le pire des cas si le terme Ackermann inverse presque constant est ignoré. Existe-t-il des exemples d'algorithmes connus...
Dans la plupart des implémentations d'algorithmes génétiques, l'accent est mis sur le croisement et la mutation. Mais d'une manière ou d'une autre, la plupart d'entre eux laissent de côté la nature diploïde (dominante / récessive) des gènes. Dans la mesure où ma compréhension (limitée) va la nature...
Ok avant de commencer, je me rends compte que c'est en marge du sujet (j'ai lu l'aide Questions pour ce site), d'autant plus que ce n'est pas un problème réel. Pourtant: Je ne trouve rien de pertinent sur Google D'un point de vue puriste, cela doit certainement relever de l'informatique? Dans tous...
Je sais ce qu'est le calcul dans un sens vague (c'est ce que font les ordinateurs), mais j'aimerais une définition plus rigoureuse. Dictionary.comLes définitions de calcul, calcul, calcul et calcul sont circulaires, donc cela n'aide pas. Wikipediadéfinit le calcul comme «tout type de calcul qui...
Eh bien, c'est une question générale. Et si quelqu'un veut rendre l'implémentation spécifique, je préférerai les choses liées à Unix. Mais il faut d'abord connaître les problèmes suivants en général: Je lis qu'un seul processus peut avoir plusieurs threads. Plusieurs threads du même processus...
J'entends souvent que le polymorphisme des lignes est une meilleure approche que le sous-typage, mais j'ai du mal à trouver quoi que ce soit en les comparant en détail. Je suis particulièrement intéressé par la perspective d'un utilisateur du système. J'ai rencontré ce billet de blog, mais il me...
Juste par intérêt, j'ai essayé de résoudre un problème de la catégorie "récente" du projet Euler ( séquence de chiffres ). Mais je suis incapable de penser à un moyen de résoudre le problème efficacement. Le problème est le suivant (dans la séquence de questions d'origine, il y en a deux au début,...
En comparant une paire ordonnée (x, y) à une paire non ordonnée {x, y} (ensemble), puis en théorie, la différence n'est que d'un bit, car si x vient en premier ou y nécessite exactement un seul bit pour représenter. Donc, si on nous donne un ensemble {x, y} où x, y sont deux entiers 32 bits...
Un article intitulé The Derivative of a Regular Type is its Type of One-Hole Contexts montre que la "fermeture à glissière" d'un type - ses contextes à un trou - suit les règles de différenciation en algèbre de type. Nous avons:
Je recherche une structure de données qui repoussera son élément le plus ancien / le dernier si un nouvel élément est inséré. Par exemple, Dreprésentons la structure. Dcontient 3 éléments des Number Dvaleurs par défaut du type seront initialisés à 1, 2et 3. D = [ 1 , 2 , 3 ]ré=[1,2,3]D = [1, 2, 3]...
L'opérateur de différence définie (par exemple, EXCEPTdans certaines variantes SQL) est l'un des nombreux opérateurs fondamentaux de l'algèbre relationnelle. Cependant, certaines bases de données ne prennent pas directement en charge l'opérateur de différence d'ensemble, mais prennent en charge...
De nombreuses références de systèmes d'exploitation disent qu'avec le multitâche coopératif (par opposition au multitâche préemptif), un processus maintient le CPU jusqu'à ce qu'il se suspende explicitement volontairement. Si un processus en cours exécute une demande d'E / S qui ne peut pas être...
Je commence une recherche bibliographique personnelle sur les algorithmes de vérification de type et souhaite quelques conseils. Quels sont les algorithmes, stratégies et techniques générales de vérification de type les plus couramment utilisés? Je m'intéresse particulièrement aux algorithmes de...
Je travaille sur la programmation dynamique depuis un certain temps. La manière canonique d'évaluer une récursivité de programmation dynamique consiste à créer une table de toutes les valeurs nécessaires et à la remplir ligne par ligne. Voir par exemple Cormen, Leiserson et al: "Introduction to...
Il y a une réduction dans le livre de Sipser "Introduction à la théorie du calcul" à la page 286 de 3SAT au problème de chemin hamiltonien. Y a-t-il une réduction plus simple? Par plus simple, je veux dire une réduction qui serait plus facile à comprendre (pour les étudiants). Y a-t-il une...
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...
Notre professeur nous a demandé de penser à une fonction dans OCaml qui a le type 'a -> 'b c'est-à-dire une fonction d'un argument qui pourrait être n'importe quoi, et qui peut retourner un autre chose. J'ai pensé à utiliser raisedans une fonction qui ignore son argument: let f x = raise Exit...
Dans Algorithmics for Hard Problems de Hromkovič (2e édition), il y a ce théorème (2.3.3.3, page 117): Il existe un problème de décision (décidable) tel que pour chaque algorithme qui résout il existe un autre algorithme qui résout également et remplit en outreA P A ′ PPPPUNEAAPPPUNE′A′A'PPP ∀∞n ∈...
La loi de De Morgan est souvent introduite dans un cours d'introduction aux mathématiques pour l'informatique, et je le vois souvent comme un moyen de transformer les déclarations de AND en OR en niant les termes. Y a-t-il une explication plus intuitive pour expliquer pourquoi cela fonctionne...