Examen Algorithme Avance & Complexite

Quelle est la différence entre un problème accepté par machine de Turing et un problème décidé par machine de Turing? 1- On veut montrer qu'un arbre rouge et noir ayant n nœuds internes à une hauteur au plus égale à 2 x log(n+1): a) Montrer que, pour un nœud x quelconque dans un arbre rouge et noir, le sous-arbre enrac

Algorithmiques Avancés et Complexité 03

Quels sont les propriétés d'un B-arbre ? Qu'est-ce que le calcul parallèle ? (0,5 pt) Présentez la classification de Flynn pour les architectures de machines parallèles. (1,5 pt) Soit G = (S, A) un graphe, un sous-ensemble des sommets de G est stable s'il ne contient pas de paire de sommets adjacents. Montrez que tout

Algorithmiques Avancés et Complexité Sujet 2

Soit f(n)=n*logn le nombre d’opérations élémentaires du pire cas d’un algorithme A.Montrez que f(n)=O(n2). A-t-on f(n)=Θ(n2) ? Expliquez. 2) Soient Bob, Henzo et Alice ont trois algorithmes conçus pour la même tâche T, et dont les nombres d’opérations élémentaires du pire cas sont, respectivement, f1(n)=n20logn, f2