【视频】计算机：算法 17 Shortest Paths I: Properties, Dijkstra's Algorithm
Introduction to Algorithms- Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search8h4a!aX O5N[:q PeT
[attach]287[/attach]
Cover of 6.046J textbook, Introduction to Algorithms, Second Edition, by Cormen, Leiserson, Rivest, and Stein. (Image courtesy of MIT Press.) 5c9h|6o A0aY8r }o
z oN)TSw jC5b
[b]Course Description[/b]
This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing.
This course was also taught as part of the Singapore-MIT Alliance (SMA) programme as course number SMA 5503 (Analysis and Design of Algorithms).4|(\4wm v g-m;YU$R
[b]Textbook[/b]p-i(?#@W`
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press. ISBN: 0262032937.
+i'o GX2@0v@+w+[
【观看视频】(因网络原因，有时需耐心等待5-10秒以上时间)](s.k\3y ] C"K K
[flash]http://www.tudou.com/v/pCHdqmnkioc[/flash] S|+a`7b.kZN
【下载讲义】$OR+\F s VA,q
[attach]288[/attach] [b]Useful References 参考书目[/b]
/Z eY-p)@a$U.R(I6N
1. Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. [i]The Design and Analysis of Computer Algorithms[/i]. Reading, MA: Addison-Wesley, 1974. ISBN: 0201000296.F;\c8_ ?8Ve%z
The classic text, but it lacks topics in network flows and linear programming, as well as more recent algorithms.
2. [i]Data Structures and Algorithms [/i]Reading, MA: Addison-Wesley, 1983. ISBN: 0201000237.7U |z*E2w
Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms.(C6gW&q/t2{/Wm I4T*t z D
2CIurw
3. Baase, Sara. [i]Computer Algorithms: Introduction to Design and Analysis[/i] 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201060353.
General reference, although the exposition is sometimes terse or sketchy.+TR0Fi*X MD
4. Bentley, Jon Louis. [i]Programming Pearls.[/i] Reading, MA: Addison-Wesley, 1986. ISBN: 0201103311.P8{Vx\,t
Applications of algorithm design techniques to software engineering.
5. [i]More Programming Pearls: Confessions of a Coder[/i]. Reading, MA: Addison-Wesley, 1988. ISBN: 0201118890.+n:y2\B1d!A i@F
More applications of algorithm design techniques to software engineering.T3V$L l!m,t!x#Z q
(Wwy _9M2a
6. [i]Writing Efficient Programs.[/i] Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0139702512.
Performance hacking extraordinaire.3XT,p9k3d&~
8R/]6{ Iv-e T}#I)` z
7. Brassard, Gilles, and Paul Bratley. [i]Algorithmics: Theory and Practice.[/i] Englewood Cliffs, NJ: Prentice-Hall, 1988. ISBN: 0130232432.
Good examples and problems. Focus on methods rather than specific problems.
4j.P{ G;S)K
8. Chung, Kai Lai. [i]Elementary Probability Theory with Stochastic Processes[/i].New York, NY: Springer-Verlag, 1974. ISBN: 0387900969.
Intuitive introduction to probability.
9. Even, Shimon. [i]Graph Algorithms. [/i]Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218.
Broad treatment of graph algorithms, including network flow and planarity.
10. Feller, William. [i]An Introduction to Probability Theory and Its Applications[/i]. 3rd ed. 2 vols. New York, NY: John Wiley & Sons, 1968, 1971. ISBN: 0471257087. ISBN: 0471257095.\*~x FC/v"|PEB8b
Excellent reference for probability theory.;{0~.k)b Xon pB
11. Garey, Michael R., and David S. Johnson. [i]Computers and Intractibility: A Guide to the Theory of NP-Completeness[/i]. San Francisco, CA: W. H. Freeman & Co., 1979. ISBN: 0716710447.$X7rr(FFg5l*v
Reference book devoted to NP-completeness. The second half contains an extensive list of NP-complete problems and references to algorithms in the literature for polynomial-time special cases.2j4T8H:x ?(M'NI0i r
12. Gonnet, Gaston H. [i]Handbook of Algorithms and Data Structures[/i]. Reading, MA: Addison-Wesley, 1984. ISBN: 020114218X. N7sj i4K&m
Code in Pascal and C, comparisons of actual running times, and pointers to analysis in research papers.
_:K&K k k
13. Gusfield, Dan. [i]Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[/i]. Cambridge, UK: Cambridge University Press, 1997. ISBN: 0521585198.
General treatment of algorithms that operate on character strings and sequences. L8^%V'{1_
7| rNl1ZiL8J a
14. Horowitz, Ellis, and Sartaj Sahni. [i]Fundamentals of Computer Algorithms[/i]. Potomac, MD: Computer Science Press, 1978. ISBN: 0914894226. T P%?(w8DtO
Good on data structures, dynamic programming, and branch-and-bound algorithms.Ir qs?a#lP a
15. Kingston, Jeffrey H.[i] Algorithms and Data Structures: Design, Correctness, Analysis[/i]. Reading, MA: Addison-Wesley Publishing Co., 1991. ISBN: 0201417057.8t"Ir:lE:P*o E
A nice introductory book on data structures, with a good chapter on algorithm correctness.
M.N U7W"n*?u
16. Knuth, Donald E. [i]The Art of Computer Programming[/i]. 3rd ed. 3 vols. Reading, MA: Addison-Wesley, 1997. ISBN: 0201896834. ISBN: 0201896842. ISBN: 0201896850.n*@z X%EJ%f)y(A
Encyclopedic work in three volumes: (1) Fundamental Algorithms, (2) Seminumerical Algorithms, and (3) Sorting and Searching.
17. Lawler, Eugene L. [i]Combinatorial Optimization: Networks and Matroids[/i]. New York, NY: Holt, Rinehart, and Winston, 1976. ISBN: 0030848660.
Graph algorithms (dense graphs), network flows, and linear programming. First few chapters are excellent.
,B"P5fz`(s)b`
18. Liu, Chung L. [i]Introduction to Combinatorial Mathematics[/i]. New York, NY: McGraw-Hill, 1968. ISBN: 0070381240.7h0{%hQ/\#g+c
Combinatorial mathematics relevant to computer science. Excellent problems.D9X%c sK
19. Manber, Udi. [i]Introduction to Algorithms: A Creative Approach[/i]. Reading, MA: Addison-Wesley, 1989. ISBN: 0201120372.6X!\}B F
Elementary text with an emphasis on creativity.
2] UMOM%k,FQ_3I
20. Mehlhorn, Kurt. [i]Data Structures and Algorithms[/i]. 3 vols. New York, NY: Springer-Verlag, 1984. ISBN: 038713302X. ISBN: 354013641X. ISBN: 0387136428. [B2Pz3s{t
Three volumes: (1) Sorting and Searching, (2) Graph Algorithms and NP-Completeness, and (3) Multidimensional Searching and Computational Geometry. Lecture notes on basic and advanced topics.
's \ `@/KB,V
21. Niven, Ivan, and Herbert S. Zuckerman. [i]An Introduction to the Theory of Numbers[/i]. 4th ed. New York, NY: John Wiley & Sons, 1980. ISBN: 0471028517. _K6Q1CP"u
Readable introduction to number theory.
$g6B!p |;U
22. Papadimitriou, Christos H., and Kenneth Steiglitz. [i]Combinatorial Optimization: Algorithms and Complexity[/i]. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0131524623.3Mvm"DF,l0x9w[
Linear programming and its variants.
23. Press, William P., Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. [i]Numerical Recipies in C: The Art of Scientific Computing[/i]. Cambridge, UK: Cambridge University Press, 1988. ISBN: 052135465X.+_6^In vl
Code for numerical algorithms./G u"@O!R.u^
nch7`y8z
24. Reingold, Edwin M., Jurg Nievergelt, and Narsingh Deo. [i]Combinatorial Algorithms: Theory and Practice.[/i] Englewood Cliffs, NJ: Prentice-Hall, 1977. ISBN: 013152447X.
Good on recurrence relations and binary search trees.
(TTD:a FH
25. Sedgewick, Robert. [i]Algorithms[/i]. 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201066734.
Elementary text with an excellent breadth of topics. Light on analysis, but lots of figures.@'S b _p})C3UT
26. Sipser, Michael. [i]Introduction to the Theory of Computation[/i]. Boston, MA: PWS Publishing Company, 1997. ISBN: 053494728X. _5c6{|j0i
A good text on computability and complexity theory.#kBg!r(U-T'^L_
-]*{&cmh
27. Tarjan, Robert Endre. [i]Data Structures and Network Algorithms[/i]. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1983. ISBN: 0898711878.
Advanced book with tons of good stuff.
Oo ? in"M
[[i] 本帖最后由 NOOODLE 于 2008-12-21 11:40 编辑 [/i]] very good !
页:
[1]