Questions marquées «ds.algorithms»

15
Maintenir l'ordre dans une liste en

Le problème de maintenance des commandes (ou «maintien de l'ordre dans une liste») est de supporter les opérations: singleton: crée une liste avec un élément, lui renvoie un pointeur insertAfter: donné un pointeur sur un élément, insère un nouvel élément après, renvoyant un pointeur sur le nouvel...

14
Algorithme pour trier les paires de nombres

J'ai déjà posé cette question sur stackoverflow , mais c'est peut-être mieux adapté à ce site. Le problème est: J'ai N paires d'entiers non signés. J'ai besoin de les trier. Le vecteur de fin des paires doit être trié de façon non décroissante par le premier nombre de chaque paire et de manière non...

14
Tri à l'aide de piles en lecture seule

Considérez le paramètre suivant: on nous donne une pile qui contient n éléments.sssnnn nous pouvons utiliser un nombre constant de piles supplémentaires.O(1)O(1)O(1) nous pouvons appliquer les opérations suivantes sur ces piles: vérifier si une pile est vide, comparer les éléments supérieurs de...

14
Frapper des cycles impairs

Y a-t-il quelque chose de connu sur le problème suivant? Est-ce que cela a du sens? Comment appelle-t-on ceci? Est-il trivialement équivalent à un autre problème? Quelle est la complexité temporelle? Étant donné un graphe non orienté (général / planaire / degré borné / etc.) G = (V, E), trouver un...

14
L'équivalence eta pour les fonctions est-elle compatible avec l'opération seq de Haskell?

Lemme: En supposant une équivalence éta, nous avons cela (\x -> ⊥) = ⊥ :: A -> B. Preuve: ⊥ = (\x -> ⊥ x)par eta-équivalence, et (\x -> ⊥ x) = (\x -> ⊥)par réduction sous lambda. Le rapport Haskell 2010, section 6.2 spécifie la seqfonction par deux équations: seq :: a -> b -> b...

14
Séparation d'un polyèdre prétraité et d'un plan

J'ai de la difficulté à comprendre une étape dans le document de Dobkin et Kirkpatrick sur la séparation des polyèdres. J'essaie de comprendre cette version: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf Il soutient qu'après avoir connu la meilleure séparation de...