Đề tài tiểu luận CNXHCNXHKH-HK1 2021-2022 PDF

Preview

Summary

Download Đề tài tiểu luận CNXHCNXHKH-HK1 2021-2022 PDF

Description

Câu 5: Trình bày một vài ví dụ cho thấy lợi ích khi khi xử lý dữ liệu đã được sắp xếp. Ví dụ 1: Cho danh sách sinh viên của 1 lớp gồm có MSSV, Họ và tên sv, Ngày sinh. Lúc dữ liệu chưa được sắp xếp thì các thứ tự MSSV, thông tin sinh viên sắp xếp rất loạn, sau khi được sắp xếp thì tìm kiếm thông tin dễ hơn. Tìm theo thứ tự MSSV hoặc chữ cái đầu của tên sinh viên. Ví dụ 2: Cho bảng điểm thi của sinh viên 1 lớp. Khi chưa được sắp xếp thì các con điểm thấp, cao nằm xen kẽ với nhau. Nên khi chúng ta muốn tìm sinh viên nào có điểm cao nhất, thấp nhất thì rất mất thời gian và bị rối. Khi được sắp xếp rồi thì chúng ta sẽ dễ dàng tìm được sinh vên có điểm cao nhất, thấp nhất và có thể sắp xếp theo thứ tự điểm từ cao xuống thấp. Câu 6: Sắp xếp trong là gì? sắp xếp ngoài là gì? những giải thuật sắp xếp nào (đã học) phù hợp với sắp xếp ngoài? Trả lời: Sắp xếp trong là dữ liệu phải được sắp xếp sẽ luôn ở trong bộ nhớ chính, ngụ ý truy cập nhanh hơn. Việc sắp xếp hoàn chỉnh sẽ xảy ra trong bộ nhớ chính. Sắp xếp ngoài là dữ liệu sẽ nằm trên đĩa cứng, đĩa mềm, bên ngoài bộ nhớ chính. Đó có thể là do dữ liệu rất lớn và không thể lưu trữ trong bộ nhớ chính. Những giải thuật sắp xếp phù hợp với sắp xếp ngoài là: MergeSort, Sắp xếp theo cơ số (RadixSort). Câu 7: Tìm kiếm nhị phân và tìm kiếm tuần tự khác nhau như thế nào? Trong điều kiện nào mới có thể sử dụng tìm kiếm nhị phân? Trả lời:

Tìm kiếm tuần tự: Trong kỹ thuật này, một danh sách có thứ tự hoặc không có thứ tự sẽ được tìm kiếm từng cái một trong một trình tự từ đầu cho đến khi phần tử mong muốn được tìm thấy. Nếu phần tử mong muốn được tìm thấy trong danh sách thì việc tìm kiếm sẽ thành công nếu không thì không thành công. Tìm kiếm nhị phân: Thuật toán tìm kiếm nhị phân chỉ có thể được sử dụng với danh sách phần tử đã được sắp xếp. Quá trình tìm kiếm này bắt đầu so sánh phần tử tìm kiếm với phần tử ở giữa trong danh sách. Nếu cả hai đều phù hợp, thì kết quả là "phần tử được tìm thấy". Sự khác biệt: chính là ở độ phức tạp. Tìm kiếm nhị phân có độ phức tạp về thời gian chạy tốt hơn nhiều so với tìm kiếm tuần tự. Về cơ bản, tìm kiếm nhị phân nhanh hơn nhiều so với tìm kiếm tuần tự cho một lượng lớn dữ liệu. Độ phức tạp: Tìm kiếm nhị phân O (log N), Tìm kiếm tuần tự O (N). Trong điều kiện dữ liệu, danh sách phải được sắp xếp từ trước thì mới sử dụng được tìm kiếm nhị phân. Câu 8: Mục đích việc tạo Index cho table trong các ứng dụng cơ sở dữ liệu. Trả lời: Index là một đối tượng lược đồ có chứa mục nhập cho mỗi giá trị xuất hiện trong (các) cột được lập chỉ mục của table hoặc cụm và cung cấp quyền truy cập trực tiếp, nhanh chóng vào các hàng. Các Index cho phép ứng dụng cơ sở dữ liệu tìm kiếm dữ liệu nhanh chóng; mà không cần đọc toàn bộ table. Index được sử dụng để tăng tốc độ tìm kiếm, truy vấn. Câu 9: Cho mảng a gồm các phần tử sau: 7,5,9,4,3,10,2. Trình bày thứ tự các bước thực hiện khi chạy các giải thuật sắp xếp sau: a) Inter Change Sort Cho mảng A gồm các phần tử được sắp xếp ngẫu nhiên như sau: 7, 5, 9, 4, 3, 10, 2.

Bước 1: i = 1; Bước 2: j = i + 1;

// tìm các phần tử a[j] < a[i], j > i

Bước 3: Trong khi j ≤ n thực hiện Nếu a[j] < a[i]: a[i] ↔ a[j]; j = j + 1; Bước 4: i = i + 1 Nếu i < n: Lặp lại bước 2. Ngược lại: Dừng. Mảng a[ ] = {7, 5, 9, 4, 3, 10, 2.} So sánh: i = 0 {7,5,9,4,3,10,2} => {5,7,9,4,3,10,2}, vì 7 > 5 nên đổi chỗ 7;5 {5,7,9,4,3,10,2} => {5,7,9,4,3,10,2}, vì 5 < 9 nên không đổi chỗ {5,7,9,4,3,10,2} => {4,7,9,5,3,10,2}, vì 5 > 4 nên đổi chỗ 5;4 {4,7,9,5,3,10,2} => {3,7,9,5,4,10,2}, vì 4 > 3 nên đổi chỗ 4;3 {3,7,9,5,4,10,2} => {3,7,9,5,4,10,2}, vì 3 < 10 nên không đổi chỗ {3,7,9,5,4,10,2} => {2,7,9,5,4,10,3}, vì 3 > 2 nên đổi chỗ 3;2 Tiếp tục i = 1 thực hiện tương tự: => {2,3,9,7,5,10,4} Tiếp tục i = 2 thực hiện tương tự: => {2,3,4,9,7,10,5} Tiếp tục i = 3 thực hiện tương tự: => {2,3,4,5,9,10,7} ……… Cho tới i = 5 thực hiện tương tự:

=> {2,3,4,5,7,9,10} Kết quả a[7] = {2,3,4,5,7,9,10} b)

Selection Sort Mảng a [7] = {7,5,9,4,3,10,2}

Tìm phần tử nhỏ nhất trong a [0 ... 6] và đặt nó ở đầu hoán đổi giá trị với phần tử đầu {2,5,9,4,3,10,7} Tìm phần tử nhỏ nhất trong a [1 ... 6] và đặt nó ở đầu a [1 ... 6] {2,3,9,4,5,10,7} Tìm phần tử nhỏ nhất trong a [2 ... 6] và đặt nó ở đầu a [2 ... 6] {2,3,4,9,5,10,7} Tìm phần tử nhỏ nhất trong a [3 ... 6] và đặt nó ở đầu a [3 ... 6] {2,3,4,5,9,10,7} Tìm phần tử nhỏ nhất trong a [4 ... 6] và đặt nó ở đầu a [4 ... 6] {2,3,4,5,7,10,9} Tìm phần tử nhỏ nhất trong a [5 ... 6] và đặt nó ở đầu a [5 ... 6] {2,3,4,5,7,9,10} Kết quả: a[7] = {2,3,4,5,7,9,10}

c) Insertion Sort Mảng a[7] = {7,5,9,4,3,10,2} Dùng vòng lặp for i = 1 đến 6 i = 1: Vì 5 < 7 nên di chuyển 7 và chèn 5 vào trước 7 (i-1) {5,7,9,4,3,10,2}

i = 2: 9 sẽ vẫn ở vị trí của nó vì tất cả các phần tử trong a [0 … i-1] đều < 9 {5,7,9,4,3,10,2} i = 3: 4 sẽ di chuyển về đầu và tất cả các phần tử 5,7,9 sẽ di chuyển lên một vị trí so với vị trí hiện tại của chúng. {4,5,7,9,3,10,2} i = 4: 3 sẽ di chuyển về đầu và tất cả các phần tử 4,5,7,9 sẽ di chuyển trước một vị trí so với vị trí hiện tại của chúng. {3,4,5,7,9,10,2} i = 5: 10 vẫn ở vị trí của nó vì tất cả các phần tử trong a [0 … i-1] đều < 10 {3,4,5,7,9,10,2} i = 6: 2 sẽ di chuyển về đầu và tất cả các phần tử 4,5,7,9,10 sẽ di chuyển trước một vị trí so với vị trí hiện tại của chúng. {2,3,4,5,7,9,10} Kết quả: a[7] = {2,3,4,5,7,9,10} d) Bubble Sort Mảng a[7] = {7,5,9,4,3,10,2} Lần lặp đầu tiên: {7,5,9,4,3,10,2} -> {5,7,9,4,3,10,2}, ở đây thuật toán sẽ so sánh 2 phần tử đầu tiên, và đổi chỗ cho nhau do 7 > 5 {5,7,9,4,3,10,2} -> {5,7,9,4,3,10,2}, hai phần tử đang xét đã đúng thứ tự nên chúng ta giữ nguyên 7 < 9, không cần đổi chỗ {5,7,9,4,3,10,2} -> {5,7,4,9,3,10,2}, đổi chỗ do 9 > 4 {5,7,4,9,3,10,2} -> {5,7,4,3,9,10,2}, đổi chỗ do 9 > 3 {5,7,4,3,9,10,2} -> {5,7,4,3,9,10,2}, {5,7,4,3,9,10,2} -> {5,7,4,3,9,2,10}, đổi chỗ do 10 > 2

Lần lặp thứ 2: {5,7,4,3,9,2,10} -> {5,7,4,3,9,2,10}, {5,7,4,3,9,2,10} -> {5,4,7,3,9,2,10}, đổi chỗ do 7 > 4 {5,4,7,3,9,2,10} -> {5,4,3,7,9,2,10}, đổi chỗ do 7 > 3 {5,4,3,7,9,2,10} -> {5,4,3,7,9,2,10} {5,4,3,7,9,2,10} -> {5,4,3,7,2,9,10}, đổi chỗ do 9 > 2 {5,4,3,7,2,9,10} -> {5,4,3,7,2,9,10} Lần lặp thứ 3: {5,4,3,7,2,9,10} -> {4,5,3,7,2,9,10}, đổi chỗ do 5 > 4 {4,5,3,7,2,9,10} -> {4,3,5,7,2,9,10}, đổi chỗ do vì 5 > 3 {4,3,5,7,2,9,10} -> {4,3,5,7,2,9,10} {4,3,5,7,2,9,10} -> {4,3,5,2,7,9,10}, đổi chỗ do 7 > 2 {4,3,5,2,7,9,10} -> {4,3,5,2,7,9,10} {4,3,5,2,7,9,10} -> {4,3,5,2,7,9,10} Lần lặp thứ 4: {4,3,5,2,7,9,10} -> {3,4,5,2,7,9,10}, đổi chỗ do 4 > 3 {3,4,5,2,7,9,10} -> {3,4,5,2,7,9,10} {3,4,5,2,7,9,10} -> {3,4,2,5,7,9,10}, đổi chỗ do 5 > 2 {3,4,2,5,7,9,10} -> {3,4,2,5,7,9,10} {3,4,2,5,7,9,10} -> {3,4,2,5,7,9,10} {3,4,2,5,7,9,10} -> {3,4,2,5,7,9,10} Lần lặp thứ 5: {3,4,2,5,7,9,10} -> {3,4,2,5,7,9,10} {3,4,2,5,7,9,10} -> {3,2,4,5,7,9,10}, đổi chỗ do 4 > 2 {3,2,4,5,7,9,10} -> {3,2,4,5,7,9,10}

{3,2,4,5,7,9,10} -> {3,2,4,5,7,9,10} {3,2,4,5,7,9,10} -> {3,2,4,5,7,9,10} {3,2,4,5,7,9,10} -> {3,2,4,5,7,9,10} Lần lặp thứ 6: {3,2,4,5,7,9,10} -> {2,3,4,5,7,9,10}, đổi chỗ do 3 > 2 {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện. Lần lặp thứ 7: {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} {2,3,4,5,7,9,10} -> {2,3,4,5,7,9,10} Kết quả: a[7] = {2,3,4,5,7,9,10} e) Quick Sort Mảng a[7] = {7,5,9,4,3,10,2} Trong partition(): iL = low = 0, iR = high = 6

mid = (iL + iR)/2 = 3, pivot = a[mid] = 4 Vòng while đầu tiên, iL 4) 2. Kiểm tra a[iR] < pivot (2 < 4) 3. Vì iL pivot (10 < 4) Thay đổi iR = iR – 1 = 4 Kiểm tra lại a[iR] < pivot (3 < 4) 3. Vì iL 2) => Kết thúc vòng lặp Return iL = 3 Trong quickSort(): Gán pi = iL = 3 Lúc này gọi đệ quy để chia mảng a[] ra thành hai nửa và thực hiện việc sắp xếp như trên, sau đó tiếp tục gọi lại cho chính nó để lặp lại toàn bộ chu trình như trên cho đến khi mảng chỉ còn một phần tử sẽ dừng lại đệ quy. quickSort(a, low, pi - 1);

quickSort(a, pi, high);

Chia mảng ra làm 2 nửa: a[low…pi - 1] = {2,3,4} a[pi…high] = {9,5,10,7} Thực hiện trên a[low…pi – 1] = {2,3,4} Thực hiện sắp xếp trong partition() => a[low…pi – 1] = {2,3,4} trả về iL = 2 Gán pi = iL = 2 Gọi đệ quy chia hai nửa: a[low…pi - 1] = {2,3} a[pi…high] = {4} -> Dừng đệ quy

Thực hiện trên a1[low…pi - 1] = {2,3} Thực hiện sắp xếp trong partition() => a[low…pi - 1] = {2,3} trả về iL = 1 Gán pi = iL = 1 Gọi đệ quy chia hai nửa: a[low…pi - 1] = {2} -> Dừng đệ quy a[pi…high] = {3} -> Dừng đệ quy

Thực hiện trên a[pi…high] = {9,5,10,7} Thực hiện sắp xếp trong partition() => a[pi…high] = {5,9,10,7} trả về iL = 1

Gán pi = iL = 1 Gọi đệ quy chia hai nửa: a[low…pi - 1] = {5} -> Dừng đệ quy a[pi…high] = {9,10,7} Thực hiện trên a[pi…high] = {9,10,7} Thực hiện sắp xếp trong partition() => a[pi…high] = {9,10,7} trả về iL = 2 Gán pi = iL = 2 Gọi đệ quy chia hai nửa: a[low…pi - 1] = {9,10} a[pi…high] = {7} -> Dừng đệ quy Thực hiện trên a[low…pi - 1] = {9,10} Thực hiện sắp xếp trong partition() => a[low…pi - 1] = {9,10} trả về iL = 1 Gán pi = iL = 1 Gọi đệ quy chia hai nửa: a[low…pi - 1] = {9} -> Dừng đệ quy a[pi…high] = {10} -> Dừng đệ quy Tới đây mảng đã được sắp xếp hoàn tất: -> Kết quả a[7] = {2,3,4,5,7,9,10} f) Merge Sort Mảng a[7] = {7,5,9,4,3,10,2} l = 0, r = 6

mergeSort(arr[], l, r) If r > l 1. Tìm chỉ số nằm giữa mảng để chia mảng thành 2 nửa: middle m = (l+r)/2 2. Gọi đệ quy hàm mergeSort cho nửa đầu tiên: mergeSort(arr, l, m) 3. Gọi đệ quy hàm mergeSort cho nửa thứ hai: mergeSort(arr, m+1, r) 4. Gộp 2 nửa mảng đã sắp xếp ở (2) và (3): merge(arr, l, m, r) Kết quả khi hoàn tất chia ra: Ta thu được các mảng con: {7} {5} {9} {4} {3} {10} {2} Thực hiện việc sắp xếp đồng thời trộn các mảng con đó lại với nhau trong merge(): - {7} {5} = > {5,7} (7 > 5) - {9} {4} => {4,9} (9 > 4) - {5,7} {4,9} => {4,5,7,9} - {3} {10} => {3, 10} - {2} => {2} - {3,10} {2} => {2,3,10} - {4,5,7,9} {2,3,10} => {2,3,4,5,7,9,10} Kết quả: a[7] = {2,3,4,5,7,9,10} g) Radix Sort: Mảng a[7] = {7,5,9,4,3,10,2} Đầu tiên, mảng sẽ được chia thành các nhóm dựa vào giá trị của chữ số hàng đơn vị. chúng ta sẽ chia được các nhóm sau: [10] // nhóm 0 [2] // nhóm 2

[3] // nhóm 3 [4] // nhóm 4 [5] // nhóm 5 [7] // nhóm 7 [9] // nhóm 9 Sau khi chia nhóm theo hàng đơn vị, thứ tự các phần tử trong mảng sẽ như sau: [10,2,3,4,5,7,9] Tiếp theo, mảng sẽ được chia thành các nhóm dựa vào hàng chục. Kết quả chúng ta được các nhóm: [2,3,4,5,7,9] // nhóm 0 [10] // nhóm 1 Sau khi chia nhóm theo hàng chục, thứ tự các phần tử trong mảng sẽ như sau: [2,3,4,5,7,9,10] Đến đây, toàn bộ các số không thuộc hàng trăm nên thuật toán sẽ dừng lại. Câu 10: Lựa chọn thuật toán sắp xếp phù hợp vào cài đặt cho dữ liệu nằm trên file - giải thích lý do. Trả lời: - Với mảng đã được sắp xếp sẵn, thì Bubble Sort cho tốc độ nhanh nhất do chi phí để biết được đây là mảng có thứ tự của thuật toán trên là O(n). - Với mảng gần như đã được sắp xếp thì Insertion Sort là sự lựa chọn tốt nhất do số phép hoán đổi phải thực hiện ít....