Giáo trình Thiết kế và đánh giá thuật toán - Trần Tuấn Minh

Giáo trình "Thiết kế và đánh giá thuật toán" có nội dung tiếp sau giáo trình "cấu trúc dữ liệu và thuật toán 1" và "toán cao cấp A4", trình bày trong 3 tín chỉ lý thuyết và 1 tín chỉ thực hành cho các sinh viên ngành Toán-Tin học và Công nghệ thông tin.Trọng tâm chính của giáo trình : Trình bày một số phương pháp thiết kế thuật toán thông dụng, tìm hiểu cơ sở phân tích độ phức tạp của thuật... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Giáo trình Thiết kế và đánh giá thuật toán - Trần Tuấn Minh Khoa toán – tin học GIÁO TRÌNH THIẾT KẾ VÀ ĐÁNH GIÁ THUẬT TOÁN Trần Tuấn Minh Thieát keá vaø ñaùnh giaù thuaät toaùn -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 Thieát keá vaø ñaùnh giaù thuaät toaùn -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 - 5. Caøi ñaët ................................................................................. - 36 - IV. Thuaät toaùn QuickSort ........................................................... - 36 - 1. YÙ töôûng ................................................................................ - 37 - 2. Moâ taû thuaät toaùn .................................................................. - 37 - 3. Ñoä phöùc taïp cuûa thuaät toaùn .................................................. - 38 - V. Thuaät toaùn nhaân Strassen nhaân 2 ma traän.............................. - 39 - 1. Baøi toaùn ............................................................................... - 39 - 2. Moâ taû ................................................................................... - 39 - VI. Baøi toaùn hoaùn ñoåi 2 phaàn trong 1 daõy.................................. - 41 - 1. Phaùt bieåu baøi toaùn................................................................ - 41 - 2. YÙ töôûng ................................................................................ - 41 - 3. Thuaät toaùn ........................................................................... - 41 - 4. Ñoä phöùc taïp thuaät toaùn ...... ...