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 />