I. Các khái niệm:

1. Dữ liệu & CTDL:

-Dữ liệu: là các phần tử biểu diễn thông tin cần thiết cho bài toán.

+Một bài toán có thể có các loại dữ liệu: dl vào, dl trung gian, dl ra.

-CTDL: Là cách thức tổ chức các phần tử dữ liệu của bài toán.

-Cấu trúc lưu trữ(CTLT): Là cách biểu diễn một CTDL trong bộ nhớ, nói cách khác, đó là cách cài đặt CTDL trên máy tinh.

+1 CTDL có thể được cài đặt bởi nhiều CTLT khác nhau, ví dụ: một ctdl kiểu mảng có thể dược lưu trữ bởi các ô nhớ kế tiếp nhau trong bộ nhớ hoặc lưu trữ bằng các ô nhớ không kế tiếp nhau trong bộ nhớ.

+1 CTLT có thể cài đặt cho nhiều CTDL khác nhau, ví dụ: cấu trúc xâu ký tự, cấu trúc mảng đều có thể cài đặt trong bộ nhớ bằng các ô nhớ kế tiếp nhau.

2. Giải thuật:

Giải thuật là một hệ thống các thao tác, các phép toán được thực hiện theo từng bước xác định trên một số đối tượng nào đó (dữ liệu) sao cho sau 1 số bước hữu hạn ta thu được kết quả mong muốn.

-Tính chất cơ bản của GT:

+Tính thực hiện được

+Tính hữu hạn:

+Tính đúng đắn: phải cho kết quả như mong muốn

+Tính tổng quát: phải áp dụng được cho mọi bài toán cùng loại

-Cách diễn đạt giải thuật:

+dùng lời diễn giải các bước

+dùng lưu đồ

+dùng giả mã (giả ngôn ngữ lập trình)

3. Mối quan hệ giữa CTDL &GT:

- Xét tới giải thuật thì fai xét xem giải thuật đó tác động trên CTDL nào.

-Xét tới CTDL thì phải hiểu CTDL đó cần được tác động bằng giải thuật nào để được kết quả như mong muốn.

-Lựa chọn một CTDL thích hợp, trên đó xây dựng một giải thuật xử lý hiệu quả là hai khâu quan trọng nhất trong lập trình.

CTDL+ GT= chương trình

- Với một CTDL ta sẽ chọn một giải thuật tương ứng. Cấu trúc thay đổi thì giải thuật cũng thay đổi theo.

4. Ví dụ: Viếtgiả mã chương trình tìm UCLN của 2 số a,b:

Read (a,b)

R:=a mod b

While r<>0 do

{

A:=b; b:=r;

R:=a mod b;

}

II. Thiết kế & Phân tích giải thuật:

1.Thiết kế giải thuật:

1.1Modul hóa giải quyết bài toán (Chia để trị/ Top-down)

Nội dung của phương pháp mô đun hoá là coi bài toán lớn như một mô đun chính và phân chia nó thành các mô đun con, mỗi mô đun con lại được phân chia tiếp, cho tới những mô đun ứng với các phần việc cơ bản mà ta đã biết cách giải quyết.

Với phương pháp mô đun hoá bài toán thì lời giải của bài toán được tổ chức theo cấu trúc cây (phân cấp) có dạng như sau:

- Cách thiết kế Top-Down hay thiết kế từ khái quát đến đến chi tiết thể hiện như sau:

+Phân tích tổng quát toàn bộ vấn đề xuất phát từ dữ liệu và mục tiêu đề ra, đề cập đến vấn đề chủ yếu, rồi sau đó mới đi dần vào giải quyết các vấn đề cụ thể một cách chi tiết hơn.

* Ưu điểm của cách thiết kế Top - Down:

- Giải quyết bài toán có định hướng, tránh sa đà vào chi tiết phụ.

- Làm nền tảng cho lập trình có cấu trúc.

- Bài toán do nhiều người cùng làm, tách bài toán thành nhiều bài toán con tạo cho các nhóm làm việc độc lập không ảnh hưởng đến nhóm khác.

- Chương trình dễ dàng trong chỉnh lý và sửa chữa.

1.2 Phương pháp tinh chỉnh từng bước:

- Phương pháp tinh chỉnh tưng bước thể hiện như sau:

Thoạt đầu chương trình thể hiện giải thuật được trình bày bằng ngôn ngữ tự nhiên, phản ánh ý chính của công việc cần làm.

Các bước sau sẽ chi tiết hoá dần dần, tương ứng với các công việc nhỏ hơn, ta gọi là các bước tinh chỉnh. Càng ở các bước sau mô tả công việc hướng tới các lệnh của chương trình.

- Quá trình thiết kế giải thuật diễn ra như sau:

Ngôn ngữ tự nhiên -> Giả ngôn ngữ -> Ngôn ngữ lập trình

-Trong quá trình này dữ liệu cũng được tinh chế dần dần từ dạng cấu trúc đến dạng cài đặt cụ thể.

1.3 Ví dụ : Lập trình sắp xếp một dãy n số nguyên khác nhau theo thứ tự tăng dần.

* Có thể phác thảo giải thuật theo ngôn ngữ tự nhiên như sau:

- Từ dãy các số nguyên chưa được sắp xếp chọn ra số nhỏ nhất, đổi chỗ cho số đầu dãy.

- Cứ lặp lại quá trình đó cho đến khi dãy chưa được sắp trở thành rỗng.

* Dùng ngôn ngữ giả Pascal :

1. Bước tinh chỉnh đầu tiên là:

Fori:=1 To n-1 Do Begin

- Xét từ ai đến an để tìm số nhỏ nhất aj

- Đổi chỗ giữa ai và aj

End

2. Bước tinh chỉnh 2.1.: Tìm số nhỏ nhất

j:=i

For k:= j+1 To nDo

If ak < ajThenj:=k

3. Bước tinh chỉnh 2.2: Đổi chỗ

x:=ai ; ai:=aj ;aj=x;

* Sau khi chỉnh lại ta có thủ tục sắp xếp như sau:

Procedure Sap(a,n)

1. For i:=1 To n-1 Do

Begin

2.j:=i

For k:=j+1 To n Do

If a[k] < a[j] Thenj:=k

3. x:=a[i]; a[i]:=a[j]; a[j]:=x;

End

Return

2.Phân tích giải thuật:

2.1Đặt vấn đề:

* Khi xây dựng giải thuật và chương trình tương ứng có các nhu cầu sau:

- Phân tích tính đúng đắn: Chạy thử chương trình trên bộ dữ liệu, so sánh kết quả với kết quả đã biết.

Các công cụ toán học chứng minh tính đúng đắn của giải thuật.

- Tính đơn giản : Dễ hiểu, dễ lập trình, dễ chỉnh lý.

- Phân tích thời gian: Thời gian thực hiện giải thuật là tiêu chuẩn đánh giá hiệu lực của giải thuật.

* Với một bài toán có nhiều giải thuật chọn giải thuật dẫn đến kết quả nhanh nhất là vấn đề đòi hỏi của thực tế.

* Thời gian thực hiện T phụ thuộc vào các yếu tố:

- Kích thước của dữ liệu vào: Nếu gọi n là kích thước của dữ liệu vào, thì thời gian thực hiện T là một hàm của n:T(n)

- Các kiểu lệnh, tốc độ xử lý của máy tính, ngôn ngữ viết chương trình, chương trình dịch cũng ảnh hưởng đến tốc độ thực hiện. Nhưng những yếu tố này không đồng đều vỡi mỗi loại máy vi tính, vì vậy không thể đưa chúng vào xác lập T(n).

Do vậy dùng “ Độ phức tạp tính toán của giải thuật “ để đánh giá thời gian thực hiện giải thuật.

.................

b. Loại bỏ một nút ra khỏi danh sách nối kép

Procedure Doubdel (L, R, M)

Cho con trỏ L, R trỏ tới nút cực trái và nút cực phải của một danh sách nối kép, M là con trỏ trỏ tới một nút trong danh sách mà ta loại bỏ. Thuật giải này gồm các bước sau:

1. { Trường hợp danh sách rỗng }

If R=NULL then begin

Write(‘ danh sach rong ‘)

Return

end

2. { Loại bỏ }

Case

L= R : Begin { Danh sach chi co 1 nút M trỏ tới }

L:=Null

R:=Null

end

M=L: Begin { Nút cực trái bị loại }

L:=RPTR(L)

LPTR(L):=null end

M=R: Begin { Nút cực phải bị loại }

R:=LPTR(R)

RPTR(R):=null end

ELSE

RPTR(LPTR(M)):=RPTR(M)

LPTR(RPTR(M)):=LPTR(M)

Endcase

M => AVAIL

Return

Chương 6: Đồ thị

1. Các khái niệm

1.1. Định nghĩa đồ thị

Đồ thị G(V,E) bao gồm một tập hữu hạn V các đỉnh (hay nút) và một tập hữu hạn E các cặp đỉnh mà ta gọi là cung ( hay cạnh).

Ví dụ 1: Một mạng gồm các máy tính và các kênh điện thoại nối các máy tính này là một đồ thị.

Ví dụ 2: Một mạng gồm các thành phố, thị xã và các đường bộ nối các thành phố, thị xã là một đồ thị.

1.2. Định nghĩa đồ thị vô hướng

Đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh và E là tập các cặp đỉnh không có thứ tự gọi là các cung.

3. Phép duyệt đồ thị

* Xét đồ thị vô hướng G(V,E) và một đỉnh vÎV. Ta cần thăm tất cả các đỉnh của G mà có thể “ với tới” từ đỉnh v ( nghĩa là đồ thị liên thông).

Có 2 cách duyệt đồ thị:

- Phép tìm kiếm theo chiều sâu ( Depth first search )

- Phép tìm kiếm theo chiều rộng (Breadth first search )

3.1. Phép tìm kiếm theo chiều sâu ( Depth first search )

Xét đồ thị vô hướng. Phép tìm kiếm theo chiều sâu thể hiện như sau:

- Đỉnh xuất phát v được thăm.

- Tiếp theo đó ta thăm đỉnh w là đỉnh chưa được thăm và là lân cận của v. Phép tìm kiếm theo chiều sâu xuất phát từ w lại được thực hiện.

Trong trường hợp đỉnh u đã được thăm mà mọi đỉnh lân cận của nó đã được thăm rồi thì ta quay lại đỉnh cuối cùng vừa được thăm ( mà đỉnh này còn đỉnh w là lân cận của nó chưa được thăm) và phép tìm kiếm theo chiều sâu xuất phát từ w lại được thực hiện.

* Thủ tục phép duyệt theo chiều sâu như sau:

Cho một đồ thị G(V,E) vô hướng có n đỉnh và véc tơ Visited(n) gồm n phần tử, ban đầu véc tơ này có giá trị =0. Thuật giải này thực hiện thăm mọi đỉnh “ với tới được “ từ đỉnh v.

Procedure DFS(v)

1. Visited(v):=1 { đánh dấu v được thăm }

2. FOR mỗi đỉnh w lân cận với v DO

If Visited(w)=0 then CALL DFS(w);

3. Return

* Đánh giá thuật toán:

+ Trường hợp biểu diễn đồ thị dùng danh sách móc nối: G có e cung, mỗi nút với tới 1 lần, nên thời gian tìm kiếm là O(e).

+ Trường hợp biểu diễn đồ thị dùng ma trận lân cận : thì thời gian xác định mọi điểm lân cận của v là O(n). Có n đỉnh nên thời gian tìm kiếm là O(n2).

3.2. Phép tìm kiếm theo chiều rộng (Breadth first search )

Xét đồ thị vô hướng. Phép tìm kiếm theo chiều rộng thể hiện như sau:

- Đỉnh xuất phát v được thăm.

- Tiếp theo các đỉnh chưa được thăm mà là lân cận của v sẽ được thăm, rồi đến các đỉnh chưa được thăm là lân cận làn lượt của các đỉnh này và cứ tương tự như vậy.

* Thủ tục phép duyệt theo chiều rộng như sau:

Cho một đồ thị G(V,E) vô hướng có n đỉnh và véc tơ Visited(n) gồm n phần tử, ban đầu véc tơ này có giá trị =0. Thuật giải này thực hiện thăm mọi đỉnh “ với tới được “ từ đỉnh v. Bắt đầu từ đỉnh v. Mọi đỉnh i được thăm đánh dấu bằng Visited(i):=1.

Dùng hàng đợi Q có kích thước n; F, R là lối trước và lối sau của hàng đợi. Khi thăm 1 đình thì loại bỏ khỏi hàng đợi; khi chưa thăm thì bổ sung vào hàng đợi

Procedure BFS(v)

1. Khởi tạo hàng đợi Q với v được đưa vào.

2. Visited(v):=1 { đánh dấu v được thăm }

3. While Q không rỗng DO

Begin

Call CQDELETE(v,Q) { loại bỏ v ra khỏi Q}

FOR mỗi đỉnh w lân cận với v DO

Begin

If Visited(w)=0 then

Begin

CALL CQINSERT(w,Q); { Bổ sung w vào Q}

Visited(w):=1

End

End

End

4. Return

* Đánh giá giải thuật: Vòng lặp While lặp lại n lần .

- Nếu biểu diễn đồ thị bằng ma trận lân cận thì thời gian thực hiện là O(n2).

- Nếu biểu diễn đồ thị bằng danh sách lân cận thì thời gian thực hiện là O(e).