Questions et réponses pour les étudiants, chercheurs et praticiens de l'informatique
Dans un cours sur les algorithmes standard, on nous apprend que quicksort est en moyenne et dans le pire des cas. Dans le même temps, d'autres algorithmes de tri sont étudiés, qui sont dans le pire des cas (comme mergesort et heapsort ) et même un temps linéaire dans le meilleur des cas (comme...
J'ai remarqué qu'il m'est beaucoup plus facile d'écrire des preuves mathématiques sans commettre d'erreur, que d'écrire un programme d'ordinateur sans bugs. Il semble que ce soit quelque chose de plus répandu que mon expérience. La plupart des gens font constamment des bogues logiciels dans leur...
En regardant la page Web de Julia , vous pouvez voir quelques points de repère de plusieurs langues à travers plusieurs algorithmes (timings montrés ci-dessous). Comment un langage avec un compilateur écrit à l'origine en C peut-il surpasser le code C? Figure: temps de référence par rapport à C...
Il y a beaucoup de questions sur la façon d'analyser le temps d' exécution des algorithmes (voir, par exemple, l' exécution d'analyse et d'analyse de l' algorithme ). Beaucoup sont similaires, par exemple ceux qui demandent une analyse des coûts des boucles imbriquées ou des algorithmes de division...
Je ne comprends pas pourquoi le problème de l' arrêt est si souvent utilisé pour écarter la possibilité de déterminer si un programme est interrompu. Le [article] [1] de Wikipedia explique correctement qu'une machine déterministe à mémoire finie arrêtera ou répétera un état antérieur. Vous pouvez...
Je parle assez bien le C / C ++ et je peux me familiariser avec les différents langages de script (awk / sed / perl). J'ai commencé à utiliser beaucoup plus python, car il combine certains aspects astucieux du C ++ avec les fonctionnalités de script de awk / sed / perl. Mais pourquoi y a-t-il tant...
On nous a donné l'exercice suivant. Laisser F( n ) = { 100n se produit dans la représentation décimale de πautref(n)={10n occurs in the decimal representation of π0else\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 &...
Permettez-moi de préciser: Étant donné le diagramme de dispersion d'un nombre donné de points n, si je veux trouver le point le plus proche d'un point du graphique, je peux immédiatement ignorer la plupart des points du graphique, réduisant ainsi mes choix à un petit nombre constant de points...
J'apprends Haskell et je suis fasciné par la langue. Cependant, je n'ai aucun fond sérieux en mathématiques ou en CS. Mais je suis un programmeur expérimenté. Je veux apprendre la théorie des catégories afin de devenir meilleur à Haskell. Quels sujets de la théorie des catégories devrais-je...
Convertir des expressions régulières en NFA (minimales) acceptant le même langage est facile avec des algorithmes standard, tels que celui de Thompson . L’autre direction semble être plus fastidieuse, cependant, et les expressions résultantes sont parfois désordonnées. Quels algorithmes existe-t-il...
La plupart des méthodes de cryptage actuelles, telles que RSA, reposent sur la factorisation entière, qui n'est pas considérée comme un problème complexe, mais appartient au BQP, ce qui la rend vulnérable aux ordinateurs quantiques. Je me demande pourquoi il n’existe pas d’algorithme de chiffrement...
Pour essayer de vérifier si un algorithme est correct pour un problème donné, le point de départ habituel est d'essayer de l'exécuter à la main sur un certain nombre de cas de test simples. Essayez-le sur quelques exemples de problèmes, y compris quelques "cas simples". ". C'est une excellente...
Un arbre binaire indexé a très peu ou pas de littérature par rapport à d'autres structures de données. Le seul endroit où il est enseigné est le tutoriel topcoder . Bien que le tutoriel soit complet dans toutes les explications, je ne peux pas comprendre l'intuition derrière un tel arbre? Comment...
Il y a beaucoup de tentatives pour prouver soit ou , et naturellement beaucoup de gens réfléchissent à la question, ayant des idées pour prouver la direction dans laquelle ils veulent aller.P ≠ N PP = N PP=NP\mathsf{P} = \mathsf{NP} P ≠ N PP≠NP\mathsf{P} \neq \mathsf{NP} Je sais qu'il a été prouvé...
De nombreux programmes d’informatique requièrent deux ou trois cours de calcul. Je me demande comment et quand le calcul est utilisé en informatique? Le contenu en informatique d'un diplôme en informatique a tendance à se concentrer sur les algorithmes, les systèmes d'exploitation, les structures...
Je me pose des questions sur cette question depuis que je suis étudiant de premier cycle. C'est une question générale mais je développerai avec des exemples ci-dessous. J'ai vu beaucoup d'algorithmes - par exemple, pour des problèmes de flux maximum, je connais environ 3 algorithmes qui peuvent...
Ces deux semblent très similaires et ont une structure presque identique. Quelle est la différence? Quelles sont les complexités temporelles pour les différentes opérations de
Dans la plupart des classes d'introduction aux algorithmes, des notations telles que (Big O) et sont introduites, et un étudiant apprendra généralement à utiliser l'une de celles-ci pour rechercher la complexité temporelle.ΘOOOΘΘ\Theta Cependant, il existe d'autres notations, telles que , et ....
La formule de la dimension Vapnik – Chervonenkis (VC) pour les réseaux de neurones va de O(E)O(E)O(E) à O(E2)O(E2)O(E^2) , avec O(E2V2)O(E2V2)O(E^2V^2) dans le pire des cas, où EEE est le nombre d'arêtes et VVV est le nombre de nœuds. Le nombre d'échantillons d'apprentissage nécessaires pour avoir...
Il existe deux méthodes de partition quicksort mentionnées dans Cormen: Hoare-Partition(A, p, r) x = A[p] i = p - 1 j = r + 1 while true repeat j = j - 1 until A[j] <= x repeat i = i + 1 until A[i] >= x if i < j swap( A[i], A[j] ) else return j et: Lomuto-Partition(A, p, r) x = A[r] i = p...