Questions et réponses pour les informaticiens théoriques et les chercheurs dans des domaines connexes
Depuis le livre de Chris Okasaki paru en 1998 "Des structures de données purement fonctionnelles", je n'ai pas vu apparaître trop de nouvelles structures de données passionnantes et purement fonctionnelles; Je peux n'en nommer que quelques-uns: IntMap (également inventé par Okasaki en 1998, mais...
Cette question est (inspirée par) / (honteusement volée à) une question similaire chez MathOverflow , mais je m'attends à ce que les réponses ici soient très différentes. Nous avons tous des articles favoris dans nos domaines théoriques respectifs. De temps en temps, on trouve un article tellement...
Paul Erdos a parlé du "livre" où Dieu conserve la preuve la plus élégante de chaque théorème mathématique. Cela a même inspiré un livre (qui, à mon avis, en est à sa quatrième édition): Proofs from the Book . Si Dieu avait un livre similaire pour les algorithmes, quel (s) algorithme (s) pensez-vous...
Pour démontrer l’importance des algorithmes (par exemple pour les étudiants et les professeurs qui ne pratiquent pas la théorie ou qui viennent même de domaines totalement différents), il est parfois utile de disposer d’une liste d’exemples où des algorithmes centraux ont été déployés dans les...
Je me suis amusé à réviser la théorie du calcul pour le plaisir et cette question me harcelait depuis un moment (drôle, je n'y ai jamais pensé lorsque j'ai appris la théorie des automates à mes études de premier cycle). Alors "pourquoi" étudions-nous exactement les automates finis déterministes et...
Norbert Blum a récemment publié une preuve de 38 pages attestant que . Est-ce correct?P≠ NPP≠NPP \ne NP Également sur le sujet: où d'autre (sur Internet) discute-t-on de son exactitude? Remarque: l'objet de cette question a évolué au fil du temps. Voir les commentaires de la question pour plus de...
[ Chronologie ] Cette question a le même esprit: quels journaux doivent être lus par tout le monde et quelles vidéos doivent être visionnées par tout le monde . Il demande des livres remarquables dans différents domaines de l'informatique théorique. Les livres peuvent être orientés vers les...
Wikipedia n'énumère que deux problèmes sous "problèmes non résolus en informatique" : P = NP? L'existence de fonctions à sens unique Quels sont les autres problèmes majeurs qui devraient être ajoutés à cette liste? Règles: Un seul problème par réponse Fournir une brève description et tout lien...
L’Université de Stanford a maintenant une chaîne Youtube , avec un accès gratuit à la vidéo HD de tous les cours, des systèmes dynamiques à l’intrication quantique. Plus de conférences et d'ateliers enregistrent leurs discours sur bande vidéo. Quelles sont les vidéos en ligne que tout le monde...
Supposons que Mario marche sur la surface d'une planète. S'il commence à marcher depuis un endroit connu, dans une direction fixe, sur une distance prédéterminée, à quelle vitesse pouvons-nous déterminer où il s'arrêtera? Plus formellement, supposons que nous recevions un polytope convexe dans un...
La factorisation et l'isomorphisme des graphes sont des problèmes dans NP qui ne sont connus ni pour P ni pour NP-Complete. Quels autres problèmes naturels (suffisamment différents) partagent cette propriété? Les exemples artificiels directement issus de la démonstration du théorème de Ladner ne...
Après avoir lu la question de Daniel Apon , j'ai commencé à penser qu'il pourrait être utile (en particulier aux jeunes chercheurs et aux étudiants diplômés comme moi) de poser une question plus large et plus générale afin que nous puissions apprendre de l'expérience de chercheurs plus...
Un mélange de deux chaînes est formé en intercalant les caractères dans une nouvelle chaîne, en maintenant les caractères de chaque chaîne dans l'ordre. Par exemple, MISSISSIPPIest un mélange de MISIPPet SSISI. Permettez-moi d'appeler un carré de corde s'il s'agit d'un mélange de deux chaînes...
Il y a eu plusieurs questions avec le même schéma que celui-ci: Quels papiers tout le monde devrait lire Quels livres tout le monde devrait lire Quels sont les récents ouvrages du SDC dont les projets sont disponibles en ligne quelles vidéos tout le monde devrait regarder J'étais réticent à en...
L'informatique théorique a fourni quelques exemples du "prix de l'abstraction". Les deux plus importants concernent l'élimination et le tri gaussiens. À savoir: On sait que l'élimination gaussienne est optimale pour, par exemple, calculer le déterminant si vous limitez les opérations à des lignes...
J'ai appris quelques notions de la théorie des catégories. C'est certainement une façon différente de voir les choses. (Résumé très approximatif pour ceux qui ne l’ont pas vue: la théorie des catégories permet d’exprimer toutes sortes de comportements mathématiques uniquement en termes de relations...
Après le post Ce que les livres doivent être lus par tous , j'ai remarqué qu'il existe des livres récents dont les brouillons sont disponibles en ligne. Par exemple, l' entrée Algorithmes d'approximation de l'article ci-dessus cite un livre de 2011 (à paraître) intitulé La conception d'algorithmes...
De nombreux algorithmes de recherche de trajectoire ont été développés ces dernières années. Ils permettent de calculer la meilleure trajectoire en réponse aux changements de graphes beaucoup plus rapidement que A * - en quoi consistent-ils et en quoi diffèrent-ils? S'agit-il de situations...
Je me prépare pour une conférence destinée aux étudiants en mathématiques de premier cycle et, dans ce cadre, j’envisage de discuter du concept de décidabilité. Je veux donner un exemple d'un problème que nous ne savons pas actuellement décisif ou indécidable. Il existe de nombreux problèmes de ce...
J'aimerais demander de l'aide pour compiler une liste du plus grand nombre possible de conférences et d'ateliers liés au SDC. Ma principale motivation est de planifier la couverture possible de plusieurs théories par le blog - trouver des correspondants assistant à ces événements qui seraient...