请求高人指导2道算法方面的题目（平摊分析和NP完全性）
哪位高人如果懂的话，还望拔刀相助啊！！我也是没有办法，《算法导论》的相关章节看了好几遍还是不太懂，更不用说用法语做题了。Cout amorti 看着好像简单，可是不知道它是用来干什么的，为什么要有这个理论？和算法时间复杂度有什么区别和联系？ NP-Completude比较难，那就是完全不懂了，还望高人指点一二（那怕有几句话给点提示也好啊），非常感谢！www.revefrance.com
后天就要考试，真是着急～～～再次感谢帮忙啊！！www.revefrance.com
1. Cout amorti
Cet exercice présente une implémentation de pile qui utilise un peu de mémoire centrale et beacoup d'espace disque. L'espace disque est partitionné en pages, pouvant chacune contenir p éléments. On peut lire et écrire les éléments individuellement lorsqu'ils sont en mémoire centrale, avec un coût O(1); mais lorsque les éléments sont sur disque, on y accède par page, avec un coût O(p).www.revefrance.com
On considère une pile qui stocke la première page de ses éléments(haute de pile) en mémoire centrale, et la suite sur disque; Il y a donc un coût O(p) lorsque le sommet de pile change de page.www.revefrance.com
1. Montrer que pour une suite de n opérations empiler ou dépiler, le nombre maximum d'accès disque est O(n) et le coût maximum O(np). Décrire une suite de n operations qui atteint ce coût maximum.www.revefrance.com
2. Montrer que si on peut stocker 2 pages en mémoire centrale, alors il est possible d'implanter les opérations empiler et dépiler avec un coût amorti O(1)
www.revefrance.com
2.NP-Completude
www.revefrance.com
1. Supponsons que l'on dispose d'un algorithme pour résoudre le problème de la clique: étant donné un graphe G et un entier k, l'algorithme A(G,k) décide si G a une clique de taille k. Donner alors un algorithme qui calcule, en utilisant seulement des appels à l'algorithme A, les sommets d'une k-clique dans un graphe (si elle existe).
2. Montrer que le problème de décision suivant est NP-Complet. Etant donnés deux graphe G1, G2 et un entier k, déterminer s'il existe un graphe avec au moins k arêtes qui est à la fois un sous-graphe de G1 et un sous-graphe de G2.www.revefrance.com
3.Supposons que l'on dispose d'un algorithme B pour résoudre le problème du plus grand sous-graphe commun de la question précédente. Donner alors un algorithme qui calcule, en utilisant seulement des appels à l'algorithme B, un sous-graphe de k arêtes (s'il existe) apparaissant dans G1, G2.
