tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật - TS. Nguyễn Trung Hòa

Bài giảng Cấu trúc dữ liệu và giải thuật cung cấp cho người học các kiến thức về giải thuật, kiểu dữ liệu và mô hình dữ liệu, danh sách tuyến tính, giải thuật đệ quy, cây. nội dung chi tiết. | Cấu trúc dữ liệu và giải thuật Người thực hiện: GVC. TS. Nguyễn Trung Hòa Email: ntrhoa@ Điện thoại: 0904 162168 Tài liệu tham khảo Đề cương chương trình 1. Cấu trúc dữ liệu và giải thuật Đỗ Xuân Lôi, NXB ĐHQGHN,2004 2. Cẩm nang thuật toán R. Sedgewick, NXB Khoa học và Kỹ thuật,1994 1 Chương 1. Giải thuật . Khái niệm giải thuật . Thiết kế giải thuật . Phân tích và đánh giá giải thuật . Khái niệm giải thuật . Giải thuật là gì? . Cấu trúc dữ liệu . Diễn đạt giải thuật 2 . Giải thuật là gì? . Giải thuật là gì? Ví dụ mở đầu Cho một dãy các số thực a1,a2, ,an. Tìm giá trị lớn nhất m của các số đã cho và chỉ số lớn nhất i trong các số đạt giá trị m. Vì phải tìm số lớn nhất với chỉ số lớn nhất, ta sẽ xuất phát từ số cuối cùng của dãy là an và sẽ so sánh với các số trước đó, khi tìm thấy một giá trị lớn hơn thì ta ghi lại (đánh dấu) và lại tiếp tục so sánh số này với các số trước đó, công việc sẽ được thực hiện cho đến khi đã so với số đầu tiên. 3 . Giải thuật là gì? Giải thuật là: Cách làm để giải quyết bài toán Một dãy có trình tự các thao tác trên một số đối tượng nào đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả mong muốn. Vào Các bướcthực hiện Ra Một giải thuật có Đầu vào (Input): tập các đối tượng (dữ liệu) Đầu ra(Output): một tập các giá trị (thông tin) . Giải thuật là gì? Các đặc trưng của giải thuật Tính có đại lượng vào/ra Tính xác định Tính hữu hạn (tính dừng) Tính tổng quát Tính hiệu quả Một vài đặc điểm cần lưu ý Không cần biết giá trị cụ thể của kết quả sau mỗi bước, chỉ cần biết cách chuyển từ bước trước tới bước sau; Kết quả cụ thể của giải thuật có thể không phải là kết quả đúng (chính xác) mặc dầu phương pháp là đúng. 4 . Cấu trúc dữ liệu Dữ liệu có cấu trúc: Lựa chọn cấu trúc dữ liệu và giải thuật thích hợp: rất quan trọng Tập hợp dữ liệu Có mối quan hệ với nhau trong bài toán xác .