Complexite des Algorithmes

Puissance | Complexite

La puissance d'un nombre est le résultat de la multiplication répétée de ce nombre avec lui-même.Une puissance est composée de 2 éléments: Une base qui indique le nombre à multiplier par lui-même. Un exposant qui indique combien de fois le nombre est multiplié par lui-même. I) Écrire un Programme C qui détermine le

Le Grand Saut | Complexite

Le problème est de déterminer à partir de quel étage d’un immeuble, sauter par une fenêtre est fatal. Vous êtes dans un immeuble à n étages (numérotés de 1 à n) et vous disposez de k étudiants. Il n’y a qu’une opération possible pour tester si la hauteur d’un étage est fatale : faire sauter un étudiant par la fenêtre.

Le Bricolage | Complexite

Dans une boite à outils, vous disposez de n écrous de diamètres tous diﬀérents et des n boulons correspondants. Mais tout est mélangé et vous voulez appareiller chaque écrou avec le boulon qui lui correspond. Les diﬀérences de diamètre entre les écrous sont tellement minimes qu’il n’est pas possible de déterminer à l’œ

Couverture dans les graphes | NP COMPLETUDE

Soit G un graphe G = (V, E) de la figure suivante. Un ensemble dominant C du graphe G est un sous-ensemble de sommets tel que tout sommet est soit dans C soit voisin d’un sommet de C. A partir de G, construire le graphe G′ = (V ′, E′) tel que V ′ = V ∪ E ; E′ = E ∪ {(v, a)|v ∈ V, a ∈ E, v es

3-SAT 3-COLORING | NP COMPLETUDE

Montrer que le problème 3-SAT se réduit polynomialement au problème 3-COLORING. Démonstration : La coloration à trois couleurs est un problème qui appartient à la classe NP. Certificat : Pour chaque nœud, une couleur choisie parmi {1, 2, 3}. Certifieur : Vérification que pour chaque arête (u, v), la couleur du

Analyse et démonstration de Complexité

Méthode de l’arbre récursif : Dans un arbre récursif, chaque nœud représente le coût d’un sous-problème individuel, situé quelque part dans l’ensemble des invocations récursives de fonction. Soit p(n)= ∑_(i=0)^p▒〖a_i n^(i ) 〗 un polynôme en n de degré p tel que ad > 0, ou d est un entier, et soit k une constate. Mon

Généralités sur les notations Asymptotiques

Dire si les affirmations suivantes sont vraies,, pour toute fonction f de N dans R+ 2^(n+1)∈O(2^n) ; (n+1)!∈O(n!); f(n)∈O(n) ⇒ 〖(f(n))〗^2∈O(n^2); f(n)∈O(n) ⇒ 2^(f(n))∈O(2^n); n^n∈O(2^n). Soient f(x) et g(x) des fonctions positives asymptotiquement, prouver ou démentir les affirmations suivantes : f(n) = O(g(n)) =>

Notations Asymptotiques et Complexités

Explorez les concepts de complexité algorithmique, les notations asymptotiques telles que O(n), Θ(n), Ω(n), et leurs applications dans cet ensemble d'exercices. Découvrez comment analyser et démontrer la complexité des algorithmes

Analyse de la Complexité Algorithmique

Exercices d'analyse de la complexité algorithmique et de la notation de Landau. Inclut des relations d'inclusion entre différentes notations, des comparaisons de complexité entre algorithmes, et des exemples de calcul de complexité en notation Big O.

Sélection et Médiane dans un Tableau

La médiane est un élément fondamental en statistiques. Dans un tableau T[1 \ldots n] contenant des entiers, la médiane est définie comme suit : Si n est impair, la médiane est le \lceil n/2 \rceil-ième plus petit élément. Si n est pair, la médiane est l'un des deux éléments au centre après tri. Trouver la médiane

Planification avec des délais

Une entreprise a une série de tâches \( J = \{1, 2, \ldots, n\} \) à exécuter. Chaque tâche \( i \) : Prend exactement une unité de temps à être exécutée. Génère un bénéfice \( g_i \) si elle est terminée avant sa date limite \( d_i \). La ressource exécutant ces tâches ne peut réaliser qu'une seule tâche à un instan

Planification avec un algorithme glouton

Un système à serveur unique (par exemple, une pompe à essence, un caissier dans une banque ou un processeur informatique) doit servir \( n \) clients. Chaque client \( i \) a un temps de service \( t_i \), connu à l'avance. Votre objectif est de minimiser le temps total passé par tous les clients dans le système, soit

Le Problème du Voyageur de Commerce (TSP)

Le problème du voyageur de commerce (TSP - Travelling Salesperson Problem) est un problème classique d'optimisation combinatoire. Un voyageur doit visiter un ensemble de villes, en passant une fois par chaque ville, et revenir à la ville de départ. Le but est de minimiser la distance totale parcourue. Ce problème es