Sơ lợc về các chủ đề
Sau đây là sơ lợc về các chủ đề sẽ đợc đề cập trong phần này của chơng trình:
+ Phần cơ sở: là các công cụ và phơng pháp đợc dùng xuyên suốt cho tất cả các
chơng sau của phần này. Nó gồm một phần bàn luận ngắn về Pascal, theo sau là
giới thiệu về các cấu trúc dữ liệu cơ bản gồm mảng, xâu liên kết, ngăn xếp, hàng
đợi và cây. Chúng ta sẽ bàn luận về công dụng thực tiễn đệ quy và bắt đầu hớng
tới việc phân tích và tiếp cận thực toán.
+ Sắp xếp: Các phơng pháp sắp xếp sẽ đợc phát triển, đợc mô tả, đợc so sánh với
nhau. Các thuật toán cho nhiều vấn đề có liên quan sẽ đợc xem xét gồm có hàng
đợi u tiên, phép chọn và phép trộn. Một vài nền tảng trong số này đợc dùng nh là
nền tảng cho các thuật toán khác tiếp sau trong phần này.
+ Xử lý chuỗi: gồm một loạt các phơng pháp để phân tích câu. Các ky thuật nén
tập và mật mã cũng sẽ đợc khảo sát. Cũng vậy, một giới thiệu về các chủ đề nâng
cao cùng đợc cung cấp qua việc xem xét một vài bài toán cơ bản quan trọng trong
phạm vi của chúng.
+ Hình học: là một sự tập hợp có chọn lọc các phơng pháp để giải quyết các bài
toán liên quan đến điểm và đờng ( và các đối tợng hình học đơn giản khác ).
Chúng ta sẽ xem xét các thuật toán để tìm bao lồi của một tập điểm, phần giao của
các đối tợng, để giải bài toán điểm gần nhất, tìm kiếm nhiều chiều ...
+ Đồ thị: Một chiến lợc tổng quát để tìm kiếm trên các đồ thị sẽ đợc phát triển và
đợc áp dụng cho các bài toán liên thông cơ bản, gồm có đờng đi ngắn nhất, cây
liên thông tối thiểu, mạng và so khớp. Một sự xem xét thống nhất đối với các thuật
toán này chứng tỏ rằng tất cả đều dựa vào một thủ tục và thủ tục này phụ thuộc
vào một cấu trúc dữ liệu cơ bản đã phát triển trớc đó.
+ Các thuật toán toán học: gồm các phơng pháp cơ bản từ số học và các số
nguyên, đa thức, và ma trận cũng nh các thuật toán để giải quyết cac vấn đề toán
học mà nó phát sinh trong nhiều ngữ cảnh : việc tạo số ngẫu nhiên, lỡi giải của các
chơng trình đồng thời, xấp xỉ dữ liệu, và lấy tích phân. Sự nhấn mạnh thiên về các
khía cạnh thuật toán của phơng pháp, chứ không phải trên nền tảng của toán học
+ Các chủ đề cao cấp: đợc thảo luận nhằm mục đích liên hệ các chủ đề trong tập
sách này với nhiều lĩnh vực nghiên cứu cao cấp khác. Phần cứng chuyên dụng, quy

Ta khai báo :
Type
Item = Record
key : Integer;
Info : Integer;
End;
Var
A : Array[1..n] of Item;
Khoá của phần tử có thể là chữ hoặc số.
Yêu cầu giải thích là dùng ít vùng nhớ và thời gian thực hiện nhanh.
b) Phơng pháp đếm (Counting sort)
* Giải thích:
Nội dung của phơng pháp này là đếm các phần tử có khoá nhỏ hơn hay bằng
khoá của các phần tử A[i]. Nếu có j phần tử có khoá nhỏ hơn khoá của phần tử
A[i] thì phần tử A[i] sẽ có vị trí theo thứ tự (j+1) trong dãy đã có thứ tự.
Trong giải thuật, ta dùng mảng Count[i] ( i = 1, 2, .. n ) với Count[i] cho biết số
phần tử có khoá nhỏ hơn khoá của phần tử A[i]. Nh vậy Count[i+1] là vị trí của
phần tử A[i] trong dãy đã có thứ tự.
* Ví dụ:
Sắp xếp dãy 2 3 1 5 2 7 6 9 4
i: 1 2 3 4 5 6 7 8
Count: 2 0 4 1 6 5 7 3
Nh vậy phần tử có khoá 9 ở vị trí 8 vì Count[9]=7.
* Thể hiện bằng Pascal:
Procedure Count_Sort;
Var
Count : Array[1..n] of Integer;
A : Array[1..n] of Item;
i,j : Integer;
Begin

Var
x : Item;
i,j : Integer;
Begin
For i := 2 to n do
Begin
x := A[i];
A[0] := x;
j := j - 1;
While x.Key < A[j].Key do
Begin
A[j+1] := A[j];
j := j - 1;
End;
A[j+1] := x;
End;
End;
d) Phơng pháp chọn (Selection Sort)
* Giải thích:
3
Nội dung của phơng pháp này là ở bớc thứ i (i = 1, 2, 3, ..., n-1 ) ta lựa chọn phần
tử nhỏ nhất trong dãy A[i]..A[n] rồi đổi chổ phần tử này với phần tử A[i]. Cuối
cùng ta sẽ có dãy A[1]..A[n] có thứ tự.
* Ví dụ:
Ta phải sắp xếp dãy số :
39 50 7 37 89 13 1 62
i=1 39 50 7 37 89 13 1 62
i=2 1 50 7 37 89 13 39 62
i=3 1 7 50 37 89 13 39 62
i=4 1 7 13 37 89 50 39 62

- Bubble Sort.
- Shake Sort.
- Sell Sort.
- Quick Sort.
* Bubble Sort:
* Giải thích:
4
Nội dung của phơng pháp này là duyệt các dãy A[1], ..., A[n]. Nếu A[i].Key >
A[i+1].Key (i = 1, 2, 3, ..., n-1)#0 thì ta đổi chỗ A[i].Key với phần tử A[i+1].Key.
Lập lại quá trình duyệt dãy này cho đến khi không còn việc đổi chổ của hai phần
tử.
Chú ý rằng bất cứ lúc nào phần tử nhỏ nhất cũng gặp trớc tiên. Nó nh những bột
khí nhẹ sẽ nổi lên trên khi đun nớc. Sau đó ở thứ hai phần tử nhỏ thứ 2 sẽ đợc đặ
vào đúng một vị trí. Vì vậy sắp xếp nổi bột thao tác nh một kiểu sắp xếp chọn,
mặc dù nó không làm nhiều việc hơn để đa từng phần tử vào đúng vị trí.
* Ví dụ:
Ta phải sắp xếp dãy số:
39 50 7 37 89 13 1 62
Bớc 0 1 2 3 4 5 6 7
50 1 1 1 1 13 1 62
39 39 7 7 7 7 7 7
7 50 39 13 13 13 13 13
37 7 50 39 37 37 37 37
89 37 13 50 39 39 39 39
13 89 37 37 50 50 50 50
1 13 89 62 62 62 62 62
62 62 62 89 89 89 89 89
* Thể hiện bằng Pascal:
Procedure Bubble_Sort;
Var

x := A[i];
A[i] := A[i+1];
A[i+1] := x;
End;
End;
End;
f* Shake Sort:
* Giải thích:
Phơng pháp này là một cải tiến của phơng pháp Bubble Sort theo hớng "Không
những phần tử nhẹ nổi lên trên mà cả phần tử nặng cũng xuống dới" giống nh khi
ta rung"rung" một cái nồi và thuật toán sắp xếp phải đợc điều khiển cả hai quá
trình "nổi lên" và "chìm xuống" này một cách tự giác. Muốn vậy ta phải ghi nhớ
lần đổi chổ cuối cùng khi duyệt dãy từ trên lên và khi duyệt từ trên xuoóng để
quyết định chu trình kế tiếp sẽ duyệt từ đâu đến đâu.
* Ví dụ:
Sắp xếp dãy số:
39 50 7 37 89 13 1 62
d = 2 3 3 4 4
c = 8 8 7 7 4
39 1 1 1 1
50 39 39 7 7
7 50 7 39 13
37 7 37 13 37
89 37 50 37 39
13 89 13 50 50
1 13 62 62 62
62 62 89 89 89
* Thể hiện bằng Pascal:
Procedure Shake_Sort;
Var

Các phơng pháp sắp xếp dã trình bày ở trên nói chung đều di chuyển mỗi phần tử
đi một vị trí trong mỗi bớc. Phơng pháp Shell Sort dựa trên ý tởng chính là hoán
các phần tử ở xa nhau. Để làm đợc việc đó ta cần phải sắp các tập tin để nó có tính
chất là việc lấy mọi phần tử thứ h (bắt đầu từ vị trí bất kì nào) cũng đều cho ra tập
tin đã sắp. Một tập tin nh vậy đợc gọi là sắp theo độ dài bớc h. Một cách nói khác,
một tập tin dợc sắp theo độ dài bớc h là tập tin đợc sắp độc lập với nhau, đan xen
vào nhau. Bằng cách sắp xếp theo độ dài bớc h ứng với vài giá trị h khá lớn, chúng
ta có thể di chuyển các phần tử ở những khoảng cách xa nhau trong mảng và vì
vậy dễ dàng hơn để sắp xếp độ dài bớc h các giá tri nhỏ hơn. Dùng thủ tục cho bất
kì một dãy các giá trị của h tận cùng là 1 sẽ cho ra một tập tin đã sắp xong: Dó
chính là Shell Sort.
* Ví dụ:
Ta phải sắp xếp dãy số:
39 50 7 39 89 13 1 62
Bớc 1: 4-Sort
39 50 7 39 89 13 1 62
39 13 1 37 89 50 7 62
Bớc 2: 2-Sort
39 13 1 37 89 50 7 62
1 13 7 37 39 50 89 62
Bớc 3: 1-Sort
1 13 7 37 39 50 89 62
1 7 13 37 39 50 89 62
* Thể hiện bằng Pascal:
Chú ý:
7