zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cấu trúc dữ liệu và giải thuật (Data Structures & Algorithms) - Th.S Đỗ Văn Tiến

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:163

Báo xấu

4
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu và giải thuật (Data Structures & Algorithms) gồm có những nội dung: Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu; Chương 2: Các chiến lược thiết kế giải thuật; Chương 3: Cấu trúc dữ liệu động: con trỏ, danh sách liên kết, danh sách đơn; Chương 3: Ngăn xếp, hàng đợi; Chương 4: Tìm kiếm và sắp xếp; Chương 5: Cấu trúc Cây: cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng , B-tree, cây đỏ đen; Chương 6: Bảng băm; Chương 6: Đồ thị. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật (Data Structures & Algorithms) - Th.S Đỗ Văn Tiến

2/23/2019 Giới Thiệu Giảng Viên Th.S Đỗ Văn Tiến CẤU TRÚC DỮ LIỆU VÀ Email: tiendv@uit.edu.vn GIẢI THUẬT - Khoa Khoa Học Máy Tính, Trường Đại Học Công Nghệ Data Structures & Algorithms Thông Tin, ĐHQG TP.HCM - Lĩnh vực nghiên cứu: Computer Vision, Data Mining, Machine Learning, … Giới Thiệu Môn Học Mục tiêu môn học • Mã môn học: IT003 1. Rèn luyện tư duy thuật toán. • Số tín chỉ: 4 ( 3 LT + 1 TH) 2. Rèn luyện kỹ năng tự học thông qua việc tìm kiếm, • Vai trò của môn học trong chương trình: Cung cấp các kiến thức đọc các tài liệu chuyên ngành. và kỹ năng căn bản và tư duy thuật toán. 3. Nắm được một số khái niêm cơ bản của CTDL & GT. • Môn học tiên quyết: Nhập môn lập trình • https://courses.uit.edu.vn/ 4. Nắm một số CTDL và một số thuật giải cơ bản. • Group facebook môn học: Xem trên Course – Mọi thông tin thông 5. Sử dụng được ngôn ngữ lập trình (C++) để tổ chức báo đều được post trên đây và viết chương trình trên máy tính. 4 Hình thức đánh giá NỘI DUNG MÔN HỌC Thành phần đánh giá Hình thức Tỷ lệ Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu Quá trình Bài tập , 10% Chương 2: Các chiến lược thiết kế giải thuật điểm danh Chương 3: Cấu trúc dữ liệu động: con trỏ, danh sách liên ,… kết, danh sách đơn Thi giữa kỳ Thi viết 20% Chương 3: Ngăn xếp, hằng đợi Thực hành Lập trình 20% Chương 4: Tìm kiếm và sắp xếp LT Cuối kỳ Thi viết 40% Chương 5: Cấu trúc Cây: cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng , B-tree, cây đỏ đen Seminar nhóm 10% Chương 6: Bảng băm Chương 6: Đồ thị 5 6 1
2/23/2019 Các yêu cầu Các yêu cầu (1) Đi học và làm bài tập đầy đủ. Có vở riêng của môn học để: (2) Chủ động đặt câu hỏi và trao đổi trên group môn học. - Ghi chép các nội dung các bài lý thuyết (3) Làm thât nhiều bài tập …. - Làm bài tập trên lớp. (4) Tương tác trong lớp học (hỏi và trả lời) Vở dùng để: - Chấm các bài tập trên lớp - Điểm danh  một phần trong điểm quá trình 7 8 Cách học 1. Nghe giảng, chú ý tập trung để hiểu bài ngay tại lớp, nếu có gì không hiểu thì hỏi 2. Về nhà: làm lại theo hướng dẫn tại bài giảng để nắm ý tưởng, nếu có gì không hiểu thì hỏi. 3. Đọc giáo trình/tài liệu theo yêu cầu để nắm được nội dung chi tiết, nếu có gì không hiểu thì hỏi 4. Làm bài tập để thực sự hiểu nội dung đã học, nếu không hiểu đề bài thì hỏi, nếu không nhớ cách làm thì 9 quay lại bước 2 hoặc 3, nếu vẫn không được thì hỏi. 10 Cách học Cách học 5. Đến giờ thực hành để kiểm tra kết quả bài tập đã Quy tắc ứng xử: làm được và để được giáo viên giúp đỡ nếu gặp khó • Tôn trọng bản thân và tôn trọng người khác: không làm khăn. ồn, không để cho người khác làm ồn, không quay cóp.... Hỏi ở đâu? Hỏi giáo viên trên lớp, hỏi bạn, hỏi cả • Vào muộn ra sớm đừng xin phép lớp trên diễn đàn, group facebook. 7. Nếu không biết làm nhưng cũng không biết hỏi Lời khuyên: như thế nào? Hãy gặp giáo viên và trình bày tình • Nỗ lực bản thân là điều quan trọng nhất. trạng khó khăn của bạn. • Giáo viên không phải cái gì cũng biết. Cần thực hiện bước 2 càng sớm càng tốt sau giờ lý • Giáo viên có thể sai. Sách có thể sai. thuyết để tránh quên mất các nội dung vừa học. Không được để đến giờ thực hành mới đem bài giảng lần • Đừng ngại hỏi. No such thing as a stupid question trước ra đọc lại. 11 12 2
2/23/2019 Tài liệu tham khảo Các nguồn tài liệu khác • Google • Youtube ( Lập trình C, c++, Nhập môn lập trình ..) • Facebook group () • congdongcviet.com • https://stackoverflow.com Phần mềm thực hành Phần mềm thực hành • Code Blocks • http://www.codeblocks.org/downloads/26 17 3
3/3/2019 BẠN THƯỜNG LÀM GÌ KHI NHẬN MỘT BÀI TẬP LẬP TRÌNH ? CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Data Structures & Algorithms Các chiến lược thiết kế giải thuật 2 3 4 1. Vét cạn Nội dung 1. Vét cạn – Complete Search/Brute-force Search 2. Chia để trị – Divide and Conquer 3. Tham lam – Greedy 4. Qui hoạch động – Dynamic Programming Mỗi chiến lược có các tính chất riêng và chỉ thích hợp cho một số dạng bài toán nào đó. 6 1
3/3/2019 1. Vét cạn 8 Ví dụ: Vét cạn theo nghĩa thông thường là xét hết mọi đối tượng hay mọi trường hợp. Tìm vị trí số x trên dãy a gồm N số thực. • Input: dãy (a, N) – dãy gồm N số thực, số x – số cần tìm • Bài toán: Có một tập C các ứng viên và một • Output: số nguyên – vị trí của x trên a (-1 nếu a hàm f để đánh giá/cho điểm các ứng viên. Hãy tìm không có x) ứng viên được đánh giá/có điểm cao nhất. • Phương pháp giải: Duyệt tất cả các ứng viên, tính điểm cho từng ứng viên, sau đó lấy ứng viên có điểm cao nhất. 7 Giải thuật vét cạn Vét cạn – dạng thức chung • Ý tưởng: Thử tìm x tại từng vị trí của a, nếu tìm thấy Tìm lời giải cho bài toán P thì ngừng và báo vị trí. Nếu đã thử hết các vị trí mà 1. C  first(P) vẫn không thấy x thì báo -1 2. While (c  ) • Giải thuật: 1. If correct(P, c) Return c; 1. For pos = 0  N-1 2. c  next(P, c); 1. If (a[pos] = x) End While 1. Return pos 3. Return NULL; //không có lời giải EndFor 2. Return -1 1. Vét cạn 2. Chia để trị • Ưu điểm: luôn đảm bảo tìm ra nghiệm (nếu có) chính Chia bài toán thành các bài toán kích thước nhỏ có thể xác giải quyết độc lập. Sau đó kết hợp nghiệm các bài toán kích thước nhỏ thành nghiệm bài toán gốc • Nhược điểm: thời gian thực thi lớn 11 12 2
3/3/2019 2. Chia để trị 14 Ví dụ 1: Cho dãy a gầm N phần tử đã được sắp xếp theo chiều tăng dần. Tìm vị trí của phần tử x trong dãy a. • Chia bài toán thành các bài toán con nhỏ hơn • Giải quyết các bài toán con (thường dùng đệ • Input: dãy (a, N) – dãy gồm N số thực, số x – số cần quy) tìm • Output: số nguyên – vị trí của x trên a (-1 nếu a • Tổng hợp các kết quả từ bài toán con thành lời không có x) giải. 13 • Ý tưởng: Thử tìm x tại vị trí giữa (mid) của (a, left, right), nếu x=a[mid] thì ngừng và báo vị trí; nếu x < a[mid] thì tìm x ở đoạn Giải thuật: bên trái mid; ngược lại tìm x ở đoạn bên phải mid 1. left = 0; right = N-1 Tìm thấy 2 tại vị trí 1 2. While (left
3/3/2019 Lũy thừa nhanh – chia để trị Cài đặt đệ qui 1. double FastPower(double x, unsigned short N) 2. { 3. if (!N) //N == 0 4. return 1; 5. if (N & 1) //N % 2 == 1 6. return x * FastPower(x, N-1); 7. double y = FastPower(x, N/2); 8. return y*y; 9. } Cài đặt không đệ qui 3. Tham lam 1. double FastPower(double x, unsigned short N) Thực hiện từng bước một. Tại mỗi bước, chọn phương án được xem là tốt lúc đó. 2. { 3. double ans = 1; 4. while (N) { 5. if (N&1) ans *= x; 6. x = x*x; 7. N >>= 1; //N /= 2 8. } 9. return ans; 10. } 22 Ví dụ: Ý tưởng: Tìm tập con có tích lớn nhất của dãy a có N phần tử 1. Nếu dãy không có số 0 và có số số âm là chẵn: kết quả • Input: N – số nguyên không âm, a – dãy gồm N số là tích toàn bộ các số của dãy thực, • Output: số thực – tích lớn nhất 2. Nếu dãy chỉ có
3/3/2019 Giải thuật: 1. int MaxProduct(int a[], int N) 2. { 1. Xác định số lượng số 0 (count_0) và số lượng số âm 3. int count_0=0, count_neg=0, max_neg=INT_MIN, product=1; (count_neg), số âm lớn nhất (max_neg), tích các số 4. for (int i=0; i
3/3/2019 31 Cài đặt bằng C/C++ Bài tập 1. unsigned long Fibo(unsigned short N) 1. Thiết kế giải thuật dạng vét cạn để tìm tập con có tích 2. { lớn nhất của dãy a, cài đặt chương trình bằng 3. unsigned long FN, FN1, FN2; C/C++/Python 4. FN = FN1 = FN2 = 1; 2. Tìm hiểu giải thuật MergeSort, hãy cho biết đây là 5. for (unsigned short i=2; i
9/15/2018 Nội dung CẤU TRÚC DỮ LIỆU VÀ GIẢI 1. Vai trò của CTDL& GT. THUẬT 2. Các tiêu chuẩn đánh giá CTDL Data Structures & Algorithms Tổng Quan về CTDL và GT 3. Kiểu dữ liệu. 4. Thuật toán và độ phức tạp. Các khái niệm cơ bản Khái niệm cơ bản  Chương trình máy tính, phần mềm (Computer Chương trình máy tính Software): Danh sách các câu lênh, chỉ thị Lập trình (Programming) (Instruction) để máy tính thực hiện một chức năng Ngôn ngữ lập trình (Programming language) nào đó. Trình thông dịch (Interpreter) Trình biên dịch (compiler) TƯ DUY LẬP TRÌNH ? NGÔN NGỮ LẬP TRÌNH VS NGÔN NGỮ MÁY? Phương pháp giải quyết một bài toán trên máy tính 5 6 1
9/15/2018 NGÔN NGỮ MÁY? NGÔN NGỮ LẬP TRÌNH? • Ngôn ngữ máy (machine language) là các chỉ thị • Progamming language là ngôn ngữ dùng để viết các dưới dạng nhị phân, can thiệp trực tiếp vào trong các chương trình cho máy tính. mạch điện tử. • Cũng như các ngôn ngữ thông thường, NNLT cũng có từ vựng, cú pháp và ngữ nghĩa. • Chương trình được viết bằng ngôn ngữ máy thì có thể được thực hiện ngay không cần qua bước trung gian nào. 7 8 NGÔN NGỮ MÁY • Ngôn ngữ máy (machine language) là các chỉ thị dưới dạng nhị phân, can thiệp trực tiếp vào trong các mạch điện tử. • Chương trình được viết bằng ngôn ngữ máy thì có thể được thực hiện ngay không cần qua bước trung gian nào. Machine Language Language directly understood by the computer binary code 9 10 NGÔN NGỮ CẤP THẤP – HỢP NGỮ • VD: • Hợp ngữ (assembly language) được thiết kế để máy tính trở nên thân thiện hơn với người sử dụng. • Các câu lệnh bao gồm hai phần: phần mã lệnh (viết tựa tiếng Anh) chỉ phép toán cần thực hiện và phần tên biến chỉ địa chỉ chứa toán hạng của phép toán đó. Machine Language Symbolic Language Language directly English-like abbreviations understood by the representing elementary computer computer operations Tuy nhiên chương trình viết bằng ngôn ngữ máy dễ sai sót, cồng kềnh và khó đọc, khó hiểu vì toàn những con số 0 và 1. binary code assembly language 11 12 2
9/15/2018 NGÔN NGỮ CẤP THẤP – HỢP NGỮ • VD • Ngôn ngữ cấp cao (High level language): là ngôn ngữ được tạo ra và phát triển nhằm phản ánh cách thức người lập trình nghĩ và làm. • Ngôn ngữ cấp cao rất gần với ngôn ngữ con người (Anh ngữ) nhưng chính xác như ngôn ngữ toán học. Machine Language Symbolic Language High-level Language Language directly English-like abbreviations Close to human language. understood by the representing elementary Example: a = a + b computer computer operations [add values of a and b, and store the result in a, Ðể máy thực hiện được một chương trình viết bằng hợp ngữ thì replacing the previous chương trình đó phải được dịch sang ngôn ngữ máy. Công cụ value] thực hiện việc dịch đó được gọi là Assembler binary code assembly language C, C++, Java, Basic 13 14 Các lớp ngôn ngữ lập trình Natural Language Khái niệm cơ bản  Lập trình (programming): viết chương trình cho máy artificial intelligence 5GLs tính. ORACLE, SEQUEL, INGRES, ...  Lập trình viên (programer): người sử dung ngôn 4GLs ngữ lập trình để biên soạn các chương trình. C/C++, Pascal, Java, ... High level languages Hợp ngữ - Assembler Assembler languages Machine language 9/15/2018 thuonghtt@uit.edu.vn 15 Khái niệm cơ bản Khái niệm cơ bản  Mã nguồn: chương trình được thể hiện bằng NNLT.  Chương trình đích: dịch chương trình từ mã nguồn thành các ngôn ngữ ở cấp thấp hơn- thường là ngôn ngữ máy  Mã máy: chương trình bằng ngôn ngữ Máy 3
9/15/2018 THÔNG DỊCH(interpreted)  Khi chương trình chạy đến dòng lệnh nào sẽ chuyển thành mã máy đến đó để máy tính có thể thực thi.  Bộ thông dịch thực hiện quá trình thông dịch gọi là interpreter. 19 BIÊN DỊCH (compiled) Compiled vs interpreted  Chương trình sẽ dịch toàn bộ thành mã máy rồi mới tiến hành thực thi.  Bộ biên dịch thực hiện quá trình biên dịch được gọi là compiler Compiled vs interpreted Giải Bài Toán Trên Máy Tính 24 4
9/15/2018 DỮ LIỆU VS THÔNG TIN DỮ LIỆU (DATA) • Theo từ điển Tiếng Việt: số liệu, tư liệu đã có, được dựa vào để giải quyết vấn đề • Tin học: Biểu diễn các thông tin từ thế giới thực cần thiết cho bài toán được đưa vào máy tính. THÔNG TIN (INFORMATION) 28 Vấn đề - Bài Toán VAI TRÒ CỦA CTDL & GT • Biểu diễn vấn đề-bài toán • A→B • A: Giả thiết, điều kiện ban đầu • B: Kết luận, mục tiêu cần đạt • Giải quyết vấn đề-bài toán • Từ A dùng một số hữu hạn các bước suy luận có lý hoặc hành động thích hợp để đạt được B • Trong Tin học, A là đầu vào (input), B là đầu ra (output) 29 5
9/15/2018 VAI TRÒ CỦA CTDL & GT MỐI QUAN HỆ GIỮA CTDL & GT 1. Tổ chức biểu diễn các đối tượng thực tế CTDL + Giải thuật = Chương trình  Nhận định: Dữ liệu của con người đa dạng nhưng dữ liệu trên máy thì hạn chế và đơn giản  biểu diễn dữ liệu của con người lên trên máy tính?  Người LTphải thực hiện việc thiết kế, xây dựng các cấu trúc thích hợp nhất để biểu diễn dữ liệu xây dựng CTDL cho bài toán 2. Xây dựng thao tác xử lý dữ liệu  Cấu trúc dữ liệu: (có thể hiểu là) cách tổ chức dữ liệu, cách mô  Từ yêu cầu xử lý thực tế, xác định trình tự các thao tả bài toán dưới dạng NNLT tác máy tính phải thi hành để cho ra kết quả mong muốn  xây dựng giải thuật cho bài toán  Giải thuật: một quy trình để thực hiện một công việc xác định. Ngoài CTDL & GT cũng đóng vai trò thể hiện giải pháp CTDL Là gì ? Các Tiêu chuẩn của CTDL Cấu trúc dữ liệu 1. Phản ánh đúng thực tế: phải biểu diễn đầy đủ Các mô hình dữ liệu, tổ chức dữ liệu thông tin, thể hiện chính xác đối tượng thực tế (khai báo, lưu trữ dữ liệu) để biểu 2. Hiệu quả lưu trữ: tiết kiệm tài nguyên hệ thống diễn dữ liệu trừu tượng hóa. 3. Hiệu quả xử lý: đáp ứng việc thiết kế hiệu quả, phải phù hợp với các thao tác trên đó, phù hợp với điều kiện cho phép của NNLT. Mô hình: • Diễn đạt toán học • Diễn đạt bằng các sơ đồ, biểu đồ Biểu diễn kiểu dữ liệu Các thuộc tính của kiểu dữ liệu T = V = {Tập các giá trị} • Tên KDL O = {Tập các thao tác xử lý} • Miền giá trị • Kích thước lưu trữ Ví dụ: Kiểu dữ liệu số nguyên int trong ngôn ngữ C • Tập các toán tử tác động lên KDL T = int V = {-32768, 32767} O = {+, -, *, /, %} 35 6
9/15/2018 Các Kiểu Dữ Liệu Cơ Bản Kiểu dữ liệu phần cứng (hardware data type) Ở cấp phần cứng máy tính: Kiểu dữ liệu phần cứng  Xây dựng sẵn 1 tập kiểu dữ liệu phần cứng (sơ cấp): bit, byte, kiểu số nhị phân, kiểu ký tự, … Kiểu dữ liệu cơ bản  Cơ chế điều khiển: tuần tự và rẽ nhánh.  Các tác vụ phần cứng: như cộng 2 số ở 2 địa chị bộ nhớ Kiểu dữ liệu có cấu trúc khác nhau rồi lưu kết quả tại 1 địa chỉ khác, dời 1 byte, … Kiểu dữ liệu trừu tượng  chỉ phù hợp cho máy chứ không phù hợp với con người . Các kiểu dữ liệu cơ bản (basic data type) Các kiểu dữ liệu cơ bản (basic data type)  Loại dữ liệu đơn giản, không có cấu trúc, giá trị dữ  Cơ chế điều khiển: liệu là đơn nhất. - Tuần tự  Các NNLT xây dựng sẵn như một thành phần của ngôn - Chọn lựa/rẽ nhánh (if, if/else, switch) ngữ (kiểu dữ liệu định sẵn). - Lặp (for, while, do …while)  Tùy NNLT, các kiểu dữ liệu có thể khác nhau đôi  Các tác vụ cài đặt trong NNLT: hàm thư viện, chương chút. trình con (hàm/thủ tục)  Bao gồm:  Khi dịch chương trình viết bằng NNLT, các kiểu dl cơ bản - Kiểu có thứ tự rời rạc: số nguyên, ký tự, boolean, liệt kê, … và tác vụ của nó chuyển dịch về các kiểu dl sơ cấp và - Kiểu không rời rạc: số thực tác vụ phần cứng để máy tính có thể thực thi được Ví du basic data type Kiểu dữ liệu có cấu trúc Data type Size Value range -128 đến 127 char 1 byte hoặc 0 đến 255 (Ký tự dạng mã ASCII) • Do người dùng định nghĩa. unsigned char 1 byte 0 đến 255 signed char 1 byte -128 đến 127 • Gom nhóm/liên kết các thành phần dữ liệu có 2 hoặc -32,768 đến 32,767 int 4 bytes hoặc -2,147,483,648 đến 2,147,483,647 kiểu dữ liệu đã được định nghĩa thành một kiểu unsigned int 2 hoặc 0 đến 65,535 dữ liệu phức hợp nhiều thành phần. 4 bytes hoặc 0 đến 4,294,967,295 short 2 bytes -32,768 đến 32,767 unsigned short 2 bytes 0 đến 65,535 long 4 bytes -2,147,483,648 đến 2,147,483,647 unsigned long 4 bytes 0 đến 4,294,967,295 41 7
9/15/2018 Kiểu dữ liệu có cấu trúc Kiểu dữ liệu trừu tượng (Abstract data type - ADT) Chuỗi ký tự (string) • Thông tin ngoài trạng thái tĩnh (dữ liệu) còn ngầm định các hoạt tính của nó (tác vụ). Mảng (array) VD: Phân/số , Tác vụ nhân Cấu trúc (struct) • Để xây dựng những kiểu dữ liệu mới phức tạp hơn người ta dùng 1 công cụ gọi là trừu tượng Con trỏ (pointer) hóa. Kết quả của quá trình trừu tượng hóa là hình thành một kiếu dữ liệu mới gọi là kiểu dữ Tập tin .(file) liệu trừu tượng. . Kiểu dữ liệu trừu tượng (Abstract data type - ADT) Kiểu dữ liệu trừu tượng (Abstract data type - ADT) • Mỗi kiểu dữ liệu trừu tượng có mô tả dữ liệu và các tác Trừu tượng hóa vụ liện quan. Ý niệm về sự vật, hiện tượng sau khi thu thập chắt lọc những thông tin có nghĩa, loại bỏ những thông tin không • Vấn đề tiếp theo là cài đặt nó thành CTDL và các đoạn cần thiết, không quan trọng chương trình. • Các kiểu dữ trừu tượng và CTDL thông dụng: - Ngăn xếp (stack) hàng đợi (queue) - danh sách (list) cây (tree) • Trừu tượng hóa dữ liệu - bảng băm (hash table) đồ thị (graph) • Trừu tượng hóa chức năng Các bước xây dựng chương trình Kiểu dữ liệu trừu tượng (Abstract data type - ADT) Thực hiện CT Chạy thử • ADT là 1 kiểu dữ liệu do ta định nghĩa ở mức khái niệm, Lỗi và cách sửa: Lỗi cú pháp, Lỗi ngữ nghĩa chưa được cài đặt cụ thể bằng NNLT. Xây dựng bộ dữ liệu test Hiệu chỉnh CT • Khi cài đặt 1 ADT trên 1 NNLT cụ thể, phải làm 2 động Cài đặt thành CTDL, đoạn CT cụ thể Diễn tả thuật toán theo NNLT đã chọn tác: Cài đặt chương trình 1.Biểu diễn kiểu dữ liệu = 1 CTDL hoặc ADT khác đã Dùng công cụ trừu tượng Biểu diễn bằng: hóa xây dựng ADT và được cài đặt thuật toán Ngôn ngữ tự nhiên Lưu đồ - Sơ đồ khối Xây dựng ADT và thuật toán Mã giả 2.Viết các CT con thực hiện các phép toán tên kiểu dữ Mô hình và giải liệu này thuật hình thức Lựa chọn phương pháp giải Xây dựng mô hình bài toán Phân tích Xác định vấn đề và đặt tả vấn đề 8
9/15/2018 Thuật toán - Algorithm Các tính chất - yêu cầu của thuật toán  Là tập hợp (dãy) hữu hạn các chỉ thị (hành động) được định • Tính chính xác/đúng: nghĩa rõ ràng nhằm giải quyết một bài toán cụ thể nào đó. • Quá trình tính toán hay các thao tác máy tính thực hiện là chính xác.  Thuật toán để giải một bài toán là một dãy hữu hạn các thao • Khi kết thúc, giải thuật phải cung cấp kết quả đúng đắn. tác được sắp xếp theo một trình tự xác định sao cho sau khi • Tính phổ dụng/tổng quát: thực hiện dãy thao tác đó, từ Input của bài toán, ta nhận • Có thể áp dụng cho một lớp các bài toán có đầu vào tương tự được Output cần tìm. nhau. • Tính kết thúc/hữu hạn: • Thuật toán phải dừng sau một số bước hữu hạn. Các tính chất - yêu cầu của thuật toán Đặc tả một thuật toán • Tính rõ ràng/hiệu quả: Các câu lệnh minh bạch được sắp xếp theo thứ tự nhất định. Tối ưu về mặt thời gian và không gian. • Tính khách quan/xác định: • Được viết bởi nhiều người trên máy tính nhưng kết quả phải như nhau. • Trong cùng một điều kiện hai bộ xử lý cùng thực hiện, thuật toán phải cho những kết quả giống nhau. Đặc tả một thuật toán Các phương pháp biểu diễn thuật toán • Dữ liệu vào. 1. Dùng ngôn ngữ tự nhiên. • Điều kiện ràng buộc (nếu có). 2. Dùng mã giả (pseudocode) • Các sản phẩm ,kết quả (xuất). 3. Dùng lưu đồ - sơ đồ khối (flowchart) • Các yêu cầu trên sản phẩm, kết quả. 4. Ngôn ngữ lập trình (chương trình) 9
9/15/2018 1. Dùng ngôn ngữ tự nhiên 1. Dùng ngôn ngữ tự nhiên Đầu vào: a, b thuộc R • Sử dụng ngôn ngữ thường ngày để liệt kê các bước Đầu ra: nghiệm phương trình ax + b = 0 của thuật toán. 1. Nhập 2 số thực a và b. • Phương pháp biểu diễn này không yêu cầu người viết 2. Nếu a = 0 thì thuật toán cũng như người đọc thuật toán phải nắm các quy 2.1. Nếu b = 0 thì 2.1.1. Phương trình vô số nghiệm tắc. 2.1.2. Kết thúc thuật toán. • Tuy vậy, cách biểu diễn này: 2.2. Ngược lại • Thường dài dòng, 2.2.1. Phương trình vô nghiệm. • Không thể hiện rõ cấu trúc của thuật toán, 2.2.2. Kết thúc thuật toán. 3. Ngược lại • Đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. 3.1. Phương trình có nghiệm. • Gần như không có một quy tắc cố định nào trong việc thể 3.2. Giá trị của nghiệm đó là x = -b/a hiện thuật toán bằng ngôn ngữ tự nhiên. 3.3. Kết thúc thuật toán. 2. Dùng mã giả 2. Dùng mã giả •Đầu vào: VD: Giải a, btrình phương thuộc R ax+b=0 • Ngôn ngữ tựa ngôn ngữ lập trình: Đầu ra: nghiệm phương trình ax + b = 0 Dùng cấu trúc chuẩn hóa, chẳng hạn tựa Pascal, C. If a = 0 Then Begin Dùng các ký hiệu toán học, biến, hàm. If b = 0 Then • Ưu điểm: Xuất “Phương trình vô số nghiệm” Else Đỡ cồng kềnh Xuất “Phương trình vô nghiệm” • Nhược điểm: End Else Không trực quan. Xuất “Phương trình có nghiệm x = -b/a” 57 3. Dùng lưu đồ 3. Dùng lưu đồ Là phương thức để biểu diễn thuật toán thông qua các Bắt đầu ký hiệu hình học Đọc a,b Đ S a= 0 Đ S Tính b= 0 x = -b/a Xuất Xuất Xuất x “VSN” “VN” Kết thúc 60 10
9/15/2018 Thuật toán - Algorithm Đánh giá độ phức tạp của thuật toán Qui trình thiết kế thuật toán • Khảo sát, phân tích • Thiết kế (CTDL, thuật toán) • Mã hóa, viết chương trình • Kiểm tra • Thực hiện • Bảo trì, phát triển Kỹ thuật thiết kế thuật toán Vét cạn Đệ qui Chia để trị Quy hoạch động Đánh giá độ phức tạp của thuật toán Đánh giá độ phức tạp của thuật toán • Là công việc ước lượng thời gian thực hiện của thuật toán để so sánh tương đối các thuật toán với nhau  Phương pháp thực nghiệm (thời gian)  Làm sao ước lượng thời gian thực hiện của thuật toán? Phương pháp xấp xỉ (số bước thực hiện) Đánh giá độ phức tạp của thuật toán Đánh giá độ phức tạp của thuật toán • Cài thuật toán rồi chọn các bộ dữ liệu thử nghiệm.  Đơn vị đo thời gian thực hiện = số các lệnh được thực • Thống kê các thông số nhận được khi chạy các bộ dữ liệu đó. hiện trong một máy tính lý tưởng • Đơn vị đo: giờ, phút, giây. VD: Tính tổng các số nguyên dương từ 1n • Ưu điểm: Dễ thực hiện. int Tong (int n){ • Nhược điểm: int S=0; for (int i = 1; i

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright ©2025 TaiLieu.VN. All rights reserved.