Examen Algorithme Avance & Complexite

Algorithmiques Avancés et Complexité Sujet 1

La communauté urbaine de PandaVille est constituée de 07 villes : Douala, Bafoussam, Bertoua, Garoua, Ebolowa, Limbe et Maroua. Les trois premières villes sont séparées des quatre autres par le fleuve Sanaga, dont la largeur maximale de 300 km sépare Bertoua et Maroua ; sa largeur minimale est de 25 km entre Douala et

Algorithmiques Avancés et Complexité 04

Quels sont les propriétés d'un B-arbre ? Considérons un arbre binaire de n nœuds. Notons f son nombre de feuilles et h sa hauteur. Tous les arbres considérés seront supposés non vides. Répondez en vous justifiant : Quelle est la hauteur minimale d'un arbre de n nœuds ? (0,5 pt) Montrez que le nombre de branches vides (

Algorithmiques Avancés et Complexité 05

Quelle est la différence entre un problème accepté par machine de Turing et un problème décidé par machine de Turing ? Supposons que f(n), g(n) et h(n) sont des fonctions, montrez que: f(n) = theta(g(n)) implique f(n) = O(g(n)) et f(n) = Ω(g(n)) (1 pt) f(n) = theta(g(n)) si et seulement si g(n) = theta(f(n)) (1 pt) So

Algorithmiques Avancés et Complexité 02

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