Bài giảng Tổng quan về cấu trúc dữ liệu và giải thuật

Bài 1: Tổng quan về cấu trúc dữ liệu và giải thuật Nội dung Giới thiệu vai trò của việc tổ chức dữ liệu đối với bài toán tin học Mối quan hệ giữa giải thuật và cấu trúc dữ liệu Các yêu cầu tổ chức dữ liệu Khái niệm kiểu dữ liệu_cấu trúc dữ liệu Thuật toán 1.Vai trò của cấu trúc dữ liệu Tổ chức biểu diễn các đối tượng thực tế phải tổ chức, xây dựng các cấu trúc dữ liệu thích hợp nhất phản ánh chính xác các dữ liệu thực tế và dễ dàng dùng máy tính để xử lý Xây dựng các thao tác xử lý dữ liệu Cấu trúc dữ liệu + Giải thuật = Chương trình 1.Vai trò… Ví dụ 1: Một chương trình quản lý điểm thi của sinh viên cần lưu các điểm số của 3 sinh viên. Do mỗi sinh viên có 4 điểm số tương ứng với 4 môn học khác nhau nên dữ liệu có dạng như sau: In điểm số các môn của từng sinhviên 1.Vai trò… Phương án 1: Sử dụng mảng một chiều Phương án 2: sử dụng mảng hai chiều 2.Các tiêu chuẩn đánh giá cấu trúc dữ liệu Phản ánh đúng thực tế: 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 Phù hợp với các thao tác trên đó: Tiêu chuẩn này giúp tăng hiệu quả của giải bài toán 3.Kiểu dữ liệu và cấu trúc dữ liệu 3.1.Định nghĩa kiểu dữ liệu Kiểu dữ liệu T được xác định bởi bộ , với : V: tập các giá trị hợp lệ mà đối tượng kiểu T có thể lưu trữ O : tập các thao tác xử lý có thể thi hành trên đối tượng kiểu T. Ví dụ : Kiểu dữ liệu ký tự = với Vc = {a - z, A - Z} Oc = {lấy mã ASCII của ký tự, biến đổi ký tự thường thành ký tự hoa,...} Kiểu dữ liệu số nguyên = Vc = {-32768 32767} Oc = {+, -, *, /, %, các phép so sánh} 3.2.Các thuộc tính của một kiểu dữ liệu Một kiểu dữ liệu bao gồm các thuộc tính sau : Tên kiểu dữ liệu Miền giá trị Kích thước lưu trữ Tập các toán tử tác động lên kiểu dữ liệu 3.3.Các kiểu dữ liệu cơ bản thường trong một hệ kiểu của ngôn ngữ lập trình sẽ có một số kiểu dữ liệu được gọi là kiểu dữ liệu đơn hay kiểu dữ liệu phân tử (atomic). các kiểu dữ liệu cơ bản thường bao gồm : Kiểu có thứ tự rời rạc : số nguyên, ký tự, logic, liệt kê, miền con Kiểu không rời rạc : số thực 3.4. Các kiểu dữ liệu có cấu trúc cấu trúc dữ liệu bao gồm một tập hợp nào đó các dữ liệu phân tử, các thành phần này liên kết với nhau bởi một phương pháp nào đó Kiểu array (mảng) sắp xếp các thành phần có cùng một kiểu thành một dãy Kiểu record (bản ghi) là kết hợp các thành phần dữ liệu (các thành phần có thể có kiểu khác nhau) thành bản ghi (record). 3.4. Các kiểu dữ liệu có cấu trúc Kiểu con trỏ mỗi thành phần là một bản ghi gồm hai trường INFOR và LINK, trường INFOR có thể có một hay nhiều trường dữ liệu, còn trường LINK có thể chứa một hay nhiều con trỏ trỏ đến các thành phần khác có quan hệ với thành phần đó Kiểu set (tập hợp) Mỗi đối tượng của kiểu tập hợp sẽ là một tập con của một tập đủ nhỏ. Kiểu file (tệp) kiểu flie với các phần tử là các đối tượng thuộc kiểu nào đó ngoại trừ kiểu file 4. Thuật toán và phân tích thuật toán 4.1.Khái niệm thuật toán Thuật toán (algorithm) là một trong những khái niệm quan trọng nhất trong tin học. Thuật ngữ xuất phát từ nhà toán học Arập Abu Ja'far Mohammed ibn Musa al Khowarizmi (khoảng năm 825). Tuy nhiên nó không mang nội dung như ngày nay chúng ta quan niệm. nổi tiếng nhất, có từ thời cổ Hy lạp là thuật toán Euclid, thuật toán tìm ước chung lớn nhất của hai số nguyên 4.1.Khái niệm .. Định nghĩa: Thuật toán là một số hữu hạn các bước thực hiện tính toán theo một trình tự xác định để biến đổi các giá trị đầu vào (Input) thành các giá trị đầu ra mong muốn (Output). 4.1.Khái niệm .. Ví dụ: bài toán sắp xếp Input: một dãy n số (a1, a2, . . . , an) Output: dãy được sắp xếp theo thứ tự tăng dần a’1≤ a’2≤, . . ≤ a’n Giả sử chúng ta có bộ số liệu sau Input: A = 5, 2, 4, 6, 1, 3 Output: A’ = 1,2, 3, 4, 5, 6 4.2 Các đặc trưng của thuật toán Đầu vào (Input) ra (Output) : mỗi thuật toán cần phải có bộ dữ liệu đầu vào và dữ liệu đầu ra (kết quả tính toán). Tính xác định: mỗi bước của thuật toán cần phải mô tả chính xác, rõ ràng. Tính khả thi: tất cả các phép toán trong thuật toán phải đủ đơn giản để thực thi được. Tính dừng: với mỗi bộ số liệu đầu vào thỏa mãn điều kiện ban đầu thì thuật toán phải dừng sau hữu hạn bước. Tính phổ dụng: Thuật toán có thể áp dụng đối với các dữ liệu đầu vào khác nhau trong một miền xác định. 4.3 Biểu diễn thuật toán a) Biểu diễn bằng cách liệt kê các bước Liệt kê ra các bước cần phải thực hiện bằng ngôn ngữ tự nhiên. VD 1: Thuật toán tìm số lớn nhất trong 3 số a,b,c Giả thiết số lớn nhất là a: Max=a Nếu Maxk; 4.4 Độ phức tạp… VD1: f(x)=anxn+an-1xn-1+…+a1x+a0, với ai là các số thực (i=0..n). Khi đó f(x)=O(xn) CM: |f(x)| = | anxn+an-1xn-1+…+a1x+a0| 1, ta có: k => f(x) là O(xn) 4.4 Độ phức tạp… VD2:f(n)=1+2+3+…+n. Chỉ ra rằng f(n) là O(n2) Chỉ ra hàm n! là O(nn) và log(n!) là O(nlogn) 4.4 Độ phức tạp… Độ tăng của tổ hợp các hàm: Xét f1(x) là O(g1(x) và f2(x) là O(g2(x)), CMR: (f1(x)+f2(x)) là O(max{g1(x),g2(x)}) CM: theo giả thiết ta có |fi(x)|k Với k=max{k1,k2} và C=C1+C2 g(x)=max{ |g1(x)|,|g2(x)|} 4.4 Độ phức tạp… Độ phức tạp của thuật toán các thuật ngữ O(1)-độ phức tạp hằng số; O(n) độ phức tạp tuyến tính; O(nb) – độ phức tạp hàm mũ. độ phức tạp tính toán sẽ được tính theo số lần thực hiện các phép toán sơ cấp:cộng, trừ, nhân, chia, phép gán,.. 4.4 Độ phức tạp… VD: Xét đoạn chương trình sau: For (i=1; i<=n; i++) { …{có phép tính sơ cấp; ko có vòng lặp ở đây nữa} } 4.4 Độ phức tạp… VD2: For (i=1; i<=n; i++) For (j=1; j<=m; j++) { {có phép tính sơ cấp; ko có vòng lặp ở đây nữa} }