Kiến trúc máy tính - Giải quyết vấn đề và thiết kế thuật toán

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG •Những vấn đề nào được giải quyết bằng máy tính ? •Cách giải quyết vấn đề bằng máy tính Giải quyết vấn đề và thiết kế thuật toán Giải quyết vấn đề và thiết kế thuật toán • Vấn đề ? Một khó khăn cần được giải quyết. • Giải quyết vấn đề: là việc tìm ra một giải pháp cho câu hỏi rắc rối, phức tạp, khó hiểu • Máy tính không thể dùng để giải quyết các vấn đề liên quan đến hành động vật lý hoặc biểu thị cảm xúc • Máy tính chỉ làm được những gì mà nó được bảo phải làm. Máy tính không thông minh, nó không thể tự phân tích vấn đề và đưa ra giải pháp. • Lập trình viên là người phân tích vấn đề, tạo ra các chỉ dẫn để giải quyết vấn đề (chương trình), và máy tính sẽ thực hiện các chỉ dẫn đó. Giải quyết vấn đề và thiết kế thuật toán • Phương pháp giải quyết vấn đề thông thường: 4 bước – Bước 1: Hiểu vấn đề: cái gì chưa biết, cái gì là dữ liệu, cái gì là điều kiện – Bước 2: Đưa ra một phương án: tìm mối quan hệ giữa dữ liệu và những thứ chưa biết, có thể tham khảo từ cách giải quyết các vấn đề tương tự – Bước 3: Thực hiện phương án – Bước 4: Kiểm tra lại lời giải thu được Giải quyết vấn đề và thiết kế thuật toán • Phương án được gọi là thuật toán trong tính toán • Một thuật toán là: – một dãy hữu hạn các thao tác và trình tự thực hiện các thao tác đó sao cho sau khi thực hiện dãy thao tác này theo trình tự đã chỉ ra, với đầu vào (input) ta thu được kết quả đầu ra (output) mong muốn. Giải quyết vấn đề và thiết kế thuật toán Giải quyết vấn đề bằng máy tính • Giai đoạn phát triển thuật toán – Phân tích: hiểu vấn đề – Đề xuất thuật toán: đưa ra các bước tuần tự giải bài toán – Kiểm tra thuật toán: theo các bước để kiểm tra lại thuật toán • Giai đoạn triển khai – Code: chuyển thuật toán thành chương trình – Kiểm tra: thực hiện trên máy tính, kiểm tra kết quả và sửa đổi nếu cần • Giai đoạn bảo trì – Sử dụng: Dùng chương trình – Bảo trì: sửa đổi chương trình cho phù hợp yêu cầu mới hoặc để sửa lỗi. Giải quyết vấn đề và thiết kế thuật toán Pha giải quyết vấn đề Pha triển khai, cài đặt Giải quyết vấn đề và thiết kế thuật toán • Xây dựng thuật toán: – Phương pháp thiết kế top-down (phân ra hàm - functional decomposition): chia vấn đề thành các vấn đề nhỏ hơn(module), các vấn đề nhỏ lại được chia tiếp cho đến khi nó đủ nhỏ để có thể xử lý trực tiếp – Phương pháp thiết kế hướng đối tượng: dữ liệu và các thuật toán xử lý dữ liệu được kết hợp với nhau trong một lớp (class) hoặc đối tượng (object) Phương pháp thiết kế top-down • Phương pháp thiết kế top-down Phương pháp thiết kế top-down VD. Bài toán tổ chức 1 buổi tiệc lớn. • Bài toán có thể chia nhỏ thành : – Mời mọi người – Chuẩn bị đồ ăn • Mời mọi người: Chưa thể gọi điện để mời vì ta chưa biết cần mời những ai. Do đó thao tác này được chia tiếp – Lên danh sách khách – Gọi điện cho khách • Lên danh sách: – Ghi tên bạn bè – Chờ 1 ngày để xem còn quên ai – Kiểm tra và bổ sung vào danh sách Phương pháp thiết kế top-down • Chia nhỏ bài toán Phương pháp thiết kế top-down • VD, Với bài toán con là viết tên khách mời (write down name): – Bạn có giấy chưa ? • Chưa có thì lấy giấy – Bạn có bút chưa? • Chưa có thì lấy bút (mua bút) – Cầm bút và viết tên khách mời lên giấy Phương pháp thiết kế top-down • Trong máy tính cũng tương tự, ta có thể dùng ngôn ngữ tự nhiên hoặc giả mã để biểu diễn thuật toán. • Nếu dùng mã giả (pseudocode) – Dùng while, repeat để biểu diễn các thao tác lặp đi lặp lại – Dùng if để biểu diễn khi phải lựa chọn 1 trong 2 các thao tác để thực hiện. – Dùng write để biểu diễn việc hiển thị ra (màn hình) – Dùng read để biểu diễn việc đọc vào (từ bàn phím) Phương pháp thiết kế top-down • VD. Bài toán lên và in ra danh sách khách mời theo thứ tự chữ cái. • Bài toán chia thành 3 module: Mức 0 – Nhập vào thông tin khách – Sắp xếp danh sách theo thứ tự chữ cái – In ra danh sách Phương pháp thiết kế top-down • Nhập vào thông tin khách Mức 1 – Nhập vào từ bàn phím – Kiểm tra đủ thông tin – Thêm vào danh sách Phương pháp thiết kế top-down • Nhập vào từ bàn phím Mức 2 – write “Nhập vào thông tin khách” – write “Nhập tên” – read họtên – write “Nhập địa chỉ” – read địachỉ – write “Nhập số điện thoại” – read sốđiệnthoại Phương pháp thiết kế top-down • Kiểm tra đủ thông tin Mức 2 – if (thiếu họtên) • write “Nhập họ tên” • read họtên – if (thiếu địachỉ) • write “Nhập địa chỉ” • read địachỉ – if (thiếu Sốđiệnthoại) • write “Nhập số điện thoại” • read Sốđiệnthoại Phương pháp thiết kế hướng đối tượng • Phương pháp thiết kế hướng đối tượng: Xây dựng lời giải của bài toán theo các thực thể nội tại được gọi là các đối tượng. Mỗi đối tượng bao gồm cả dữ liệu và các thao tác để xử lý dữ liệu đó • Các đối tượng tương tự nhau được mô tả bằng 1 lớp – class. VD. Mặc dù 2 sinh viên khác nhau nhưng có các đặc điểm và hành vi chung: đều là người và cùng tham gia khóa học tại trường. Phương pháp thiết kế hướng đối tượng • Quan hệ giữa các lớp có thể là – Chứa đựng – containment: lớp này nằm trong lớp khác. VD đối tượng lốp xe nằm trong đối tượng ô tô – Kế thừa – Inheritance: lớp này có thể kế thừa dữ liệu và cách ứng xử của lớp khác. VD lớp sinh viên kế thừa từ lớp người. Phương pháp thiết kế hướng đối tượng • Quan hệ giữa các lớp có thể là – Quan hệ cộng tác – collaboration: Một lớp có thể gọi 1 lớp khác để cung cấp thông tin. VD Lớp sinh viên có thể gọi dịch vụ của lớp thư viện – library để mượn sách. Giải quyết vấn đề và thiết kế thuật toán • Biểu diễn thuật toán: – Dùng ngôn ngữ tự nhiên – Dùng giả ngôn ngữ – Dùng sơ đồ khối – Dùng ngôn ngữ lập trình • VD. Bài toán tìm giá trị lớn nhất của một dãy N số nguyên – Đầu vào: N và giá trị của N số nguyên a1, a2,, aN – Đầu ra: số nguyên lớn nhất của dãy Giải quyết vấn đề và thiết kế thuật toán 3 5 7 9 2 max 3 5 max<5 max = 3 7 9 9 8 9 9 max<7 max<9 max>2 max>8 Kết quả Giải quyết vấn đề và thiết kế thuật toán Thuật toán: Tìm giá trị lớn nhất trong dãy số nguyên • B1: Max  a1, i  2. • B2: Nếu i > N, thuật toán kết thúc và Max là giá trị lớn nhất của dãy cần tìm • B3: Nếu ai > Max, gán ai cho Max. • B4: Tăng i lên 1 đơn vị. • B5: Quay lên B2. • B6: In ra Max Giải quyết vấn đề và thiết kế thuật toán Bắt đầu Max  a1 i  2 i > N Kết thúc ai > Max Max  ai i  i + 1 S Đ Đ S Hiển thị Max Giải quyết vấn đề và thiết kế thuật toán Bắt đầu hoặc kết thúc Lệnh gán Lệnh vào, lệnh ra (read hoặc write) Kiểm tra điều kiện Luồng thực hiện Nối tiếp đoạn lệnh Một số khối trong sơ đồ khối dùng biểu diễn thuật toán