Bài giảng Thuật toán ứng dụng: Tư duy thuật toán và cấu trúc dữ liệu, kỹ năng lập trình

Bài giảng "Thuật toán ứng dụng: Tư duy thuật toán và cấu trúc dữ liệu, kỹ năng lập trình" trình bày các nội dung chính sau đây: Giới thiệu chung; Các kỹ năng cơ bản cần rèn luyện; Dạng bài toán Ad Hoc. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Thuật toán ứng dụng: Tư duy thuật toán và cấu trúc dữ liệu, kỹ năng lập trìnhTHUẬT TOÁN ỨNG DỤNG Tư Duy Thuật Toán Và CTDL + Kỹ Năng Lập Trình1 Giới thiệu chung2 Các kỹ năng cơ bản cần rèn luyện3 Dạng bài toán Ad Hoc 3 / 441 Giới thiệu chung Mô hình tổng quát Mục tiêu Phương pháp tiếp cận Tài liệu tham khảo Các chủ đề Mẫu đề bài Bài toán ví dụ – ALICEADD Hệ thống chấm điểm Các phản hồi2 Các kỹ năng cơ bản cần rèn luyện3 Dạng bài toán Ad Hoc 4 / 44Mô hình Bài tập lập trình Thuật toán ứng dụngYếu tố chính : giải bài toán đúng nhanh nhất có thể! 5 / 44Mục tiêu Đề bài yêu cầu lập trình giải quyết một bài toán có nội dung ứng dụng thực tế, các vấn đề bao gồm: mô hình hoá bài toán, tìm lời giải hiệu quả sử dụng các thuật toán và cấu trúc dữ liệu, chuyển lời giải thành chương trình và chạy thử nghiệm, làm càng nhanh càng tốt dưới áp lực thời gian và độ chính xác, và phải làm đúng: chương trình không sinh lỗi, kết quả đúng trong thời gian và bộ nhớ hạn chế. Mục tiêu của khoá học này là thực hành giải quyết những vấn đề trên. 6 / 44Phương pháp tiếp cận Học những dạng bài phổ biến khác nhau Chỉ ra những ứng dụng của các thuật toán và cấu trúc dữ liệu bạn biết từ khóa học cơ bản về các thuật toán khóa học cơ bản về cấu trúc dữ liệu Học các dạng thuật toán và cấu trúc dữ liệu phổ biến khác Học một số lý thuyết toán/tin học hay dùng Thực hành giải bài toán Thực hành lập trình Thực hành nữa .. và thực hành mãi 7 / 44Tài liệu tham khảo Competitive Programming. Steven Halim http://libgen.io/ads. php?md5=f6f195012783a8b3c8bb7628882a51b7 Slides bài giảng Phân tích và thiết kế thuật toán. Nguyễn Đức Nghĩa Algorithm design. Jon Kleinberg and Éva Tardos. Introduction to Algorithms. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Bài giảng Chuyên đề Lê Minh Hoàng Competitive Programming Course at Reykjavík University 8 / 44Các chủ đề dự kiến Thứ tự Chủ đề Buổi 1 Giới thiệu Buổi 2 Cấu trúc dữ liệu và thư viện Buổi 3 Thực hành Buổi 4 Kỹ thuật đệ qui và nhánh cận Buổi 5 Chia để trị Buổi 6 Qui hoạch động Buổi 7 Thực hành Buổi 8 Qui hoạch động Kiểm tra giữa kỳ Buổi 9 Đồ thị Buổi 10 Thực hành Buổi 11 Đồ thị Buổi 12 Xử lý xâu và thực hành Buổi 13 Thuật toán tham lam Buổi 14 Thực hành Buổi 15 Lớp bài toán NP-đầy đủ 9 / 44Mẫu đề bài Mẫu chuẩn bài toán trong hầu hết các kỳ thi bao gồm: Mô tả bài toán Mô tả định dạng dữ liệu vào Mô tả định dạng kết quả ra Ví dụ Dữ liệu vào/Kết quả ra Giới hạn thời gian theo giây Giới hạn bộ nhớ theo bytes/megabytes Giới hạn kích thước các tham số đầu vào Yêu cầu viết chương trình giải bài toán đúng càng nhiều bộ dữ liệu càng tốt Mặc định là dữ liệu vào đúng, không cần kiểm tra tính đúng đắn Chương trình không được chạy quá giới hạn thời gian và giới hạn bộ nhớ 10 / 44Bài toán ví dụ – ALICEADDMô tả bài toánAlice có a cái kẹo, Bob cho Alice thêm b cái kẹo. Hỏi Alice có tất cả baonhiêu cái kẹo?Mô tả dữ liệu vào Dòng đầu chứa một số nguyên không âm T là số bộ dữ liệu (T ≤ 10). Mỗi dòng trong số T dòng tiếp theo chứa hai số nguyên không âm a và b cách nhau bởi dấu cách (a, b ≤ 1018 ).Mô tả kết quả raGồm T dòng là kết quả cho T bộ dữ liệu theo thứ tự đầu vào. 11 / 44Bài toán ví dụ – ALICEADD Ví dụ dữ liệu vào Dữ liệu kết quả ra 2 8 3 5 5 4 1 12 / 44Lời giải ví dụ 1 # include < iostream > 2 using namespace std ; 3 int main () { 4 int T ; 5 cin >> T ; 6 for ( int i = 0; i < T ; i ++) { 7 int a , b ; 8 cin >> a >> b ; 9 cout Lời giải ví dụ 1 # include < iostream > 2 using namespace std ; ...