Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Cấu trúc dữ liệu và giải thuật. Những nội dung chính được trình bày trong chương 1 gồm có: Mối quan hệ giữa cấu trúc dữ liệu và giải thuật, các cách diễn đạt giải thuật, thiết kế và phân tích giải thuật, giải thuật đệ quy. Mời các bạn cùng tham khảo. | CHƯƠNG 1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật . Giải thuật thuật toán algorithms l Khái niệm Giải thuật là một hệ thống các thao tác các phép toán được thực hiện theo trình tự nhất định trên một số đối tượng dữ liệu nào đó sao cho sau một số bước hữu hạn ta có được kết quả mong muốn. l Giải thuật phản ánh các phép xử lý còn đối tượng xử lý là dữ liệu. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 . Giải thuật thuật toán algorithms l Giải thuật phải có các tính chất cơ bản sau l Tính thực hiện được l Tính kết thúc l Tính kết quả Phải cho kết quả mong muốn. l Tính hiệu quả l Tính duy nhất l Tính tổng quát Phải áp dụng cho mọi bài toán cùng loại. l Tính hình thức Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 . Cấu trúc dữ liệu l Khái niệm dữ liệu Dữ liệu là các phần tử biểu diễn các thông tin cần thiết cho bài toán. l Một bài toán có thể có các loại dữ liệu Dữ liệu vào dữ liệu trung gian dữ liệu ra. l Dữ liệu vào là dữ liệu cần đưa vào để xử lý đây chính là đầu vào của bài toán. l Dữ liệu trung gian là dữ liệu chứa các kết quả trung gian trong quá trình xử lý. l Dữ liệu ra là dữ liệu chứa kết quả mong muốn của bài toán. l Giải thuật thực hiện biến đổi từ các dữ liệu vào thành các dữ liệu ra. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 . Cấu trúc dữ liệu tiếp l Ví dụ 1 Ta xét bài toán tính học bổng cho sinh viên theo chế độ hiện hành. Các dữ liệu của bài toán bao gồm l Dữ liệu vào Họ và tên Điểm các môn Số trình các môn học. l Dữ liệu trung gian Điểm trung bình l Dữ liệu ra Học bổng Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 . Cấu trúc dữ liệu tiếp l Ví dụ 2 Xét bài toán giải phương trình bậc hai ax2 bx c 0 . Các dữ liệu của bài toán này như sau l Dữ liệu vào a b c l Dữ liệu trung gian delta l Dữ liệu ra x1 x2 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 . Cấu trúc dữ liệu
