Xem mẫu
- TOÁN RỜI RẠC
(DISCRETE MATHEMATICS)
Bùi Thị Thủy
Đặng Xuân Thọ
- Support
2
Full name: Đặng Xuân Thọ
Mobile: 091.2629.383
Email: thodx@hnue.edu.vn
Website: http://fit.hnue.edu.vn/~thodx/
Toán rời rạc - ĐHSPHN
- NỘI DUNG
3
Chương 1. Logic mệnh đề
Chương 2. Lý thuyết tập hợp
Chương 3. Một số công thức tổ hợp
Chương 4. Suy luận và kiểm chứng chương trình
Chương 5. Đại số Boole và cấu trúc mạch logic
Chương 6. Thuật toán
Chương 7. Lý thuyết đồ thị
Toán Rời Rạc - ĐHSPHN
- Chương 6. Thuật toán
4
Thuật toán (algorithm) là một trong những khái
niệm quan trọng trong lĩnh vực tin học.
Khái niệm thuật toán
Các đặc trưng của thuật toán
Phương pháp nào để biểu diễn thuật toán?
Mô tả từng bước
Sơ đồ khối
Ngôn ngữ giả mã
Toán Rời Rạc - ĐHSPHN
- 5 Khái niệm thuật toán
Toán Rời Rạc - ĐHSPHN
- Khái niệm bài toán
6
Bài toán trong phạm vi Tin học?
In dòng chữ ra màn hình
Giải phương trình bậc 2
Quản lý hồ sơ cán bộ
…
Dùng máy tính giải bài toán, 2 yếu tố quan tâm
INPUT
OUTPUT
Toán Rời Rạc - ĐHSPHN
- Phát biểu bài toán
7
Ví dụ 1: Bài toán tìm ước chung lớn nhất?
Ví dụ 2: Bài toán sắp xếp?
Ví dụ 3: Bài toán kiểm tra tính nguyên tố?
Ví dụ 4: Bài toán quản lý hồ sơ cán bộ?
BLACK OUTPUT
INPUT BOX
Toán Rời Rạc - ĐHSPHN
- Khái niệm giải thuật
8
Giải thuật hay còn gọi là thuật toán, thuật giải.
Định nghĩa: Là tập hữu hạn có thứ tự các
bước tác động trên một đối tượng dữ liệu
Input để sau một số hữu hạn lần thực hiện sẽ
cho ta kết quả Output.
Toán Rời Rạc - ĐHSPHN
- Ví dụ về giải thuật
9
Bài toán: Cho 3 số nguyên a, b, c. Mô tả giải
thuật tìm số lớn nhất trong 3 số đã cho.
Phân tích:
Input: 3 số nguyên a, b, c.
Output: số lớn nhất trong 3 số.
Toán Rời Rạc - ĐHSPHN
- Ví dụ về giải thuật
10
Bài toán: Cho 3 số nguyên a, b, c. Mô tả giải thuật tìm
số lớn nhất trong 3 số đã cho.
Thuật toán:
Bước 1. Gán max := a;
Bước 2. Nếu b > max thì gán max := b;
Bước 3. Nếu c > max thì gán max := c;
Tư tưởng của thuật toán là duyệt lần lượt giá trị của
từng số và giữ lại giá trị lớn nhất vào biến max.
Kết thúc thuật toán max cho số nguyên lớn nhất trong 3
số đã cho.
Toán Rời Rạc - ĐHSPHN
- 11
Bước 1: Gán max=a Max =a ;
Bước 2: nếu max
- Ví dụ về giải thuật
12
Bài toán: Cho 3 số nguyên a, b, c. Mô tả giải
thuật tìm số lớn nhất trong 3 số đã cho.
Theo dõi quá trình thực hiện của thuật toán
với giá trị cụ thể của a, b, c.
a := 1;
b := 5;
c := 3;
Toán Rời Rạc - ĐHSPHN
- Ví dụ về giải thuật
13
a = 1 b = 5 c = 3
Bước 1. Gán giá trị của a vào biến max max = 1
Bước 2. Do b > max (5 > 1) nên max gán bằng b max = 5
Bước 3. Do c < max (3 < 5) nên ko thực hiện gán max = 5
Toán Rời Rạc - ĐHSPHN
- Ví dụ về giải thuật
14
Một vài nhận xét:
Giải thuật nhận đầu vào là 3 số a, b, c và đưa kết
quả ở đầu ra là Max.
Các bước của giải thuật được mô tả chính xác.
Giải thuật kết thúc sau 3 bước và đưa ra lời giải
của bài toán, vì vậy giải thuật là hữu hạn
Nếu đầu vào là đã xác định, kết quả tại mỗi bước
của giải thuật được xác định duy nhất.
Giải thuật luôn đưa ra giá trị của số lớn nhất trong
3 số bất kì, như vậy giải thuật có tính tổng quát.
Toán Rời Rạc - ĐHSPHN
- Các đặc trưng của giải thuật
15
Đầu vào (Input): Giải thuật nhận dữ liệu vào từ một tập nào đó.
Đầu ra (Output): Với một tập các dữ liệu đầu vào, giải thuật đưa ra
các dữ liệu tương ứng với lời giải của bài toán.
Chính xác (Precision): Các bước của giải thuật được mô tả chính
xác.
Hữu hạn (Finiteness): Giải thuật phải đưa được đầu ra sau một số
hữu hạn bước với mọi đầu vào.
Đơn trị (Uniqueness): Các kết quả trung gian của từng bước thực
hiện giải thuật được xác định một cách đơn trị và chỉ phụ thuộc đầu
vào và các kết quả của các bước trước.
Tổng quát (Generality): Giải thuật có thể áp dụng để giải mọi bài
toán có dạng đã cho.
Toán Rời Rạc - ĐHSPHN
- Ví dụ lặp vô hạn
16
i=1 i = 1;
Do s = 1;
i=i*i While (s > 0)
While (i==1) s := s + i;
EndWhile
Toán Rời Rạc - ĐHSPHN
- 17 Biểu diễn thuật toán
Toán Rời Rạc - ĐHSPHN
- Biểu diễn thuật toán
18
Có nhiều phương pháp biểu diễn thuật toán.
Có thể biểu diễn bằng liệt kê các bước.
Có thể biểu diễn bằng sơ đồ khối.
Có thể mô tả giải thuật dùng giả mã
…
Một chương trình là sự biểu diễn của một
thuật toán trong ngôn ngữ lập trình đã chọn.
Thông thường các trình bày các thuật toán bởi
các thủ tục và hàm trong ngôn ngữ tựa
Pascal.
Toán Rời Rạc - ĐHSPHN
- Luyện tập
19
Biểu diễn thuật toán bằng 3 cách?
Bài 1: Kiểm tra một số có phải số nguyên tố
hay ko?
Bài 2: Tìm ước chung lớn nhất của hai số tự
nhiên?
Bài 3: Sắp xếp nổi bọt n phần tử.
Toán Rời Rạc - ĐHSPHN
- THANK YOU!
nguon tai.lieu . vn