thiết kế và đánh giá thuật toán - trần tuấn minh -1

Ta dùng một mảng logic Daxet[ ] để đánh dấu các đỉnh được thăm, mảng này được khởi động bằng 0 tất cả để chỉ rằng lúc đầu chưa đỉnh nào được thăm. Một mảng trước để lưu trữ các đỉnh nằm trên đường đi ngắn nhất.
Nội dung trích xuất từ tài liệu:
thiết kế và đánh giá thuật toán - trần tuấn minh -1 Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 1 - MUÏC LUÏC LÔØI NOÙI ÑAÀU .................................................................................. - 6 - Chöông 1 : GIÔÙI THIEÄU THIEÁT KEÁ, ÑAÙNH GIAÙ THUAÄT TOAÙN . - 8 - I. Ñònh nghóa tröïc quan veà Thuaät toaùn........................................... - 8 - 1. Ñònh nghóa ............................................................................. - 8 - 2. Caùc ñaëc tröng cô baûn cuûa thuaät toaùn ...................................... - 9 - 3. Ñaëc taû thuaät toaùn .................................................................. - 9 - II. Caùc daïng dieãn ñaït thuaät toaùn .................................................... - 9 - 1. Daïng löu ñoà ( sô ñoà khoái ) ................................................... - 10 - 2. Daïng ngoân ngöõ töï nhieân ...................................................... - 10 - 3. Ngoân ngöõ laäp trình............................................................... - 10 - 4. Daïng maõ giaû ........................................................................ - 10 - III. Thieát keá thuaät toaùn ................................................................ - 12 - 1. Modul hoùa vaø thieát keá töø treân xuoáng (Top-Down)............... - 13 - 2. Phöông phaùp laøm mòn daàn (hay tinh cheá töøng böôùc )........... - 13 - 3. Moät soá phöông phaùp thieát keá ............................................... - 15 - IV. Phaân tích thuaät toaùn............................................................... - 17 - 1. Caùc böôùc trong quaù trình phaân tích ñaùnh giaù thôøi gian chaïy cuûa thuaät toaùn ................................................................................ - 17 - 2. Caùc kyù hieäu tieäm caän .......................................................... - 18 - 3. Moät soá lôùp caùc thuaät toaùn ................................................... - 19 - 4. Phaân tích thuaät toaùn ñeä qui. ................................................. - 21 - 5. Caùc pheùp toaùn treân caùc kyù hieäu tieäm caän ............................ - 25 - 6. Phaân tích tröôøng hôïp trung bình .......................................... - 26 - V. Toái öu thuaät toaùn .................................................................... - 27 - 1. Kyõ thuaät toái öu caùc voøng laëp ................................................ - 27 - 2. Toái öu vieäc reõ nhaùnh ........................................................... - 30 - Baøi taäp ..................................................................................... - 30 - Chöông 2 : PHÖÔNG PHAÙP CHIA ÑEÅ TRÒ .................................. - 33 - I. Môû ñaàu..................................................................................... - 33 - 1. YÙ töôûng ................................................................................ - 33 - 2. Moâ hình ............................................................................... - 33 - II. Thuaät toaùn tìm kieám nhò phaân................................................. - 33 - 1. Phaùt bieåu baøi toaùn................................................................ - 33 - 2. YÙ töôûng ................................................................................ - 33 - 3. Moâ taû thuaät toaùn .................................................................. - 33 - Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 2 - 4. Ñoä phöùc taïp thôøi gian cuûa thuaät toaùn ................................... - 34 - 5. Caøi ñaët ................................................................................. - 34 - III. Baøi toaùn MinMax .................................................................. - 35 - 1. Phaùt bieåu baøi toaùn................................................................ - 35 - 2. YÙ töôûng ................................................................................ - 35 - 3. Thuaät toaùn ........................................................................... - 35 - 4. Ñoä phöùc taïp thuaät toaùn ........................................................ - 36 - ...