Vue d'ensemble
Le chapitre 1 contient du matériel de révision sur les mathématiques discrètes et la récursivité. Je crois que la seule façon d'être à l'aise avec la récursivité, c'est de voir de bons usages à plusieurs reprises. Par conséquent, la récursivité est très répandue dans ce texte, avec des exemples dans chaque chapitre, sauf du chapitre 5.
Le chapitre 2 traite avec l'analyse d'algorithmes. Ce chapitre explique l'analyse asymptotique et ses principales faiblesses. De nombreux exemples sont fournis, y compris une explication en profondeur des logarithmes le temps de fonctionnement. Simple programmes récursifs sont analysés par intuitivement en les convertissant en itérative des programmes. Plus compliquées diviser et conquérir les programmes sont mis en place, mais certains de l'analyse (résolution des relations de récurrence) est implicitement retardée jusqu'à ce que le chapitre 7, où il est effectué en détail.
Le chapitre 3 traite des listes, piles, files d'attente et. L'accent est mis sur le codage de ces structures de données en utilisant ADTs, mise en œuvre rapide de ces structures de données, et une exposition de certaines de leurs utilisations. Il n'ya presque pas de programmes (juste des routines), mais les exercices contiennent une grande quantité d'idées pour des missions de programmation.
Le chapitre 4 couvre les arbres, avec un accent sur les arbres de recherche, y compris les arbres de recherche externes (B-arbres). Le système de fichiers UNIX et des arborescences d'expression sont utilisés comme exemples. Arbres AVL et les arbres splay sont introduits, mais pas analysé. Soixante dix pour cent-cinq le code est écrit, en laissant des cas semblables à être rempli par l'élève. Un traitement plus attentif des détails de mise en œuvre de recherche d'arbres se trouve au chapitre 12. Une couverture supplémentaire d'arbres, tels que la compression des fichiers et des arbres de jeu, est reporté jusqu'à ce que le chapitre 10. Les structures de données pour un support externe sont considérés comme le dernier sujet en plusieurs chapitres.
Le chapitre 5 est le chapitre relativement court au sujet des tables de hachage. Une analyse est effectuée, et le hachage extensible est couverte à la fin du chapitre.
Le chapitre 6 est des files d'attente prioritaires. Tas binaires sont couverts, et il ya du matériel supplémentaire sur quelques-unes des implémentations théoriquement intéressantes de files d'attente prioritaires. Le tas de Fibonacci est discuté dans le chapitre 11, et le tas d'appariement est discuté dans le chapitre 12.
Chapitre 7 couvre le tri. Il est très spécifique à l'égard de codage de détails et d'analyse. Tous les algorithmes de tri importantes d'usage général sont couverts et comparées. Quatre algorithmes sont analysés en détail: le tri par insertion, Shellsort, heapsort, et quicksort. L'analyse de la durée moyenne des cas en cours d'exécution du tri par tas est nouveau pour cette édition. Tri externe est couverte à la fin du chapitre.
Le chapitre 8 traite de l'algorithme ensemble disjoint avec la preuve de la durée de fonctionnement. C'est un chapitre court et précis qui peut être ignorée si l'algorithme de Kruskal n'est pas discutée.
Chapitre 9 couvre les algorithmes de graphes. Algorithmes sur les graphes sont intéressants, non seulement parce qu'ils se produisent fréquemment dans la pratique, mais aussi parce que leur temps d'exécution est donc fortement tributaire de la bonne utilisation des structures de données. La quasi-totalité des algorithmes standards sont présentées avec les structures de données appropriées, pseudocode, et l'analyse des temps de fonctionnement. Pour placer ces problèmes dans un contexte approprié, une brève discussion sur la théorie de la complexité (y compris la NP-complétude et de l'indécidabilité) est fourni.
Chapitre 10 couvre la conception d'algorithmes communs en examinant la résolution de problèmes techniques. Ce chapitre est lourdement fortifié avec des exemples. Pseudocode est utilisé dans ces derniers chapitres de sorte que l'appréciation de l'élève d'un algorithme par exemple n'est pas obscurci par les détails d'implémentation.
Le chapitre 11 traite de l'analyse amorti. Trois structures de données des chapitres 4 et 6 et le tas de Fibonacci, introduit dans ce chapitre, sont analysés.
Le chapitre 12 est nouveau pour cette édition. Il couvre les algorithmes d'arbres de recherche, l'arbre kd, et le tas d'appariement. Ce chapitre part du reste du texte en fournissant des implémentations complètes et attention pour les arbres de recherche et d'appariement tas. Le matériau est structuré de telle sorte que l'instructeur peut intégrer les sections des discussions dans d'autres chapitres. Par exemple, le top-down arbre rouge noir dans le chapitre 12 peut être discuté sous les arbres AVL (chapitre 4).
Chapitres 1-9 de fournir assez de matériel pour la plupart des structures de données d'un semestre de cours. Si le temps le permet, puis le chapitre 10 peut être couverte. Un cours universitaire sur l'analyse d'algorithmes pourrait couvrir les chapitres 7-11. Les structures de données avancées analysés dans le chapitre 11 peut facilement être mentionné dans les chapitres précédents. La discussion de la NP-complétude dans le chapitre 9 est beaucoup trop brève pour être utilisé dans un tel cours. Garey et Johnson livre sur la NP-complétude peut être utilisé pour augmenter ce texte.
Télécharger