Đang chuẩn bị liên kết để tải về tài liệu:
Algorithms and Complexity

Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG Tải xuống

For the past several years mathematics majors in the computing track at the University of Pennsylvania have taken a course in continuous algorithms (numerical analysis) in the junior year, and in discrete algorithms in the senior year. This book has grown out of the senior course as I have been teaching it recently. It has also been tried out on a large class of computer science and mathematics majors, including seniors and graduate students, with good results. | Algorithms and Complexity Herbert S. Wilf University of Pennsylvania Philadelphia PA 19104-6395 Copyright Notice Copyright 1994 by Herbert S. Wilf. This material may be reproduced for any educational purpose multiple copies may be made for classes etc. Charges if any for reproduced copies must be just enough to recover reasonable costs of reproduction. Reproduction for commercial purposes is prohibited. This cover page must be included in all distributed copies. Internet Edition Summer 1994 This edition of Algorithms and Complexity is available at the web site http www cis.upenn.edu wilf . It may be taken at no charge by all interested persons. Comments and corrections are welcome and should be sent to wilf@math.upenn.edu CONTENTS Chapter 0 What This Book Is About 0.1 Background.1 0.2 Hard vs. easy problems.2 0.3 A preview.4 Chapter 1 Mathematical Preliminaries 1.1 Orders of magnitude .5 1.2 Positional number systems. 11 1.3 Manipulations with series. 14 1.4 Recurrence relations. 16 1.5 Counting . 21 1.6 Graphs . 24 Chapter 2 Recursive Algorithms 2.1 Introduction. 30 2.2 Quicksort. 31 2.3 Recursive graph algorithms. 38 2.4 Fast matrix multiplication. 47 2.5 The discrete Fourier transform. 50 2.6 Applications of the FFT. 56 2.7 A review. 60 Chapter 3 The Network Flow Problem 3.1 Introduction. 63 3.2 Algorithms for the network flow problem. 64 3.3 The algorithm of Ford and Fulkerson. 65 3.4 The max-flow min-cut theorem. 69 3.5 The complexity of the Ford-Fulkerson algorithm . 70 3.6 Layered networks. 72 3.7 The MPM Algorithm. 76 3.8 Applications of network flow. 77 Chapter 4 Algorithms in the Theory of Numbers 4.1 Preliminaries. 81 4.2 The greatest common divisor. 82 4.3 The extended Euclidean algorithm. 85 4.4 Primality testing. 87 4.5 Interlude the ring of integers modulo n. 89 4.6 Pseudoprimality tests. 92 4.7 Proof of goodness of the strong pseudoprimality test. 94 4.8 Factoring and cryptography. 97 4.9 Factoring large integers. 99 4.10 Proving primality.100 iii .