Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - GV. Nguyễn Minh Thành

Chương 1 Tổng quan về cấu trúc dữ liệu và giải thuật thuộc trong bài giảng cấu trúc dữ liệu và giải thuật trình bày về các nội dung chính: giới thiệu về cấu trúc dữ liệu, khái niệm cấu trúc dữ liệu, các kiểu cấu trúc dữ liệu cơ sở, khái niệm giải thuật, đánh giá độ phức tạp của thuật giải.
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 - GV. Nguyễn Minh ThànhChương 1 : TỔNG QUAN VỀ CTDL & GT Giảng viên : Nguyễn Minh Thành Email : thanhnm@itc.edu.vnNội DungI. Giới thiệuII. Cấu trúc dữ liệu 1. Khái niệm 2. Các cấu trúc (kiểu) dữ liệu cơ sởIII. Giải thuậtIV. Đánh giá độ phức tạp của thuật giải2 Nguyễn Minh ThànhI. Giới Thiệu Cấu trúc dữ liệu và giải thuật là hai yếu tố quan trọng nhất của một chương trình. Niklaus Wirth đã phát biểu :  Chương trình = Giải thuật + Cấu trúc dữ liệu Cấu trúc dữ liệu  Phương pháp biểu diễn và lưu trữ dữ liệu phù hợp với thao tác xử lý trong giải thuật. Giải thuật  Các bước để giải quyết một vấn đề (một bài toán) phù hợp với một cấu trúc dữ liệu cụ thể.3 Nguyễn Minh ThànhII. Cấu trúc dữ liệu Để đánh giá một cấu trúc dữ liệu, phải dựa vào các tiêu chí sau :  Phản ánh đúng thực tế  Phù hợp với thao tác  Tiết kiệm tài nguyên hệ thống4 Nguyễn Minh ThànhII.1 Khái niệm cấu trúc dữ liệu Cho  T = : kiểu (cấu trúc) dữ liệu  V = {Tập các giá trị}  O = {Tập các thao tác xử lý được phép thực hiện} Ví dụ: Kiểu dữ liệu số nguyên int trong ngôn ngữ C T = int V = {-32768, 32767} O = {+, -, *, /, %}5 Nguyễn Minh ThànhII.1 Khái niệm cấu trúc dữ liệu Các thuộc tính của một cấu trúc (kiểu) dữ liệu gồm:  Tên  Miền giá trị  Kích thước lưu trữ  Tập các thao tác tác động lên kiểu dữ liệu đó Các loại kiểu dữ liệu  Kiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bản  Kiểu dữ liệu có cấu trúc : Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, …6 Nguyễn Minh ThànhII.1 Khái niệm cấu trúc dữ liệu Với từng cấu trúc dữ liệu, ta có thể chọn 1 trong 2 cách để khởi tạo (cấp phát bộ nhớ) : Tĩnh và Động Tĩnh Động • Được định nghĩa ở thời điểm • Được gắn kết với một con trỏ biên dịch. (tại thời điểm biên dịch chưa có). • Được cấp phát ở thời điểm liên • Phát sinh lúc thực thi. kết. • Có thể có giá trị ban đầu tùy • Không xác định giá trị ban đầu. theo từng ngôn ngữ lập trình. • Được giải phóng khỏi bộ nhớ • Tồn tại đến khi kết thúc khi cần. chương trình.7 Nguyễn Minh ThànhII.2 Các kiểu dữ liệu cơ sởTên kiểu Miền giá trị Kích thước Ý nghĩachar -127  128 8 bit Số nguyên, ký tựInt -32767  32768 16 bit (hoặc 32, 64) Số nguyênfloat … 32 bit Số thực (6 thận phân)double … 64bit Số thực (10 thập phân)Các từ khoá khai báo đặc biệt• Unsigned, signed, short, long8 Nguyễn Minh ThànhIII. Giải Thuật Giải thuật hay còn gọi là thuật toán  Một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán9 Nguyễn Minh ThànhIII. Giải Thuật Các đặc trưng cơ bản của một giải thuật  Yếu tố vào – ra (input/output)  Tính dừng (Finitary)  Tính chính xác (Exactitude)  Tính hiệu quả (effectiveness)  Tính tổng quát (generalliness)10 Nguyễn Minh ThànhIV. Đánh Giá Giải Thuật Các độ đo dùng để đánh giá giải thuật  Độ dài của chương trình (số dòng lệnh)  Dễ lập trình (phát hiện lỗi, quản lý)  Bộ nhớ  Thời gian thực thi Thời gian thực thi là tiêu chuẩn quyết định  Có thể lượng giá được và dễ dàng so sánh  Thường là yếu tố “cổ chai” quan trọng11 Nguyễn Minh ThànhIV. Đánh Giá Giải Thuật Đánh giá độ phức tạp (thời gian) của giải thuật  Một giải thuật có thể thực thi khác nhau tuỳ thuộc vào:  nền tảng phần cứng (PC, Cray, Sun)  ngôn ngữ lập trình (C, Java, C++)  lập trình viên (you, me, Bill Joy)  Tuy khác nhau về chi tiết, tất cả mô hình phần cứng và chương trình đều có điểm tương tự nhau: chúng là các máy Turing.  Chỉ cần đếm các phép toán cơ bản là đủ.  Độ đo đơn giản nhưng có giá trị đối với hiệu quả của các thuật toán là một hàm của kích thước input.12 Nguyễn Minh ThànhFAQs (Hỏi - Đáp)13 Nguyễn Minh Thành ...