CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 1 TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GiẢI THUẬT

Chia sẻ: Lê Ngọc Hoàng | Ngày: | Loại File: PPT | Số trang:29

Thêm vào BST

Báo xấu

77
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thông tin là gì? Là những tín hiệu, ký hiệu, hình ảnh tác động vào các giác quan đem lại sự hiểu biết cho con người Thông tin là nguồn gốc của nhận thức Dữ liệu là gì? Là những thông tin được lưu trữ trên các vật mang tin – Bộ nhớ máy tính

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 1 TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GiẢI THUẬT

TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GiẢI THUẬT CHƯƠNG 1
Thông tin và dữ liệu  Thông tin là gì? Là những tín hiệu, ký hiệu, hình ảnh tác động – vào các giác quan đem lại sự hiểu biết cho con người Thông tin là nguồn gốc của nhận thức –  Dữ liệu là gì? Là những thông tin được lưu trữ trên các vật – mang tin – Bộ nhớ máy tính
Khái niệm cấu trúc dữ liệu Dữ liệu được lưu trong bộ nhớ máy tính và được  xử lý nên nó phải có cấu trúc Dữ liệu lớn được xây dựng từ các dữ liệu  nguyên tử Cấu trúc dữ liệu là mô hình của dữ liệu được  lưu trong bộ nhớ Trong các ngôn ngữ lập trình cấu trúc dữ liệu  chính là các kiểu dữ liệu
Khái niệm giải thuật Phòng học Rời phòng học Ðến cầu thang Xuống tầng Các bước thực hiện khi hầm Ði đến quán một người muốn đi đến quán ăn tự phục vụ từ ăn tự phục vụ phòng học Cafeteria
Khái niệm giải thuật Giải thuật là dãy các bước có thứ tự chính xác để giải  quyết được một bài toán cụ thể, theo đó với mỗi bộ dữ liệu vào giải thuật cho một kết quả Ví dụ: Giải phương trình bậc 2  Bước 1: Tính delta – Bước 2 so sánh delta với 0 – >0: tính 2 nghiệm x1=.., x2=… và thông báo nghiệm   =0: tính nghiệm kép và thông báo 
Các đặc trưng của giải thuật Bộ dữ liệu vào: Các DL mà giải thuật xử lý  Bộ dữ liệu ra: Là kết quả của việc thực hiện giải thuật,  DL ra có quan hệ xác định với DL vào Tính tất định: mỗi bước của giải thuật chỉ cho một kết  quả duy nhất Tính dừng: Sau hữu hạn bước giải thuật dừng lại và cho  kết quả Tính đúng đắn: Giải thuật thực sự giải quyết được yêu  cầu của bài toán Tính phổ dụng: Giải thuật giải quyết được một lớp bài  toán
Mối quan hệ giữa CTDL và GT Cấu trúc dữ liệu và giải thuật là hai phần của  một bài toán Giải thuật là mã lệnh xử lý dữ liệu có cấu trúc  định sẵn trong bộ nhớ và tạo ra dữ liệu mới Giải thuật qui định cấu trúc dữ liệu và ngược lại  Cấu trúc dữ liệu + Giải thuật = Chương trình
Mối quan hệ giữa CTDL và GT dụ: Bài toán tìm max của 4 số nguyên  Ví Cách 1: Cách 2: Dữ liệu được lưu trữ bởi 4 biến Dữ liệu được lưu trữ bởi mảng độc lập: a, b, c, d. A[4] có 4 phần tử Khi đó giải thuật như sau: Khi đó giải thuật như sau: max = a; max = A[0]; if (max
Ngôn ngữ diễn đạt giải thuật Ngôn ngữ tự nhiên  Lược đồ khối  Ngôn ngữ lập trình  Là các phương tiện để ghi lại các thiết kế cấu trúc dữ liệu và giải thuật Thường sử dụng nhất là ngôn ngữ lập trình
Đánh giá giải thuật giá về bộ nhớ để lưu trữ bộ dữ liệu  Đánh mà giải thuật sẽ xử lý giá về giải thuật  Đánh Tính khả thi của giải thuật – Thời gian mà giải thuật thực hiện xử lý dữ – liệu
Đánh giá bộ nhớ Có 2 quan niệm:  Quan niệm 1: Tổng dung lượng nhớ để lưu trữ tất cả – các dữ liệu mà giải thuật xử lý (tính bằng đơn vị nhớ - bit, byte, KB…) Quan niệm 2: Tổng số chỗ nhớ để lưu tất cả các dữ – liệu Tổng số chỗ nhớ gồm DL vào, DL ra, và các  biến phụ
Đánh giá thời gian thực hiện GT 2 quan niệm  Có Quan niệm 1: Là tổng thời gian mà giải thuật – thực hiện xử lý dữ liệu (tính bằng đơn vị thời gian) Quan niệm 2: Là tổng số phép toán cơ bản – mà giải thuật phải thực hiện để xử lý dữ liệu (các phép toán cơ bản: cộng, trừ, nhân, chia, gán, các phép toán logic…)
Các tiêu chuẩn đánh giá CTDL Phản ánh đúng thực tế: đây là tiêu chuẩn quan trọng nhất, quyết định tính đúng  đắn của toàn bộ bài toán. Cần xem xét kỹ l ưỡng cũng nh ư d ự trù các tr ạng thái biến đổi của dữ liệu trong chu trình sống để có thể lựa chọn cấu trúc d ữ liệu l ưu trữ thể hiện chính xác đối tượng thực tế. Phù hợp với các giải thuật xử lý trên đó: Tiêu chuẩn này giúp tăng hiệu quả khi  giải quyết bài toán, việc phát triển các giải thu ật đ ơn gi ản, t ự nhiên h ơn và chương trình đạt hiệu quả cao hơn về tốc độ xử lý. Tiết kiệm tài nguyên hệ thống: CTDL chỉ nên sử dụng tài nguyên vừa đủ đ ể đảm  nhiệm được chức năng của nó. Thông thường có hai lo ại tài nguyên c ần l ưu ý nhất là bộ vi xử lý (CPU) và bộ nhớ. Tiêu chuẩn này nên cân nh ắc tùy vào tình huống cụ thể khi thực hiện bài toán. Nếu tỏ chức s ử dụng bài toán c ần có nh ững xử lý nhanh thì khi chọn CTDL yếu tố tiết kiệm thời gian x ử lý ph ải đ ược ưu tiên hơn tiêu chuẩn sử dụng tối đa bộ nhớ và ngược lại.
Độ phức tạp giải thuật Có 3 kiểu đánh giá  Độ phức tạp trong trường hợp tốt nhất: Số phép toán – ít nhất mà giải thuật phải thực hiện để xử lý mọi bộ dữ liệu vào Độ phức tạp trung bình: Số phép toán trung bình mà – giải thuật phải thực hiện để xử lý mọi bộ dữ liệu vào Độ phức tạp trong trường hợp xấu nhất: Số phép toán – nhiều nhất mà giải thuật phải thực hiện để xử lý mọi bộ dữ liệu vào
Một số ví dụ  Bài toán max Vào: Dãy X có n số: X1, X2, …, Xn – Ra: Max – Giải thuật – Max = X[1]; for (i=2; i
Một số ví dụ  Bài toán Max Xét dãy X={34 32 45 65 23 54}, n=6 Độ phức tạp bộ nhớ: 9 chỗ nhớ vào: 7 chỗ nhớ (X1, …, X6, n) phụ: 1 (i) ra: 1 (Max) Độ phức tạp thời gian: 8 phép toán
Max = X[1]; for (i=2; i Max Max=45 2 phép toán i=4 -> Max Max=65 2 phép toán i=5 -> Max không gán 1 phép toán i=6 -> Max không gán 1 phép toán
Một số ví dụ  Bài toán Max Xét dãy X={65 32 45 34 23 54}, n=6 Độ phức tạp bộ nhớ: 9 vào: 7 phụ: 1 ra: 1 Độ phức tạp thời gian: 6 phép toán
Một số ví dụ  Bài toán Max Xét dãy X={23 32 34 45 54 65}, n=6 Độ phức tạp bộ nhớ: 9 vào: 7 phụ: 1 ra: 1 Độ phức tạp thời gian: 11 phép toán
Một số ví dụ toán max – Đánh giá tổng quát  Bài Vào: Dãy X có n số: X1, X2, …, Xn – Ra: Max – Max = X[1]; Giải thuật – for (i=2; i