Mở đầu về thiết kế, đánh giá thuật toán và kiến thức bổ trợ

Khái niệm về thuật toán

Thuật toán (algorithm) là một trong những khái niệm quan trọng trong lĩnh vực tin học. Thuật ngữ thuật toán được xuất phát từ nhà toán học Arập Abu Ja’far Mohammedibn Musa al Khowarizmi (khoảng năm 825).

Tuy nhiên lúc bấy giờ và trong nhiều thế kỷ sau, nó không mang nội dung như ngày nay chúng ta quan niệm. Thuật toán 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. Có thể mô tả thuật toán đó như sau:

ThuậttoánEuclid.

Input: m, n nguyên dương

Output: g (ước chung lớn nhất của m và n)

Phương pháp:

Bước 1: Tìm r, phần dư của m cho n

Bước 2: Nếu r = 0, thì g:=n (gán giá trị của n cho g),và dừng lại. Trong trường

hợp ngược lại (r≠0), thì m:=n; n:=r và quay lại bước 1.

Chúng ta có thể quan niệm các bước cần thực hiện để làm một món ăn, được mô tả trong các sách dạy chế biến món ăn, là một thuật toán. Cũng có thể xem các bước cần tiến hành để gấp đồ chơi bằng giấy ,được trình bày trong sách dạy gấp đồ chơi bằng giấy là một thuật toán. Phương pháp cộng nhân các số nguuyên, chúng ta đã được học

ở cấp I cũng là các thuật toán.

Vì vậy ta có định nghĩa không hình thức về thuật toán như sau:

Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán,

hoặc hành động cần thực hiện ... để cho ta lời giải của bài toán.

Các yêu cầu về thuật toán

Định nghĩa trên về thuật toán tất nhiên còn chứa nhiều điều chưa rõ ràng. Để hiểu đầy đủ ý nghĩa của khái niệm thuật toán, chúng ta đưa ra 5 đặc trưng sau đây của thuật toán.

Phương pháp liệt kê từng bước

Ngôn ngữ liệt kê từng bước nội dung như sau:

Thuật toán: Tên thuật toán và chức năng.

Vào: Dữ liệu vào với tên kiểu.

Ra: Các dữ liệu ra với tên kiểu.

Biến phụ (nếu có) gồm tên kiểu.

Hành động là các thao tác với các lệnh có nhãn là các số tự nhiên.

Phương pháp sơ đồ

Phương pháp dùng sơ đồ khối mô tả thuật toán là dùng mô tả theo sơ đồ trên mặt

phẳng các bước của thuật toán. Sơ đồ khối có ưu điểm là rất trực giác dễ bao quát.

Để mô tả thuật toán bằng sơ đồ khối ta cần dựa vào các nút sau đây:

Nútthaotác:Biểu diễn bằng hình chữ nhật,

Nútđiềukhiển:Được biểu diễn bằng hình thoi, trong đó ghi điều kiện cần kiểm tra trong quá trình tính toán.

Nútkhởiđầu,kếtthúc:Thường được biểu diễn bằng hình tròn thể hiện sự bắt đầu hay kết thúc quá trình.

Cung:Đoạnnối từ nút này đến nút khác và có mũi tên chỉ hướng.

Danh sách

Danh sách là một tập sắp thứ tự các phần tử cùng một kiểu. Đối với danh sách, người ta có một số thao tác: Tìm một phần tử trong danh sách, chèn một phần tử vào danh sách, xoá một phần tử khỏi danh sách, sắp xếp lại các phần tử trong danh sách theo một trật tự nào đó v.v...

Các phương pháp biểu diễn danh sách trong máy tính:

- Mảng một chiều

- Danh sách nối đơn

- Danh sách nối kép

- Danh sách nối vòng một hướng

- Danh sách nối vòng hai hướng

Các phép toán cơ bản trên danh sách

Để thiết lập kiểu dữ liệu trừu tượng danh sách (hay ngắn gọn là danh sách) ta phải định nghĩa các phép toán trên danh sách. Và như chúng ta sẽ thấy trong toàn bộ giáo trình, khôngc ó một tập hợp các phép toán nào thích hợp cho mọi ứng dụng (application). Vì vậy ở đây ta sẽ định nghĩa một số phép toán cơ bản nhất trên danh sách. Để thuận tiện cho việc định nghĩa ta giả sử rằng danh sách gồm các phần tử có kiểu là kiểu phần tử (elementType); vị trí của các phần tử trong danh sách có kiểu là kiểu vị trí và vị trí sau phần tử cuối cùng trong danh sách L là ENDLIST(L). Cần nhấn mạnh rằng khái niệm vị trí (position) là do ta định nghĩa, nó không phải là giá trị của các phần tử trong danh sách. Vị trí có thể là đồng nhất với vị trí lưu trữ phần tử hoặc không.

Các phép toán được định nghĩa trên danh sách là:

INSERT_LIST(x,p,L):xen phần tử x ( kiểu ElementType ) tại vị trí p (kiểu

position) trong danh sách L. Tức là nếu danh sách là a1, a2, . , ap-1, ap,.. , an thì sau khi xen ta có kết quả a1, a2. . . ap-1, x, ap, . . . , an. Nếu vị trí p không tồn tại trong danh sách thì phép toán không được xác định.

LOCATE(x,L):thực hiện việc định vị phần tử có nội dung x đầu tiên trong danh sách

L. Locate trả kết quả là vị trí (kiểu position) của phần tử x trong danh sách. Nếu x không có trong danh sách thì vị trí sau phần tử cuối cùng của danh sách được trả về, tức là ENDLIST(L).

- RETRIEVE(p,L):lấy giá trị của phần tử ở vị trí p (kiểu position) của danh sách L; nếu vị trí p không có trong danh sách thì kết quả không xác định (có thể thông báo lỗi).

- DELETE_LIST(p,L):chương trình con thực hiện việc xoá phần tử ở vị trí p (kiểu position) của danh sách. Nếu vị trí p không có trong danh sách thì phép toán không được định nghĩa và danh sách L sẽ không thay đổi

- NEXT(p,L):cho kết quả là vị trí của phần tử (kiểu position) đi sau phần tử p; nếu p là phần tử cuối cùng trong danh sách L thì NEXT(p,L) cho kết quả là

ENDLIST(L):Next không xác định nếu p không phải là vị trí của một phần tử trong danh sách.

- PREVIOUS(p,L):cho kết quả là vị trí của phần tử đứng trước phần tử p trong danh sách. Nếu p là phần tử đầu tiên trong danh sách thì Previous(p,L) không xác định. Previous cũng không xác định trong trường hợp p không phải là vị trí của phần tử nào trong danh sách.

- FIRST(L):cho kết quả là vị trí của phần tử đầu tiên trong danh sách. Nếu danh sách rỗng thì ENDLIST(L) được trả về.

- EMPTY_LIST(L):cho kết quả TRUE nếu danh sách có rỗng, ngược lại nó cho giá trị FALSE.

- MAKENULL_LIST(L):khởi tạo một danh sách L rỗng.

- Trong thiết kế các giải thuật sau này chúng ta dùng các phép toán trừu tượng đã được định nghĩa ở đây như là các phép toán nguyên thủy.

Đồ thị

Cây