, On remarquera qu'on retient dans A seulement les couples avec capacité strictement positive

, On retrouve ces mêmes conditions dans d'autres contextes. Par exemple, les lois de Kirchoff jouent un rôle similaire dans l'´ etude de circuitsélectriquescircuitsélectriques

, Programmez une fonction d'en tête int lonbourrage(int n, int m) qui calcule la longueur d'un texte composé de n caractères après bourrage relativementàrelativement`relativementà une permutation sur {0, p.1

, int m) qui prend en argument un tableau t[n] qui contient le texte et un tableau bt[l] non-initialisé dont la longueur l est exactement celle prévue par la fonction longbourrage relativementàrelativementà m, Programmez une fonction d'en tête void bourrage

, Programmez une fonction d'en tête void chif(int l, char bt[l], int m, int perm[m]) qui prend en argument un texte après bourrage (par rapportàrapport`rapportà m) représenté

, Programmez une fonction d'en tête void invperm(int m, int perm[m]) qui calcule la permutation inverse de celle reçue en entrée dans le tableau perm

, Programmez une fonction d'en tête int dechif

, Soit C une fonction sur les nombres naturels qui satisfait la récurrence : C(0) =, vol.1

, D'après ce que vous avez appris, pensez-vous qu'une approche diviser pour régner permet d'améliorer la complexité O(n 2 ) de la question 1 ?

, Montrez que l'algorithme A calcule un arbre de recouvrement (` a défaut, vous pouvez supposer ce résultat). *allocate_edge(int n1

. , Programmez une fonction d'en tête : struct edge * enum_edge(int n, struct node * tabnode

, qui prend en argument le nombre de noeuds et le tableau des listes d'adjacence et retourne un pointeurà pointeur`pointeurà une liste qui contient toutes les arêtes du graphe (exactement une fois)

, Programmez une fonction d'en tête : short accessible(int n, struct node * tabnode[n], int i, int j) qui prend en argument le nombre de noeuds, le tableau des listes d'adjacence et deux noeuds i et j et retourne 1 si les noeuds

, En utilisant vos reponses aux questions 2 et 3, analysez la complexité d'une mise en oeuvre de l'algorithme A en fonction de m et n Est-ce possible d'avoir une borne, Et une borne

. La-terminologie-suivante, .. .. Soit-n-=-{0, ;. Un-ensemble-fini-non-vide, .. .. , ,. .. Si et al., On appelle chaqué elément de P une classe d'´ equivalence. On introduit une structure de données pour représenter les partitions de N et qui permet d'exécuter deux opérations :-equal(i,j) décide si lesélémentsleséléments i et j sont dans la même classe d'´ equivalence de la partition.-union(i,j) génère une nouvelle partition dans laquelle les classes d'´ equivalence de i et j sont fusionnées

, On utilise ces déclarations de la façon suivante :-une struct eqclass sertàsert`sertà représenter une classe d'´ equivalence : nombre d'´ eléments dans la classe et pointeur au premier struct node d'une liste qui contient lesélémentsleséléments de la classe.-le tableau belong sertàsert`sertà affecteràaffecter`affecterà chaqué elément de N sa classe d'´ equivalence

, Décrivez (avec un dessein de préférence) une représentation possible de la partition suivante : P = {{0, 3}, {1, 2, 4}, {5, 6}} , qui utilise les struct class et le tableau belong ci-dessus. Aussi expliquez les opérations qu'il faut faire pour implémenter l'opération equal(0,1)

, Peut-on implementer la fonction equal en temps O(1) et la fonction union en temps O(n) ? Expliquez

, Programmez une fonction d'en tête short equal(int n, struct eqclass * belong[n], int i, int j) qui prend en entrée le nombre de noeuds n, le tableau belong et deux noeuds i et j et retourne 1 si les deux noeuds sont dans la même classe d'´ equivalence et 0 autrement

, Programmez une fonction d'en tête void union(int n, struct eqclass * belong[n], int i, int j) qui prend en entrée le nombre de noeuds n, le tableau belong et deux noeuds i et j et fait l'union des classes d'´ equivalence de i et j (on supposera que i n'est pas dans la même classe que j)

{. and .. , Considérons la situation o` u ` a partir de la partition P = {{0}, {n ? 1}} on effectue n ? 1 opérations

. Montrez-que-le-coût-de, Suggestion : combien de fois un elément de N = {0,. .. , n ? 1} peut-il changer de classe d'´ equivalence

, Comment peut-on utiliser la structure de données présentée dans le contexte de l'algorithme A ? Quelle est la complexité de l'algorithme A dans ce cas ?

, Supposons que les arêtes du graphe G sont pondérées par des poids non-négatifs. Est-ce possible d'adapter l'algorithme A de façonfaçon`façonà qu'il calcule un arbre de recouvrement de poids minimal ? Expliquez

M. Akra and L. Bazzi, On the solution of linear recurrence equations, Computational Optimization and Applications, vol.10, issue.2, pp.195-210, 1998.

M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P. Annals of Mathematics, vol.160, issue.2, pp.781-793, 2004.

R. Bellman, The theory of dynamic programming, Bulletin of the AMS, vol.60, issue.6, pp.503-516, 1954.

J. Bentley, Programming pearls : algorithm design techniques, Communications of the ACM, vol.27, issue.9, pp.865-873, 1984.

J. Hans-, M. Boehm, and . Weiser, Garbage collection in an uncooperative environment, Softw., Pract. Exper, vol.18, issue.9, pp.807-820, 1988.

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to algorithms, 2009.

J. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp, vol.19, pp.297-301, 1965.

G. Dantzig, Programming in a linear structure, 1948.

E. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, vol.1, pp.269-271, 1959.

J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, vol.19, issue.2, pp.248-264, 1972.

L. Ford and D. Fulkerson, Maximal flow through a network, Canadian journal of mathematics, vol.8, issue.3, pp.399-404, 1956.

C. A. Hoare, Algorithm 64 : Quicksort, Commun. ACM, vol.4, issue.7, p.321, 1961.

D. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the IRE, vol.40, pp.1098-1101, 1952.

N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, vol.4, issue.4, pp.373-396, 1984.

L. Khachiyan, A polynomial algorithm in linear programming, Akademiia Nauk SSSR. Doklady, vol.244, pp.1093-1096, 1979.

A. Karatsuba and Y. Ofman, Multiplication of many-digital numbers by automatic computers, Proceedings of the USSR Academy of Sciences, vol.145, pp.293-294, 1962.

B. Kernighan and R. Pike, La programmation en pratique, 2017.

B. Kernighan, D. R. Le-langage, and C. Dunod, , 2014.

G. L. Miller, Riemann's hypothesis and tests for primality, J. Comput. Syst. Sci, vol.13, issue.3, pp.300-317, 1976.

J. I. Munro, T. Papadakis, and R. Sedgewick, Deterministic skip lists, Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, pp.367-375, 1992.

R. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal, vol.36, issue.6, pp.1389-1401, 1957.

W. Pugh, Skip lists : A probabilistic alternative to balanced trees, Commun. ACM, vol.33, issue.6, pp.668-676, 1990.

O. Michael and . Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput, vol.9, issue.2, pp.273-280, 1980.

V. Shoup, A computational introduction to number theory and algebra, 2005.

A. Daniel, S. Spielman, and . Teng, Smoothed analysis of algorithms : Why the simplex algorithm usually takes polynomial time, J. ACM, vol.51, issue.3, pp.385-463, 2004.

. Volker-strassen, Gaussian elimination is not optimal, Numer. Math, vol.13, pp.354-356, 1969.