proof

2La chaleur

1Répondre

Prouver que les valeurs de distance extraites dans l'algorithme de Dijkstra ne sont pas décroissantes?

Je revois mes anciennes notes d'algorithmes et j'ai trouvé cette preuve. C'était d'une mission que j'avais et je l'ai eu raison, mais je pense que la preuve manque certainement. La question est de pro

0La chaleur

1Répondre

Ensemble indépendant maximal dans un arbre. algorithme d'examen, besoin de preuves

pseudocode: void recursive('k'){ // 'k' and 'i' vertices sumA = 0; sumB = 0; for each non visited 'i' neighbor do{ recursive('i'); sumA = sumA + b['i']; sumB = sumB + max

0La chaleur

4Répondre

Équivalence formelle entre les langages de programmation

Nous avons 2 langues qui sont (officieusement) sémantiquement équivalentes mais syntaxiquement différentes. L'un est xml et l'autre est basé sur un script. Comment puis-je prouver formellement que les

2La chaleur

3Répondre

Prouvez que n! n'est pas dans O (n^p) pour un nombre naturel constant p

Comment puis-je prouver que n! n'est pas dans O (n^p) pour un nombre naturel constant p? Et est (n k) (n choisir k) dans O (n^p), pour tout k?

8La chaleur

3Répondre

Comment déterminer la hauteur d'un arbre de récurrence à partir d'une relation de récurrence?

Comment peut-on déterminer la hauteur d'un arbre de récursion, construit en cas de récurrence? En quoi diffère-t-il de la détermination de la hauteur d'un arbre régulier? alt text http://homepages.ius

0La chaleur

1Répondre

Stable Matching Problème

Je suis en train de lire un livre d'Algorithme et je suis tombé sur le problème du Stable Matching. Et une question est venue à l'esprit que je suis curieux, mais le livre ne répond pas. Dans chaque S

6La chaleur

11Répondre

Vérification formelle de l'exactitude d'un algorithme

Tout d'abord, est-ce seulement possible sur des algorithmes qui n'ont pas d'effets secondaires? Deuxièmement, où pourrais-je en apprendre davantage sur ce processus, les bons livres, articles, etc?

0La chaleur

1Répondre

complexité preuve

Je voudrais prouver l'exemple suivant: n^k = O (c^n) for every k and c>1 Il est à noter que la fonction polynomiale croît plus vite que la fonction exponentielle. Nous essayons de trouver K0> 0 sati

3La chaleur

3Répondre

Démontrer ou réfuter n^2 - n + 2 ∈ O (n)

Pour mon cours d'analyse d'algorithme, j'ai dérivé d'un algorithme la fonction f (n) = n^2 - n + 2. Maintenant je dois prouver ou réfuter f (n) ∈ O (n). Évidemment, ce n'est pas le cas, alors j'ai ess

1La chaleur

1Répondre

Preuve par induction de la somme des hauteurs des noeuds dans un arbre binaire complet

j'essaie de prouver ce qui suit par induction: sum(k*2^(H-k), k = 0 .. H) = N-H-1 il est un problème pour une classe d'algorithmes. Je pensais pouvoir faire ce que je fais normalement pour les somma