LỜI NÓI ĐẦU
Ngày nay, khoa học máy tính và công nghệ thông tin phát triển mạnh mẽ,
thâm nhập vào hầu hết mọi lĩnh vực hoạt động của con người. Nhu cầu về các
hệ thống thông minh đã trở thành một nhu cầu thiết yếu. Đó là lý do ra đời Trí
tuệ nhân tạo, một lĩnh vực của khoa học máy tính chuyên nghiên cứu, phát triển
các hệ thống ngày càng thông minh hơn. Lập trình Hàm, lập trình Prolog là
những ngôn ngữ lập trình cơ bản và rất quan trọng trong các hệ thống Trí tuệ
nhân tạo.
Bởi vậy, nhóm tác giả đã chọn đề tài với những nội dung liên quan như
sau:
Phần I: LÝ THUYẾT LẬP TRÌNH HÀM
Đề tài: Áp dụng kiểu dữ liệu trừu tượng, xây dựng kiểu cấu trúc dữ liệu truyền
thống hàng đợi (Queue) trong Scheme. Cho ví dụ minh hoạ vận dụng hàng
đợi để quản lý nhập/xuất một sản phẩm.
Phần II: BÀI TOÁN LẬP TRÌNH HÀM
Đề tài: Hãy viết chương trình Scheme mô phỏng các hàm đệ quy thực hiện các
phép chia (Division) và tìm giá trị căn bậc hai (Square Root)
Phần III: BÀI TOÁN LẬP TRÌNH PROLOG
Đề tài: Cài đặt thuật toán tìm kiếm sâu (Depth-First-Search) trong lý thuyết trí
tuệ nhân tạo (Artificial Intelligence). Cho ví dụ minh hoạ chạy demo.
Do thời gian và vốn kinh nghiệm còn hạn chế nên không thể tránh khỏi
những sai sót, kính mong Thầy giáo và các bạn góp ý để tiểu luận được hoàn
thiện hơn.
Xin chân thành cảm ơn!
Nhóm học viên thực hiện:
1. 1. Lê Nam Trung
2. 2. Nguyễn Nương Quỳnh
3. 3. Nguyễn Duy Linh
4. 4. Hoàng Đình Tuyền
MỤC LỤC
LỜI NÓI ĐẦU 1

Ngày nay, khoa học máy tính và công nghệ thông tin phát triển mạnh mẽ, thâm
nhập vào hầu hết mọi lĩnh vực hoạt động của con người. Nhu cầu về các hệ thống
thông minh đã trở thành một nhu cầu thiết yếu. Đó là lý do ra đời Trí tuệ nhân
tạo, một lĩnh vực của khoa học máy tính chuyên nghiên cứu, phát triển các hệ
thống ngày càng thông minh hơn. Lập trình Hàm, lập trình Prolog là những
ngôn ngữ lập trình cơ bản và rất quan trọng trong các hệ thống Trí tuệ nhân tạo.
1
Bởi vậy, nhóm tác giả đã chọn đề tài với những nội dung liên quan như sau: 1
Phần I: LÝ THUYẾT LẬP TRÌNH HÀM 1
Đề tài: Áp dụng kiểu dữ liệu trừu tượng, xây dựng kiểu cấu trúc dữ liệu truyền
thống hàng đợi (Queue) trong Scheme. Cho ví dụ minh hoạ vận dụng hàng đợi
để quản lý nhập/xuất một sản phẩm. 1
Do thời gian và vốn kinh nghiệm còn hạn chế nên không thể tránh khỏi những
sai sót, kính mong Thầy giáo và các bạn góp ý để tiểu luận được hoàn thiện hơn.
1
Xin chân thành cảm ơn! 1
Nhóm học viên thực hiện: 1
MỤC LỤC 1
Phần I: LÝ THUYẾT LẬP TRÌNH HÀM 3
Đề tài: Áp dụng kiểu dữ liệu trừu tượng, xây dựng kiểu cấu trúc dữ liệu truyền
thống hàng đợi (Queue) trong Scheme. Cho ví dụ minh hoạ vận dụng hàng đợi
để quản lý nhập/xuất một sản phẩm. 3
I. Tổng quan về Hàng đợi (Queue) 3
1. Hàng đợi (Queue) 3
II. Xây dựng kiểu cấu trúc dữ liệu truyền thống hàng đợi (Queue) trong Scheme 7
III. Ví dụ minh hoạ vận dụng hàng đợi để quản lý nhập/xuất một sản phẩm 10
Phần II: BÀI TOÁN LẬP TRÌNH HÀM 12
Phần III: BÀI TOÁN LẬP TRÌNH PROLOG 14
I. Thuật toán tìm kiếm chiều sâu 14
1. Sơ lược thuật toán tìm kiếm chiều sâu: 14

2. Kỹ thuật tìm kiếm chiều sâu: 15
3. Cài đặt chương trình 17
4. Ưu và nhược điểm của phương pháp tìm kiếm chiều sâu: 20
II. Thuật toán tìm kiếm chiều rộng 21
1. Sơ lược thuật toán tìm kiếm chiều rộng: 21
2. Kỹ thuật tìm kiếm chiều rộng: 21
Ví dụ: 22
3. Cài đặt chương trình 23
III. So sánh thuật toán tìm kiếm chiều sâu, tìm kiếm chiều rộng 28
TÀI LIỆU THAM KHẢO 30
Phần I: LÝ THUYẾT LẬP TRÌNH HÀM
Đề tài: Áp dụng kiểu dữ liệu trừu tượng, xây dựng kiểu cấu trúc dữ liệu
truyền thống hàng đợi (Queue) trong Scheme. Cho ví dụ minh hoạ vận
dụng hàng đợi để quản lý nhập/xuất một sản phẩm.
I. Tổng quan về Hàng đợi (Queue)
1. Hàng đợi (Queue)
Hàng đợi là một vật chứa (container) các đối tượng làm việc theo cơ chế FIFO
(First In First Out) nghĩa là việc thêm một đối tượng vào hàng đợi hoặc lấy một
đối tượng ra khỏi hàng đợi được thực hiện theo cơ chế "Vào trước ra trước".
Các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào nhưng chỉ có đối
tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi.
Thao tác thêm một đối tượng vào hàng đợi và lấy một đối tượng ra khỏi hàng
đợi lần lượt được gọi là "enqueue" và "dequeue".
Việc thêm một đối tượng vào hàng đợi luôn diễn ra ở cuối hàng đợi và một
phần tử luôn được lấy ra từ đầu hàng đợi.
Ta hình dung nguyên tắc hoạt động của Queue như sau:
Trong tin học, CTDL hàng đợi có nhiều ứng dụng: khử đệ qui, tổ chức lưu vết
các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và
phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím, .
Ta có thể định nghĩa CTDL hàng đợi như sau: hàng đợi là một CTDL trừu

tượng (ADT) tuyến tính. Tương tự như stack, hàng đợi hỗ trợ các thao tác:
EnQueue(o): Thêm đối tượng o vào cuối hàng đợi
DeQueue(): Lấy đối tượng ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó.
Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.
IsEmpty(): Kiểm tra xem hàng đợi có rỗng không.
Front(): Trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu
hàng đợi rỗng thì lỗi sẽ xảy ra.
Các thao tác thêm, trích và huỷ một phần tử phải được thực hiện ở 2 phía khác
nhau của hàng đợi do đó hoạt động của hàng đợi được thực hiện theo nguyên
tắc FIFO (First In First Out - vào trước ra trước).
Cũng như stack, ta có thể dùng cấu trúc mảng 1 chiều hoặc cấu trúc danh sách
liên kết để biểu diễn cấu trúc hàng đợi.
2. Các kĩ thuật trên hàng đợi
Có rất nhiều kĩ thuật hàng đợi: FIFO (first in first out), PQ (priority queue-hàng
đợ ưu tiên), FQ (fair queue-hàng đợi cân bằng). FIFO đây là kĩ thuật xếp hàng
vào trước ra trước cơ bản. Các gói đến trước sẽ là các gói đầu tiên được xử lý.
Khi hàng đợi đầy và có tắc nghẽn xảy ra thì các gói đến sẽ bị loại bỏ. Hàng đợi
FIFO dựa vào hệ thống đầu cuối để điều khiển tắc nghẽn thông qua cơ chế điều
khiển tắc nghẽn. Do loại hàng đợi này rất đơn giản nhiều khi không điều khiển
được tắc nghẽn nên ta thường xét các loại hàng đợi hiệu quả hơn: hàng đợi ưu
tiên(PQ), hàng đợi cân bằng (FQ), hàng đợi có trọng số (WQ).
a. Hàng đợi FIFO (First In First Out)
FIFO là hàng đợi mặc định được sử dụng trong hầu hết các router trên thế giới.
Hoạt động của FIFO. Các gói đến từ các luồng khác nhau được đối xử công
bằng bằng cách đưa vào các hàng đợi theo trật tự đến (gói nào đến trước sẽ
được đưa vào trước và được phục vụ trước)
Hàng đợi hoạt động như một nơi lưu giữ các gói để tránh việc loại bỏ các gói
không cần thiết khi có dấu hiệu của tắc nghẽn. Khi có tắc nghẽn xảy ra, và hàng
đợi tràn thì tất cả các gói đến sẽ bị loại bỏ. Hàng đợi FIFO được sử dụng hầu
hết trong các router, nó đơn giản do không phải định cấu hình cho nó mà chỉ

việc sử dụng luôn. Trong các router của cisco, khi không có kế hoạch hàng đợi
nào khác được cấu hình, thì tất cả các giao diện(ngoại trừ các giao diện có tốc
độ bằng hoặc nhỏ hơn luồng E1) đều sử dụng hàng đợi FIFO mặc định. Tốc độ
xử lý gói phải nhanh hơn tốc độ các gói đến hàng đợi IF0 thì mới tránh được
hiện tượng tắc nghẽn trong mạng (hàng đợi IF1 rỗng), khi tốc độ xử lý quá thấp
hơn so với tốc độ các gói vào, có nghĩa là tốc độ ra nhỏ hơn tốc gói vào (hàng
đợi đầu ra dễ bị tràn) thì sẽ xảy ra tắc nghẽn khi có quá nhiều gói đi vào trong
mạng, và khi vấn đề này xảy ra thì các gói đến sau sẽ bị loại bỏ
b. Hàng đợi ưu tiên PQ (Priority Queue)
Kĩ thuật này được sử dụng trong trường hợp đa hàng đợi, mỗi hàng đợi có một
mức ưu tiên khác nhau, hàng đợi nào có mức ưu tiên cao nhất sẽ được ưu tiên
phục vụ trước. Khi có tắc nghén xảy ra thì các gói trong các hàng đợi có độ ưu
tiên thấp sẽ bị loại bỏ. Có một vấn đề đối với kĩ thuật này: khi các hàng đợi có
độ ưu tiên cao quá nhiều thì các gói trong hàng đợi có độ ưu tiên thấp sẽ không
bao giờ được phục vụ. Các gói được phân loại và được sắp xếp vào hàng đợi
tuỳ thuộc vào thông tin bên trong các gói. Tuy nhiên kĩ thuật này dễ bị lạm
dụng bởi người sử dụng hay các ứng dụng do ấn định các độ ưu tiên không cho
phép.
Vậy PQ cho phép định nghĩa các luồng lưu lượng ưu tiên như thế nào trong
mạng? Ta có thể cấu hình các độ ưu tiên lưu lượng, có thể định nghĩa một loạt
các bộ lọc trên cơ sở các đặc điểm của gói qua router để sắp xếp các lưu lượng
trong các hàng đợi. Hàng đợi có độ ưu tiên cao nhất sẽ được phục vụ trước cho
đến khi hàng đợi rỗng, sau đó các hàng đợi có độ ưu tiên thấp hơn sẽ được phục
vụ lần lượt. Câu hỏi đặt ra là PQ làm việc như thế nào? Trong quá trình truyền
dẫn,các hàng đợi có độ ưu tiên cao được đối xử ưu tiên hơn các hàng đợi có
mức ưu tiên thấp hơn, hay nói cách khác các, lưu lượng quan trọng sẽ được gán
các mức ưu tiên cao và lưu lượng có mức ưu tiên cao nhất được truyền trước,
còn lại các lưu lượng ít quan trọng hơn. Các gói được phân loại dựa trên các
tiêu chuẩn phân loại của người sử dụng,và được đặt ở một trong số các hàng đợi
đầu ra với các độ ưu tiên: độ ưu tiên cao, trung bình, bình thường (không được

ưu tiên), ưu tiên thấp. Các gói không được ấn định độ ưu tiên sẽ được đưa tới
các hàng đợi bình thường. Khi các gói được gửi tới giao diện đầu ra, các hàng
đợi ưu tiên tại giao diện đó được quét các gói theo thứ tự độ ưu tiên giảm dần.
Hàng đợi có độ ưu tiên cao nhất được quét đầu tiên, sau đó đến các hàng đợi
trung bình và tiếp tục các hàng đợi có độ ưu tiên khác. Gói đứng đầu hàng đợi
có độ ưu tiên cao nhất được truyền đầu tiên. Thủ tục này được lặp lại mỗi khi
có một gói được truyền. Chiều dài lớn nhất của hàng đợi được định nghĩa theo
chiều dài giới hạn. Khi một hàng đợi dài hơn chiều dài hàng đợi giới hạn thì các
gói đến sau sẽ bị loại bỏ.
Cơ chế hàng đợi đầu ra ưu tiên có thể được sử dụng để quản lý lưu lượng từ tất
cả các giao thức trong mạng. PQ cung cấp cách đối sử ưu tiên cho các luồng lưu
lượng có độ ưu tiên cao, chắc chắn rằng các luồng lưu lượng then chốt khi qua
các kết nối WAN sẽ đạt được độ ưu tiên cao.
Các gói được phân loại như thế nào trong kĩ thuật PQ
Danh sách ưu tiên là một tập các luật lệ mô tả các gói sẽ được ấn định các độ ưu
tiên như thế nào trong các hàng đợi. Ngoài ra nó cũng có thể mô tả độ ưu tiên
mặc định hoặc giới hạn kích thước hàng đợi của các hàng đợi ưu tiên.
Các gói được phân loại theo:
- Loại giao thức hoặc giao thức con
- Giao diện đầu vào
- Kích thước các gói tin
- Các Fragment
- Danh sách truy nhập
Tất cả các lưu lượng dùng để quản lý và điều khiển mạng đều được ấn định độ
ưu tiên cao nhất để trong trường hớp có tắc nghẽn xảy ra thì chúng được ưu tiên
truyền trước. Các lưu lượng không được ấn định mức ưu tiên nào thì được đưa
vào các hàng đợi bình thường.
PQ cung cấp thời gian đáp ứng nhanh hơn so với các kĩ thuật hàng đợi khác.
Mặc dù có thể ấn định các độ ưu tiên cho các hàng đợi tại bất kì giao diện đầu
nào nhưmg nó thường được sử dụng cho các lưu lượng có băng thông thấp.

Để giải quyết vấn đề các hàng đợi có độ ưu tiên thấp không được xử lý khi có
quá nhiều hàng đợi có độ ưu tiên cao thì ta có thể sử dụng các kiểu hàng đợi
khác: hàng đợi cân bằng có trọng số (WFQ) hay hàng đợi cân bằng (FQ), đơn
giản hơn ta có thể sử dụng cơ chế định dạng lưu lượng hay CAR để giới hạn tốc
độ của lưu lượng có độ ưu tiên cao hơn. PQ sử dụng định cấu hình tĩnh do đó
nó không thể thích ứng với các mạng thay đổi. Cơ chế xếp hàng ưu tiên là cơ
chế đơn giản, có thể cung cấp các lớp dịch vụ phân biệt và cần ít nhất hai hàng
đợi FIFO. Lấy một ví dụ sau: cho các hàng đợi FIFO và ta sẽ ấn định các mức
ưu tiên khác nhau cho chúng: mức ưu tiên cao, mức ưu tiên trung bình, mức ưu
tiên bình thường, mức ưu tiên thấp.
II. Xây dựng kiểu cấu trúc dữ liệu truyền thống hàng đợi (Queue) trong
Scheme
Việc thực hiện hàng đợi trong Scheme phức tạp hơn so với thực hiện của ngăn
xếp. Một lần nữa, giữ cho các phần tử của hàng đợi trong một danh sách. Tuy
nhiên, các hoạt động của queue nhanh hơn nếu đại diện cho một hàng đợi rỗng
bởi một danh sách có chứa một yếu tố là một `` giả tiêu đề ", và lưu trữ các yếu
tố hàng đợi thực tế sau tiêu đề này, theo thứ tự cũ nhất lưu giữ trước. Các tiêu
đề giả không được chèn vào bởi enqueue và không thể được gỡ bỏ bởi các
dequeue.
Các thao tác trên Hàng đợi được thực hiện việc truy cập vào danh sách thông
qua 3 trường khác nhau là: fore, aft, và size. Trường fore chứa cấu trúc toàn bộ
danh sách, bắt đầu bởi các “giả tiêu đề”, (cdr ) là yếu tố thực tế của Hàng đợi, và
(cadr fore) là yếu tố thực sự đầu tiên của hàng đợi(Khi nó không phải là rỗng). Các trường aft là một danh
sách phần tử nó có chứa phần tử cuối cùng của hàng đợi, ngoại trừ khi hàng đợi rỗng, trong trường. Trường
Size theo dõi số lượng các phần tử trong hàng đợi, không bao gồm các tiêu đề giả
Sơ đồ khối và con trỏ sau cho thấy một hàng đợi với các ký hiệu a, b, và c theo
thứ tự :
Sau đây là quá trình xây dựng cấu trúc Hàng đợi trong Scheme:
;, Make-Queue: xây dựng và trả về một hàng đợi
; Givens:

; Không
; Kết quả:
; QUEUE, một thủ tục
; Điều kiện đầu:
; Không có.
; Quá trình thực hiện:
; (1) QUEUE ban đầu rỗng.
; (2) Khi QUEUE được gọi với các đối số: EMPTY?, nó báo cáo
; Cho dù đó là sản phẩm nào.
; (3) Khi QUEUE đã được gọi với đối số đầu tiên: Enqueue! và
; Một đối số thứ hai, ta gọi NEW-VALUE, NEW-VALUE ở phía sau, và
; Tất cả các giá trị khác trong hàng đợi ở phía trước của nó, theo thứ tự
thời gian.
; (4) Khi QUEUE đã được gọi với đối số: Dequeue!,
; Trả về giá trị lâu nhất enqueued, ở phía trước, và
; Giữ lại tất cả các giá trị khác, theo thứ tự thời gian.
; (5) Khi QUEUE được gọi với các đối số: FRONT, nó trả về
; Giá trị ở phía trước (có sẵn cho dequeuing).
; (6) Khi QUEUE được gọi với đối số: SIZE, nó trả về
; Số các giá trị trong hàng đợi.
; (7) Đây là một lỗi để cung cấp cho QUEUE bất kỳ đối số khác khi gọi nó.
; (8) Khi QUEUE được gọi với đối số đầu tiên: EMPTY?,:DEQUEUE!,
;: FRONT, hoặc :SIZE, đó là một lỗi để cho nó hai hoặc nhiều đối số.
; (9) Khi QUEUE được gọi với đối số đầu tiên: :ENQUEUE!, nó là một
; Lỗi để cho nó chỉ có một đối số hoặc ba hoặc nhiều hơn.
(define make-queue
(lambda ()
(let* ((fore (list 'dummy-header))
(aft fore)
(size 0))

(lambda (message . arguments)
(cond ((eq? message ':empty?)
(if (null? arguments)
(zero? size)
(error "queue:empty?: no arguments are required")))
((eq? message ':enqueue!)
(cond ((null? arguments)
(error "queue:enqueue!: an argument is required"))
((not (null? (cdr arguments)))
(error "queue:enqueue!: no more than one argument is
required"))
(else
; Attach a new cons cell behind the current aft
; element.
(set-cdr! aft (list (car arguments)))
; Advance AFT so that it is once more a list
; containing only the last element.
(set! aft (cdr aft))
; Increment SIZE.
(set! size (+ size 1)))))
((eq? message ':dequeue!)
(cond ((not (null? arguments))
(error "queue:dequeue!: no argument is required"))
((null? (cdr fore))
(error "queue:dequeue!: the queue is empty"))
(else
; Recover the first element of the queue (not
; including the dummy header).
(let ((removed (cadr fore)))
; Splice out the element to be dequeued.

(set-cdr! fore (cddr fore))
; If we just spliced out the last element of the
; queue, reset AFT so that it holds the dummy
; header.
(if (null? (cdr fore))
(set! aft fore))
; Decrement SIZE.
(set! size (- size 1))
removed))))
((eq? message ':front)
(cond ((not (null? arguments))
(error "queue:front: no argument is required"))
((null? (cdr fore))
(error "queue:front: the queue is empty"))
(else
(cadr fore))))
((eq? message ':size)
(if (null? arguments)
size
(error "queue:size: no argument is required")))
(else (error 'queue "unrecognized message")))))))
III. Ví dụ minh hoạ vận dụng hàng đợi để quản lý nhập/xuất một sản phẩm
FIFO hàng đợi là một cấu trúc dữ liệu tiêu chuẩn có nhiều công dụng .
Việc thực hiện Hàng đợi với một mảng hai con trỏ được gọi là phía trước
và phía sau.
Một sản phẩm được thêm vào hàng đợi bằng cách đẩy con trỏ ở phía sau
một vòng tròn và đặt các đối tượng mới tại điểm đó. Một sản phẩm được
lấy ra khỏi hàng đợi bằng cách loại bỏ các sản phẩm được trỏ đến bởi con
trỏ phía trước và sau đó đẩy con trỏ một lần nữa trong vòng tròn.
Trong Scheme và Lisp, FIFOs thường được thực hiện với danh sách bằng cách

thao tác cdr của yếu tố cuối cùng để đẩy một sản phẩm mới vào hàng đợi. Điều
này là nhanh chóng và trực tiếp nhưng vẫn phải duy trì con trỏ phía sau.
Dưới đây là một vận dụng hàng đợi để quản lý nhập/xuất một sản phẩm đó
trong Scheme.
1:;;
2:;; Queue obect
3:;;
4:
5:; 'push x: y x vào phía sau c a hàng iđẩ ủ đợ
6:; 'pop: lo i b các u c a hàng i và g i l iạ ỏ đầ ủ đợ ử ạ
7:; 'peek: tr l i ng i ng u c a hàng iả ạ ườ đứ đầ ủ đợ
8:; 'show: hi n th n i dung c a hàng iể ị ộ ủ đợ
9:; 'fb: hi n th các ph n m t tr c và sau c a hàng i ( g ể ị ầ ặ ướ ủ đợ để ỡ
l i)ỗ
10: (define make-queue
11: (lambda ()
12: (let ((front '()) (back '()))
13: (lambda (cmd . data)
14: (define exchange
15: (lambda ()
16: (set! front (reverse back))
17: (set! back '())))
18: (case cmd
19: ((push) (push (car data) back))
20: ((pop) (or (pop front)
21: (begin
22: (exchange)
23: (pop front))))
24: ((peek) (unless (pair? front)
25: (exchange))

26: (car front))
27: ((show) (format #t "~s\n" (append front (reverse
back))))
28: ((fb) (format #t "front: ~s, back: ~s\n" front
back))
29: (else (error "Illegal cmd to queue object"
cmd)))))))
Có thể đẩy và bật các Sản phẩm vào và ra hàng đợi bằng cách gửi nó đẩy hoặc
lệnh pop.
(define q (make-queue))
(q 'push "Hello, World!")
(q 'pop) → "Hello, World!"
Phần II: BÀI TOÁN LẬP TRÌNH HÀM
Đề tài: Hãy viết chương trình Scheme mô phỏng các hàm đệ quy thực hiện
các phép chia (Division) và tìm giá trị căn bậc hai (Square Root)
Bài làm:
(define (sqrt-iter guess x)
02.(if (good-enough? guess x)
03.guess
04.(sqrt-iter (improve guess x)
05.x)))
06.
07.(define (improve guess x)
08.(average guess (/ x guess)))
09.
10.(define (average x y)
11.(/ (+ x y) 2))
12.
13.(define (good-enough? guess x)
14.(< (abs (- (square guess) x))

15.0.001))
16.
17.(define (sqrt x)
18.(sqrt-iter 1.0 x))
19.
20.(sqrt 10)
(define (sqrt x)
(define (square x) (* x x))
(define (average x y) (/ (+ x y) 2)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))
1. ; divides two numbers until cutoff is reached
2. (define (divide n d cutoff)
3. (let ((step 10)) ; any value >1 will work
4. (define (loop i p sum)
5. (letrec ((sp (expt step p))
6. (dp (* d sp))
7. (q (quotient i dp))
8. (r (remainder i dp))
9. (new-sum (+ sum (* q sp))))
10. (cond
11. ((= r 0)
12. new-sum)

13. ((< (abs r) cutoff)
14. (exact->inexact new-sum))
15. (else
16. (loop r (- p 1) new-sum)))))
17. (loop n 0 0)))
18.
19. ; divides two numbers until cutoff is reached without
quotient/remainder
20. (define (divide-2 n d cutoff)
21. (let ((step 10)) ; any value >1 will work
22. (define (loop i ud p sum)
23. (cond
24. ((= i 0)
25. sum)
26. ((< (abs i) cutoff)
27. (exact->inexact sum))
28. (else
29. (letrec ((sp (expt step p))
30. (dp (* ud sp))
31. (new-sum (+ sum sp)))
32. (cond
33. ((< dp i)
34. (loop (- i dp) ud p new-sum))
35. (else
36. (loop i ud (- p 1) sum)))))))
37. (if (< n 0)
38. (if (< d 0)
39. (loop (- 0 n) (- 0 d) 0 0)
40. (- 0 (loop (- 0 n) d 0 0)))
41. (if (< d 0)

42. (- 0 (loop n (- 0 d) 0 0))
43. (loop n d 0 0)))))
Phần III: BÀI TOÁN LẬP TRÌNH PROLOG
Đề tài: Cài đặt thuật toán tìm kiếm sâu (Depth-First-Search) trong lý thuyết
trí tuệ nhân tạo (Artificial Intelligence). Cho ví dụ minh hoạ chạy demo.
I. Thuật toán tìm kiếm chiều sâu.
1. Sơ lược thuật toán tìm kiếm chiều sâu:
Trong tìm kiếm theo chiều sâu, tại trạng thái (đỉnh) hiện hành, ta chọn
một trạng thái kế tiếp (trong tập các trạng thái có thể biến đổi thành từ trạng thái
hiện tại) làm trạng thái hiện hành cho đến lúc trạng thái hiện hành là trạng thái
đích. Trong trường hợp tại trạng thái hiện hành, ta không thể biến đổi thành
trạng thái kế tiếp thì ta sẽ quay lui (back-tracking) lại trạng thái trước trạng thái
hiện hành (trạng thái biến đổi thành trạng thái hiện hành) để chọn đường khác.
Nếu ở trạng thái trước này mà cũng không thể biến đổi được nữa thì ta quay lui
lại trạng thái trước nữa và cứ thế. Nếu đã quay lui đến trạng thái khởi đầu mà
vẫn thất bại thì kết luận là không có lời giải. Hình ảnh sau minh họa hoạt động
của tìm kiếm theo chiều sâu.
Hình 1: Hình ảnh của tìm kiếm chiều sâu. Nó chỉ lưu ý "mở rộng" trạng thái
được chọn mà không "mở rộng" các trạng thái khác (nút màu trắng trong hình
vẽ).
2. Kỹ thuật tìm kiếm chiều sâu:
Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp tục cho
đến khi hoặc đến ngõ cụt hoặc đến đích. Tại mỗi nút có luật trong tài, chẳng
hạn, “đi theo nút cực trái”, hướng dẫn việc tìm. Nếu không đi tiếp được, gọi là
đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hướng khác,
chẳng hạn, đến nút “sát nút cực trái”. Hành động này gọi là quay lui.
Thuật toán tìm kiếm theo chiều sâu được hình dung như việc khảo sát một cây
bắt đầu từ gốc đi theo mọi cành có thể được, khi gặp cành cụt thì quay lại xét
cành chưa đi qua.
- Ở bước tổng quát, giả sử đang xét đỉnh i, khi đó các đỉnh kề với i có các

trường hợp:
+ Nếu tồn tại đỉnh j kề i chưa được xét thì xét đỉnh này (nó trở thành đỉnh đã
xét) và bắt đầu từ đó tiếp tục quá trình tìm kiếm với đỉnh này
+ Nếu với mọi đỉnh kề với i đều đã được xét thì i coi như duyệt xong và quay
trở lại tìm kiếm từ đỉnh mà từ đó ta đi đến được i.

Ví dụ:
Cho cây như hình vẽ:
Đỉnh đầu: A
Đỉnh Đích: J
J
HGFE
DCB
A
Các bước chi tiết thực hiện giải thuật:
Lần Lặp L = Ø U U € T V L
0 A
1 False A False B,C,D D,C,B
2 False D False H H,C,B
3 False H False Ø C,B
4 False C False G G,B
5 False G False J J,B
6 False J True
Ta có J ∈ DICH ⇒ Thành Công. Xây dựng đường đi. A → C → G → J.
Kết quả đường đi trên cây
là:
J
HGFE
DCB
A

3. Cài đặt chương trình
domains
d = integer
STATE = state(D STRING,D STRING)
PATH = STATE*
predicates
nondeterm stack(STATE,PATH,PATH)
nondeterm member(STATE,PATH)
nondeterm member_set(STATE,PATH)
nondeterm member_stack(STATE,PATH)
add_if_not_in_set(STATE,PATH,PATH)
nondeterm path(PATH,PATH,PATH,STATE)
empty_set(PATH)
empty_stack(PATH)
nondeterm go(STATE,STATE)
nondeterm move(STATE,STATE)
nondeterm reverse_print_stack(PATH)
nondeterm test
clauses
path(Open_stack,_,_,_):-
empty_stack(Open_stack),
write("No solution found with these rules").
path(Open_stack,_,Path_stack,Goalstate):-
stack(Top,_,Open_stack),Top = Goalstate,
write("A solution found :\n"),
reverse_print_stack(Path_stack).
path(Open_stack,Closed_set,Path_stack,Goalstate):-
stack(Top,Res_open_stack,Open_stack),
move(Top,Next_state),
not(member_stack(Next_state,Open_stack)),

not(member_set(Next_state,Closed_set)),
stack(Next_state,Res_open_stack,New_open_stack),
stack(Next_state,Path_stack,New_path_stack),
add_if_not_in_set(Next_state,Closed_set,New_closed_set),
path(New_open_stack,New_closed_set,New_path_stack,Goalstate),!.
go(Start,Goalstate):-
empty_stack(Open),
empty_stack(Path),
empty_set(Closed),
stack(Start,Open,Open_stack),
stack(Start,Path,Path_stack),
add_if_not_in_set(Start,Closed,Closed_set),
path(Open_stack,Closed_set,Path_stack,Goalstate).
move(state(X,Y),state(New_x,New_y)):- X < 4,New_x = 4, New_y = Y.
move(state(X,Y),state(New_x,New_y)):- Y < 3, New_x = X, New_y = 3.
move(state(X,Y),state(New_x,New_y)):- X > 0, New_x = 0, New_y = Y.
move(state(X,Y),state(New_x,New_y)):- Y >0, New_x = X, New_y = 0.
move(state(X,Y),state(New_x,New_y)):- X + Y >= 4,
Y > 0,New_x = 4, New_y = Y - (4 - X).
move(state(X,Y),state(New_x,New_y)):- X + Y >= 3,
X > 0,New_x = X - (3 - Y),New_y = 3.
move(state(X,Y),state(New_x,New_y)):- X + Y < 0,
Y > 0,New_x = X + Y, New_y = 0.
move(state(X,Y),state(New_x,New_y)):- X + Y < 3,
X > 0,New_x = 0,New_y = X + Y.

empty_stack([]).
empty_set([]).
stack(Top,Stack,[Top|Stack]).
reverse_print_stack(S):-

empty_stack(S).
reverse_print_stack(S):-
stack(E,Res,S),
reverse_print_stack(Res),write(E),nl.
member(X,[X|_]):-
!.
member(X,[_|L]):-
member(X,L).
member_stack(Element,Stack):- member(Element,Stack).
member_set(S,L):- member(S,L).
add_if_not_in_set(X,S,S):-
member(X,S),!.
add_if_not_in_set(X,S,[X|S]).
test:-
go(state(0,0),state(2,_)).
goal
test.
4. Ưu và nhược điểm của phương pháp tìm kiếm chiều sâu:
* Ưu điểm:
- Nếu bài toán có lời giải, phương pháp tìm kiếm sâu bảo đảm tìm ra lời giải.
- Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài lòng khi các
câu hỏi tập trung vào vấn đề chính.
- Do cách tìm của kỹ thuật này, nếu lời giải ở rất sâu, kỹ thuật tìm sâu sẽ tiết
kiệm thời gian.
* Nhược điểm:
- Tìm sâu khai thác không gian bài toán để tìm lời giải theo thuật toán đơn giản
một cách cứng nhắc. Trong quá trình tìm nó không có thông tin nào hổ trợ để
phát hiện lời giải. Nếu chọn nút ban đầu không thích hợp có thể không dẫn đến
đích của bài toán.
- Không phù hợp với không gian bài toán lớn, kỹ thuật tìm kiếm sâu có thể

không đến lời giải trong khoảng thời gian vừa phải.
II. Thuật toán tìm kiếm chiều rộng.
1. Sơ lược thuật toán tìm kiếm chiều rộng:
Ngược lại với tìm kiếm theo kiểu chiều sâu, tìm kiếm chiều rộng mang
hình ảnh của vết dầu loang. Từ trạng thái ban đầu, ta xây dựng tập hợp S bao
gồm các trạng thái kế tiếp (mà từ trạng thái ban đầu có thể biến đổi thành). Sau
đó, ứng với mỗi trạng thái Tk trong tập S, ta xây dựng tập Sk bao gồm các trạng
thái kế tiếp của Tk

rồi lần lượt bổ sung các Sk vào S. Quá trình này cứ lặp lại
cho đến lúc S có chứa trạng thái kết thúc hoặc S không thay đổi sau khi đã bổ
sung tất cả Sk.
Hình 2: Hình ảnh của tìm kiếm chiều rộng. Tại một bước, mọi trạng thái
đều được mở rộng, không bỏ sót trạng thái nào.
2. Kỹ thuật tìm kiếm chiều rộng:
Kỹ thuật tìm kiếm rông là tìm kiếm trên tất cả các nút của một mức trong
không gian bài toán trước khi chuyển sang các nút của mức tiếp theo.
Kỹ thuật tìm kiếm rộng bắt đầu từ mức thứ nhất của không gian bài toán, theo
hướng dẫn của luật trọng tài, chẳng hạn “đi từ trái sang phải”. Nếu không thấy
lời giải tại mức này, nó chuyển xuống mức sau để tiếp tục … đến khi định vị
được lời giải nếu có.
Ví dụ:
Cho cây như hình vẽ:
Đỉnh đầu: A
Đỉnh đích: K
Các bước chi tiết thực hiện giải thuật:
Lần Lặp L = Ø
U U € T V L
0 A
1 False A False B,C,D B,C,D

2 False B False E,F C,D,E,F
3 False C False G D,E,F,G
4 False D False H,I E,F,G,H,I
5 False E False J,K F,G,H,I,J,K
6 False F False Ø G,H,I,J,K
7 False G False L H,I,J,K,L
8 False H False Ø I,J,K,L
F H
LKJ
E
D
CB
A
G
P
I
9 False I False P J,K,L,P
10 False J False Ø K,L,P
11 False K True
Ta có K
∈
Đích
⇒
Thành công. Xây dựng đường đi: A
→
B
→
E
→
K

Kết quả đường đi trên cây:
3. Cài đặt chương trình
Domains
d = integer
STATE = state(D STRING,D STRING)
PATH = STATE*
predicates
nondeterm member(STATE,PATH)
nondeterm member_set(STATE,PATH)
add_if_not_in_set(STATE,PATH,PATH)
nondeterm path(PATH,PATH,STATE)
empty_set(PATH)
empty_queue(PATH)
nondeterm go(STATE,STATE)
nondeterm move(STATE,STATE)
nondeterm dequeue(STATE,PATH,PATH)
LKJ
E
D
CB
A
G
P
I
F
H
nondeterm add_to_queue(STATE,PATH,PATH)
nondeterm moves(STATE,PATH,PATH,STATE)
get_children(STATE,PATH,PATH,PATH)
nondeterm union(PATH,PATH,PATH)

nondeterm append(PATH,PATH,PATH)
nondeterm add_list_to_queue(PATH,PATH,PATH)
nondeterm member_queue(STATE,PATH)
nondeterm printsolution(STATE,PATH)
nondeterm reverse_writelist(PATH)
nondeterm test
clauses
go(Start,Goalstate):-
empty_queue(Empty_open_queue),
add_to_queue(Start,Empty_open_queue,Open_queue),
empty_set(Closed_set),
path(Open_queue,Closed_set,Goalstate).
path(Open_queue,_,_):-
empty_queue(Open_queue),
write("Graph search, no solution found.").
path(Open_queue,Closed_set,Goalstate):-
dequeue(State,Open_queue,_),
State = Goalstate,
write("Solution path is : "),
printsolution(State,Closed_set),nl,reverse_writelist(Closed_se
t).
ath(Open_queue,Closed_set,Goalstate):-
dequeue(State,Open_queue,Res_open_queue),
get_children(State,Res_open_queue,Closed_set,Children),
add_list_to_queue(Children,Res_open_queue,New_open_queue),
union([State,_],Closed_set,New_closed_set),
path(New_open_queue,New_closed_set,Goalstate),!.
get_children(State,Res_open_queue,Closed_set,Children):-
findall(Child,moves(State,Res_open_queue,
Closed_set,Child),Children).

moves(State,Res_open_queue,Closed_set,Next):-
move(State,Next),
not(member_queue(Next,Res_open_queue)),
not(member_set(Next,Closed_set)).
printsolution(State,_):-
write(State),nl.
printsolution(State,Closed_set):-
member_set(State,Closed_set),
printsolution(State,Closed_set),
write(State),nl.