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

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