Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Cấu trúc dữ liệu và Giải thuậtCấu trúc dữ liệu và Giải thuậtChương I: Các kiến thức cơ bảnCác kiến thức cơ bản.Nội dung. Cáckhái niệm Giảithuật. Cấu trúc dữ liệu. Phântích giải thuật Giảngôn ngữ. Thời gian thực hiện giải thuật. Đánh giá độ phức tạp sử dụng tiệm cậnĐỗ Bích Diệp - Khoa CNTT- ĐHBKHN1.Cấu trúc dữ liệu và Giải thuậtGiải thuật.–Một thủ tục bao gồm một dãy hữu hạn các bước.cần thực hiện để thu được đầu ra cho đầu vào.cho trước của một bài toánGiải thuật.zĐặc trưng của giải thuật.–.–.–.–.–Đầu vào.Đầu ra.Tính hữu hạn.Tính hiệu quả.Tính xác địnhĐỗ Bích Diệp - Khoa CNTT- ĐHBKHN2.Cấu trúc dữ liệu và Giải thuậtGiải thuật và Chương trìnhChương trình là một thể hiện của Giải thuật trong một.ngôn ngữ lập trình nào đóCấu trúc dữ liệu.zKiểu dữ liệu trừu tượng (Abstract Data Type).–Là mô hình toán học và những phép toán thực.hiện trên mô hình toán học này–Ví dụ: ADT List.z.zDữ liệu: Các nút.Các phép toán:.–.–.–.–Bổ sung một nút mới.Loại bỏ một nút.Tìm kiếm một nút có giá trị cho trước. Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN3.Cấu trúc dữ liệu và Giải thuậtCấu trúc dữ liệu.zCấu trúc dữ liệu.–.–.–.–Sử dụng để biểu diễn mô hình toán học trong.ADT.Việc cài đặt các kiểu dữ liệu trừu tượng đòi hỏi.phải chọn các cấu trúc dữ liệu để biểu diễn.Liên quan đến cách thức tổ chức và truy nhập.các phần tử dữ liệu.Ví dụ: ADT List.z.zCài đặt sử dụng cấu trúc mảng đơn giản.Cài đặt sử dụng cấu trúc con trỏXây dựng chương trình giải bài toán.–Lời giải một bài toán bao gồm.z.z–Cấu trúc dữ liệu.Thuật toánXây dựng chương trình giải bài toán.z.zTương tự như vòng đời của phần mềm.Gồm các bước.Thu thập yêu cầu: Hiểu rõ đầu vào và kết quả đầu ra.Thiết kế : Xây dựng giải thuật, bỏ qua các chi tiết về cách thức.cài đặt dữ liệu hay các phương thức, tập trung vào các bước xử.lý.– Phân tích : Tìm, so sánh với giải thuật khác.– Cài đặt: Xây dựng chương trình, quan tâm đến cách thức tổ.chức, biểu diễn và cài đặt các phương thức.– Kiểm thử : Bao gồm chứng minh tính đúng đắn của chương.trình, kiểm thử các trường hợp , tìm, sửa lỗi.–.–Đỗ Bích Diệp - Khoa CNTT- ĐHBKHN4.Cấu trúc dữ liệu và Giải thuậtThuật toán và độ phức tạp.–Đánh giá lượng tài nguyên các loại mà một giải.thuật đã sử dụngzzGiải thuật này thực hiện trong thời gian thế nào Æ.Phân tích về thời gian thực hiện giải thuật.Giải thuật này sử dụng bao nhiêu bộ nhớ Æ Phân tích.độ không gian nhớ mà giải thuật (chương trình) cần có.Phân tích thời gian thực hiện giải thuật.–Mục tiêu của việc xác định thời gian thực hiện.một giải thuật:.z.z.z.zĐể ước lượng một chương trình sẽ thực hiện trong bao.lâu.Để ước lượng kích thước dữ liệu đầu vào lớn nhất có.thể cho một giải thuật.Để so sánh hiệu quả của các giải thuật khác nhau, từ đó.lựa chọn ra một giải thuật thích hợp cho một bài toán.Để giúp tập trung vào đoạn giải thuật được thực hiện.với thời gian lớn nhấtĐỗ Bích Diệp - Khoa CNTT- ĐHBKHN5.
