Questions marquées «big-list»

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...

[ 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...

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...

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...

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...

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...

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...

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...

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...

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....

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...

Souvent, lorsque nous participons aux conférences du SDC, nous remarquons quelques petits détails dont nous souhaitons que les organisateurs de la conférence se soient occupés. Et lorsque nous organisons des conférences, nous l’avons déjà oublié. D'où la question: quelles petites mesures...

Je cherche des exemples de problèmes paramétrés par un nombre , où la dureté du problème est non monotone en . La plupart des problèmes (selon mon expérience) ont une transition de phase unique, par exemple -SAT a une transition de phase unique de (où le problème est en P) à (où le le problème est...