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. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật - TS. Nguyễn Trung HòaCấu trúc dữ liệuvà giải thuậtNgười thực hiện: GVC. TS. Nguyễn Trung HòaEmail: ntrhoa@yahoo.comĐiện thoại: 0904 162168Tài liệu tham khảoĐề cương chương trình1. Cấu trúc dữ liệu và giải thuậtĐỗ Xuân Lôi, NXB ĐHQGHN,20042. Cẩm nang thuật toánR. Sedgewick, NXB Khoa học và Kỹthuật,19941Chương 1. Giải thuật1.1. Khái niệm giải thuật1.2. Thiết kế giải thuật1.3. Phân tích và đánh giá giải thuật1.1. Khái niệm giải thuật1.1.1. Giải thuật là gì?1.1.2. Cấu trúc dữ liệu1.1.3. Diễn đạt giải thuật21.1.1. Giải thuật là gì?1.1.1. 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 itrong 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ẽ sosá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 sosá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.31.1.1. Giải thuật là gì?„Giải thuật là:‰‰Cách làm để giải quyết bài toánMột dãy có trình tự các thao tác trên một số đốitượng nào đó sao cho sau một số hữu hạn bướcthực hiện ta đạt được kết quả mong muốn.Vào‰Các bướcthực hiệnRaMộ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)1.1.1. 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/raTính xác địnhTính hữu hạn (tính dừng)Tính tổng quátTí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.41.1.2. 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ấtquan trọng‰‰„Tập hợp dữ liệuCó mối quan hệ với nhau trong bài toán xác địnhVídụ: viết chương trình tìm kiếm số điện thoại theo tên đơnvịGiải thuật + Dữliệu = Chương trìnhBiểu diễn cấu trúc dữ liệu trong bộ nhớ:‰Lưu trữ trong„‰Thông qua các biếnLưu trữ ngoài„Tệp (định kiểu và không định kiểu)1.1.3. Diễn đạt giải thuật„Ngôn ngữ tự nhiên‰Ngôn ngữ liệt kê các bước5