, 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
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)
Considérons la situation o` u ` a partir de la partition P = {{0}, {n ? 1}} on effectue n ? 1 opérations ,
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
On the solution of linear recurrence equations, Computational Optimization and Applications, vol.10, issue.2, pp.195-210, 1998. ,
, PRIMES is in P. Annals of Mathematics, vol.160, issue.2, pp.781-793, 2004.
The theory of dynamic programming, Bulletin of the AMS, vol.60, issue.6, pp.503-516, 1954. ,
Programming pearls : algorithm design techniques, Communications of the ACM, vol.27, issue.9, pp.865-873, 1984. ,
Garbage collection in an uncooperative environment, Softw., Pract. Exper, vol.18, issue.9, pp.807-820, 1988. ,
Introduction to algorithms, 2009. ,
An algorithm for the machine calculation of complex Fourier series, Math. Comp, vol.19, pp.297-301, 1965. ,
Programming in a linear structure, 1948. ,
A note on two problems in connexion with graphs, Numerische Mathematik, vol.1, pp.269-271, 1959. ,
Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, vol.19, issue.2, pp.248-264, 1972. ,
Maximal flow through a network, Canadian journal of mathematics, vol.8, issue.3, pp.399-404, 1956. ,
Algorithm 64 : Quicksort, Commun. ACM, vol.4, issue.7, p.321, 1961. ,
A method for the construction of minimum-redundancy codes, Proceedings of the IRE, vol.40, pp.1098-1101, 1952. ,
A new polynomial-time algorithm for linear programming, Combinatorica, vol.4, issue.4, pp.373-396, 1984. ,
A polynomial algorithm in linear programming, Akademiia Nauk SSSR. Doklady, vol.244, pp.1093-1096, 1979. ,
Multiplication of many-digital numbers by automatic computers, Proceedings of the USSR Academy of Sciences, vol.145, pp.293-294, 1962. ,
La programmation en pratique, 2017. ,
, , 2014.
Riemann's hypothesis and tests for primality, J. Comput. Syst. Sci, vol.13, issue.3, pp.300-317, 1976. ,
Deterministic skip lists, Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, pp.367-375, 1992. ,
Shortest connection networks and some generalizations, Bell System Technical Journal, vol.36, issue.6, pp.1389-1401, 1957. ,
Skip lists : A probabilistic alternative to balanced trees, Commun. ACM, vol.33, issue.6, pp.668-676, 1990. ,
Probabilistic algorithms in finite fields, SIAM J. Comput, vol.9, issue.2, pp.273-280, 1980. ,
A computational introduction to number theory and algebra, 2005. ,
Smoothed analysis of algorithms : Why the simplex algorithm usually takes polynomial time, J. ACM, vol.51, issue.3, pp.385-463, 2004. ,
Gaussian elimination is not optimal, Numer. Math, vol.13, pp.354-356, 1969. ,