TimTaiLieu.vn - Tài liệu, ebook, giáo trình, đồ án, luận văn

Giới thiệu  Đối sánh chuỗi  Từ khóa: String matching, String searching, Pattern searching, Text Searching  Một trong những thuật toán quan trọng và có ứng dụng rộng rãi.  Ứng dụng của đối sánh chuỗi:  Máy tìm kiếm  Trình soạn thảo văn bản  Trình duyệt web  Sinh học phân tử (Tìm mẫu trong dãy DNA).  Mục tiêu:  Kiểm tra sự tồn t...

26 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 596 | Lượt tải: 1

Khái niệm  Nén dữ liệu không mất mát (Lossless data compression)  Ví dụ:  Run-length encoding  LZW  Ứng dụng:  Ảnh PCX, GIF, PNG,.  Tập tin *. ZIP  Ứng dụng gzip (Unix)  Nén dữ liệu không mất mát (Lossless data compression)  Cho phép dữ liệu nén được phục hồi nguyên vẹn như dữ liệu nguyên thủy (lúc chưa được nén).

43 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 532 | Lượt tải: 1

 Cây tìm kiếm m-nhánh là cây có tính chất:  Có tối đa m-1 khóa trong mỗi node (v1, v2,., vk) (k  m-1).  Các giá trị khóa trong node được tổ chức có thứ tự (v1 < v2 < . < vk).  Một node có k khóa thì sẽ có k + 1 cây con (các cây con có thể rỗng).  Các cây con đặt giữa hai giá trị khóa.  Hai cây con nằm ở hai đầu của dãy khóa  Mỗi khó...

24 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 476 | Lượt tải: 1

 Placing data items in nodes of a 2-3 tree  A 2-node (has two children) must contain single data item greater than left child’s item(s) and less than right child’s item(s)  A 3-node (has three children) must contain two data items, S and L , such that  S is greater than left child’s item(s) and less than middle child’s item(s);  L is g...

28 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 459 | Lượt tải: 1

Định nghĩa Cây (cây có gốc) được xác định đệ quy như sau: 1. Tập hợp gồm 1 đỉnh là một cây. Cây này có gốc là đỉnh duy nhất của nó. 2. Gọi T1, T2, Tk (k ≥ 1) là các cây không cắt nhau có gốc tương ứng r1, r2, rk. Giả sử r là một đỉnh mới không thuộc các cây Ti. Khi đó, tập hợp T gồm đỉnh r và các cây Ti tạo thành một cây mới với gốc r. Các...

40 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 536 | Lượt tải: 1

Giới thiệu Mảng: cấu trúc dữ liệu quen thuộc  Tập có thứ tự  Số lượng phần tử cố định (tĩnh)  Cấp phát vùng nhớ liên tục  Truy xuất phần tử thông qua chỉ số Đánh giá thao tác trên mảng:  Truy xuất phần tử?  Cập nhật?  Chèn phần tử?  Xoá phần tử?  Thực tế:  Không xác định được chính xác số lượng phần tử  Danh sách bệnh nhân...

39 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 505 | Lượt tải: 1

Để giải quyết nhu cầu tự động hóa, nhu cầu căn bản của Khoa học Máy tính, các nhà khoa học máy tính phải tạo ra sự trừu tượng hóa về những bài toán trong thế giới thực,  để người sử dụng máy tính có thể hiểu được  và có thể biểu diễn và xử lý được bên trong máy tính.  Ví dụ:  Mô hình hóa việc biểu diễn cầu thủ bóng đá  Mô hình hóa mạch...

14 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 588 | Lượt tải: 1

Giới thiệu Bài toán sắp xếp: Sắp xếp là quá trình xử lý một danh sách các phần tử để đặt chúng theo một thứ tự thỏa yêu cầu cho trước  Ví dụ: danh sách trước khi sắp xếp: {1, 25, 6, 5, 2, 37, 40} Danh sách sau khi sắp xếp: {1, 2, 5, 6, 25, 37, 40}  Thông thường, sắp xếp giúp cho việc tìm kiếm được nhanh hơn.  Các phương pháp sắp xếp th...

25 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 560 | Lượt tải: 1

Thuật toán: LinearExhaustive • Bước 1. Khởi tạo biến chỉ số: i = 0 • Bước 2. Kiểm tra xem có thực hiện hết mảng hay chưa: So sánh i và n • Nếu chưa hết mảng (i < n), sang bước 3. • Nếu đã hết mảng (i >= n), thông báo không tìm thấy giá trị x cần tìm. • Bước 3. So sánh giá trị a[i] với giá trị x cần tìm • Nếu a[i] bằng x: Kết thúc chương trì...

27 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 546 | Lượt tải: 1

Độ phức tạp cố định của thuật toán Vì phép sơ cấp sử dụng trong thuật toán là phép so sánh, nên phép so sánh được dùng làm thước đo độ phức tạp.  Tại mỗi số hạng, ta thực hiện 2 phép so sánh, 1 phép xem đã hết dãy hay chưa và 1 phép so với cực đại tạm thời.  Vì hai phép so sánh được dùng từ số hạng thứ 2 đến n, và thêm 1 phép so sánh nữa ...

17 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 596 | Lượt tải: 1