Examen Algorithme Avance & Complexite

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

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é 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é 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é 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