Je suis en train de lire sur le calcul lambda pour "apprendre à le connaître". Je le vois comme une forme alternative de calcul par opposition à la machine de Turing. C'est une manière intéressante de faire les choses avec des fonctions / réductions (en gros). Certaines questions continuent à me...
Désolé pour le titre accrocheur. Je veux comprendre, que doit-on faire pour réfuter la thèse de Church-Turing? Quelque part j'ai lu c'est mathématiquement impossible de le faire! Pourquoi? Turing, Rosser, etc. ont utilisé différents termes pour distinguer entre "ce qui peut être calculé" et "ce qui...
Quel est le travail publié le plus drôle sur le TCS que vous connaissez? S'il vous plaît inclure uniquement ceux qui sont destinés à être drôle. Les œuvres explicitement conçues pour être intelligemment humoristiques (plutôt que, par exemple, un recueil publié de petites blagues sur la théorie de...
C’est une "question historique" plus qu’une question de recherche, mais la réduction classique à la recherche d’ordres dans l’algorithme de factorisation de Shor a-t-elle été découverte à l’origine par Peter Shor, ou était-elle connue auparavant? Existe-t-il un document décrivant la réduction...
Je suis actuellement un étudiant de premier cycle, obligé d'obtenir un diplôme cette année. Après avoir obtenu mon diplôme, j’envisage d’obtenir un master / doctorat en sciences de la technologie. J'ai commencé à me demander quels domaines des mathématiques sont considérés comme utiles pour le SDC,...
À la lumière de l'annonce de la première puce au monde à photonique quantique programmable , je me demandais quel serait le logiciel d'un ordinateur utilisant l'intrication quantique. L’un des premiers programmes que j’ai écrit était quelque chose comme: for i = 1 to 10 print i next i Quelqu'un...
Cette question peut ne pas convenir à ici, mais je ne pouvais pas trouver un meilleur endroit pour poser (c'était fermé à SO). Je trouve les articles de recherche en informatique difficiles à comprendre. Bien sûr les sujets sont compliqués. Mais après avoir compris un document, je peux généralement...
Veuillez énumérer des exemples dans lesquels un théorème mathématique qui n’était normalement pas considéré comme applicable en informatique a été utilisé pour la première fois pour prouver un résultat en informatique. Les meilleurs exemples sont ceux où le lien n'était pas évident, mais une fois...
En réponse à une question précédente , j'ai mentionné la croyance commune mais fausse selon laquelle l' élimination «gaussienne» se fait dans le temps O(n3)O(n3)O(n^3) . Bien qu'il soit évident que l'algorithme utilise des opérations arithmétiques O(n3)O(n3)O(n^3) , une mise en œuvre négligente...
Les mathématiciens s’inquiètent parfois de l’axiome du choix (AC) et de l’axiome de la détermination (AD). Axiom of Choice : Compte tenu de toute collection des ensembles non vides, il y a une fonction qui, étant donné un ensemble dans , retourne un membre de . f S C SCC{\cal C}FffSSSCC{\cal C}SSS...
Je suis un praticien en logiciel et j'écris une étude sur les structures algébriques à des fins de recherche personnelle et j'essaie de produire des exemples d'utilisation de ces structures en informatique théorique (et, dans une moindre mesure, dans d'autres sous-domaines de l'informatique). ....
Quels sont les algorithmes d’utilité légitime tout simplement trop complexes à mettre en œuvre? Soyons clairs: je ne cherche pas d’algorithmes comme l’algorithme actuel de multiplication de matrice optimale asymptotique (Coppersmith-Winograd), qu’il est raisonnable de mettre en œuvre mais dont la...
Venant d'un contexte plus mathématique, je n'ai jamais vraiment appris à coder. Je commence un doctorat en SDC et beaucoup de gens ont été surpris par le peu de connaissances que j'avais sur la programmation (et sur l'ordinateur en général). Je peux écrire des algorithmes en pseudo-code, mais je ne...
À l' heure actuelle, la résolution soit une problème -complete ou un P S P A C E problème -complete est impossible dans le cas général pour les grandes entrées. Cependant, les deux peuvent être résolus en temps exponentiel et en espace polynomial.NPNPNPPSPUn cEPSPACEPSPACE Puisque nous ne pouvons...
Je connais pas mal de résultats qui utilisent le théorème PCP (principalement dans l'approximation d'algorithmes), mais je n'ai jamais trouvé d'explication claire du théorème PCP (c'est-à-dire que ).NP=PCP(O(log(n)),O(1))NP=PCP(O(log(n)),O(1))\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1)) Quels sont...
La question posée est de savoir si la question suivante est décidable: Problème Étant donné un entier et que la machine de Turing trouverait dans P, le temps d’exécution de par rapport à la longueur en entrée ?M M O ( n k ) nkkkMMMMMM O ( nk)O(nk){O}(n^k)nnn Une réponse étroite de «oui», «non» ou...
Une question récente de Huck Bennett demandant si la classe PH était contenue dans la classe PP, a reçu des réponses quelque peu contradictoires (tout à fait vrai, semble-t-il). D'un côté, plusieurs résultats Oracle ont été donnés, et de l'autre Scott a suggéré que la réponse était probablement...
EDIT AU 10/12/08: Je vais essayer de modifier la question pour que plus de personnes puissent partager leurs opinions. Nous avons besoin de vos contributions! Ce billet est inspiré de celui de MO: Exemples de fausses croyances courantes en mathématiques . Les grandes listes génèrent parfois un...
Mis à jour ci-dessous Nous connaissons tous l'importance cruciale de l'examen par les pairs. C’est la principale forme de contrôle de la qualité et de retour d’information sur la recherche. Cependant, pour un chercheur débutant (comme moi), cela peut parfois être un système / processus déroutant....
Ma question aujourd'hui est (comme d'habitude) un peu bête; mais je vous demanderais de bien vouloir l'examiner. Je voulais connaître la genèse et / ou la motivation du concept de largeur d'arbre. Je comprends bien que cela soit utilisé dans les algorithmes FPT, mais je ne pense pas que ce soit la...