Questions concernant des instructions bien définies pour accomplir une tâche, et une analyse pertinente en termes de temps / mémoire / etc.
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...
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...
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...
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...
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...
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...
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...
Contexte Il y a plusieurs années, lorsque j'étais étudiant de premier cycle, on nous a confié un devoir d'analyse en amortissement. J'ai été incapable de résoudre l'un des problèmes. Je l’avais demandé en théorie , mais aucun résultat satisfaisant n’a été obtenu. Je me souviens du cours TA a...
Connaissez-vous des algorithmes sensés fonctionnant en temps polynomial en (Longueur d’entrée + longueur en sortie), mais dont le temps de fonctionnement asymptotique dans la même mesure a un exposant / une constante vraiment énorme (au moins, où la limite supérieure prouvée du temps de...
Il est largement supposé que , l'exposant optimal pour la multiplication matricielle, est en fait égal à 2. Ma question est simple:ωω\omega Quelles raisons avons-nous pour croire que ?ω=2ω=2\omega = 2 Je connais des algorithmes rapides comme Coppersmith-Winograd, mais je ne sais pas pourquoi ils...
Les algorithmes génétiques n'ont pas beaucoup de poids dans le monde théorique, mais ils constituent une méthode métaheuristique assez bien utilisée (par métaheuristique, je veux dire une technique qui s'applique de manière générique à de nombreux problèmes, tels que l'annelage, la descente de...
Deux manières d’analyser l’efficacité d’un algorithme sont: mettre une limite supérieure asymptotique sur son temps d'exécution, et pour l'exécuter et collecter des données expérimentales. Je me demande s’il existe des cas connus où il existe un écart important entre (1) et (2). Par cela, je veux...
Pour (rechercher les versions) des problèmes NP- complets, la vérification d'une solution est clairement plus facile que de la trouver, car la vérification peut être effectuée en temps polynomial, tandis que la recherche d'un témoin prend (probablement) une durée exponentielle. En P , cependant, la...
Supposons que j'ai un graphe acyclique dirigé avec des pondérations en nombre réel sur ses sommets. Je souhaite trouver un ordre topologique du groupe de disponibilité de base de données dans lequel, pour chaque préfixe de cet ordre topologique, la somme des poids est non négative. Ou si vous...
J'ai toujours eu du mal à comprendre l'importance de l' écart d' intégrité (IG) et des limites qui s'y rattachent. IG est le rapport entre (la qualité de) une réponse entière optimale à (la qualité de) une solution réelle optimale de la relaxation du problème. Prenons la couverture de vertex (VC)...
Je cherche des hypothèses sur les algorithmes et la complexité qui ont été jugées crédibles par beaucoup à un moment donné, mais qui ont ensuite été réfutées, ou du moins incrédules, en raison de la multiplication des contre-preuves. Voici deux exemples: Hypothèse aléatoire d'oracle: les relations...
Si vous pouviez renommer la programmation dynamique, comment
Quelles sont les explications théoriques à la réussite pratique des solveurs SAT, et quelqu'un peut-il donner un aperçu et des explications de type "wikipedia"? Par analogie, l' analyse lissée ( version arXiv ) de l'algorithme simplex explique très bien pourquoi elle fonctionne si bien dans la...
Dans un autre fil de discussion , Joe Fitzsimons s'est interrogé sur "la meilleure limite inférieure actuelle de 3SAT". J'aimerais faire l'inverse: quelle est la meilleure limite supérieure actuelle sur 3SAT? En d'autres termes, quelle est la complexité temporelle du solveur SAT le plus efficace?...