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

Sau khi học xong chương 1 "Tổng quan về Cấu trúc dữ liệu và giải thuật" này người học có thể hiểu về: Khái niệm giải thuật, các kiểu dữ liệu cơ bản, các kiểu dữ liệu trừu tượng, các cấu trúc dữ liệu cơ bản, mối quan hệ giữa CTDL và giải thuậ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: Chương 1 - Ngô Quang ThạchCẤU TRÚC DỮ LIỆU VÀGIẢI THUẬTNGÔ QUANG THẠCHEmail: thachnq@gmail.comĐT: 01273984123CHƯƠNG 1: Tổng quan về CTDL và GTKhái niệm giải thuậtCác kiểu dữ liệu cơ bảnCác kiểu dữ liệu trừu tượngCác cấu trúc dữ liệu cơ bảnMối quan hệ giữa CTDL và giải thuậtGiải bài toán bằng phần mềm1• Xác định bài toán2• Tìm cấu trúc dữ liệu biểu diễn bài toán3• Tìm thuật toán4• Lập trình5• Kiểm thử phần mềm6• Tối ưu chương trìnhGiải thuậtGiải thuật hay Thuật toán dùng để chỉ phương pháp haycách thức (method) để giải quyết vấn đề.Thuật toán là một chuỗi hữu hạn các lệnh, mỗi lệnh cómột ngữ nghĩa rõ ràng và có thể được thực hiện với mộtlượng hữu hạn tài nguyên trong một khoảng hữu hạnthời gian.Giải thuật có thể được minh họa bằng ngôn ngữ tựnhiên (natural language), bằng sơ đồ (flow chart) hoặcbằng mã giả (pseudo code)Các tính chất của giải thuậtHữu hạn (finiteness): giải thuật phải luôn luôn kết thúcsau một số hữu hạn bước.Xác định (definiteness): mỗi bước của giải thuật phảiđược xác định rõ ràng và phải được thực hiện chính xác,nhất quán.Hiệu quả (effectiveness): các thao tác trong giải thuậtphải được thực hiện trong một lượng thời gian hữu hạn.– Ngoài ra một giải thuật còn phải có đầu vào (input) vàđầu ra (output).