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

Thuật ngữ thuật toán (Algorithm ) là từ viết tắt của tên một nhà toán học ở thế kỷ IX : Abu Jafa Mohammed ibn Musa al-Khowarizmi . Đầu tiên, thuật toán được hiểu như là các quy tắc thực hiện các phép toán số học với các con số được viết trong hệ thập phân. Cùng với sự phát triên của máy tính , khái niệm thuật toán được hiểu theo nghĩa rộng hơn. Một định nghĩa hình thức về thuật toán được nhà toán học người Anh là Alanh Turing đưa ra vào năm 1936 thông qua máy...
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 GIÁO TRÌNH THIẾT KẾ VÀ ĐÁNH GIÁ THUẬT TOÁN TRẦN TUẤN MINH Khoa Toán Tin 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 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 ........................................................ - 43 - 5. Ca ...