Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Ngô Quang Thạch

CẤU TRÚC DỮ LIỆU VÀ<br /> GIẢI THUẬT<br /> NGÔ QUANG THẠCH<br /> Email: thachnq@gmail.com<br /> ĐT: 01273984123<br /> <br /> CHƯƠNG 1: Tổng quan về CTDL và GT<br /> Khái niệm giải thuật<br /> Các kiểu dữ liệu cơ bản<br /> Các kiểu dữ liệu trừu tượng<br /> <br /> Các cấu trúc dữ liệu cơ bản<br /> <br /> Mối quan hệ giữa CTDL và giải thuật<br /> <br /> Giải bài toán bằng phần mềm<br /> <br /> 1<br /> <br /> • Xác định bài toán<br /> <br /> 2<br /> <br /> • Tìm cấu trúc dữ liệu biểu diễn bài toán<br /> <br /> 3<br /> <br /> • Tìm thuật toán<br /> <br /> 4<br /> <br /> • Lập trình<br /> <br /> 5<br /> <br /> • Kiểm thử phần mềm<br /> <br /> 6<br /> <br /> • Tối ưu chương trình<br /> <br /> Giải thuật<br /> Giải thuật hay Thuật toán dùng để chỉ phương pháp hay<br /> cách thức (method) để giải quyết vấn đề.<br /> Thuật toán là một chuỗi hữu hạn các lệnh, mỗi lệnh có<br /> một ngữ nghĩa rõ ràng và có thể được thực hiện với một<br /> lượng hữu hạn tài nguyên trong một khoảng hữu hạn<br /> thời gian.<br /> Giải thuật có thể được minh họa bằng ngôn ngữ tự<br /> nhiên (natural language), bằng sơ đồ (flow chart) hoặc<br /> bằng mã giả (pseudo code)<br /> <br /> <br /> Các tính chất của giải thuật<br /> Hữu hạn (finiteness): giải thuật phải luôn luôn kết thúc<br /> sau một số hữu hạn bước.<br /> Xác định (definiteness): mỗi bước của giải thuật phải<br /> được xác định rõ ràng và phải được thực hiện chính xác,<br /> nhất quán.<br /> Hiệu quả (effectiveness): các thao tác trong giải thuật<br /> phải được thực hiện trong một lượng thời gian hữu hạn.<br /> – Ngoài ra một giải thuật còn phải có đầu vào (input) và<br /> đầu ra (output).<br /> <br />