bởi admin lúc Mon, Apr 16 '18 11:38 AM | Lần xem 497 | Lần tải 26
  • Download images Giải thuật (Đại học Cần Thơ)
  • Download images Giải thuật (Đại học Cần Thơ)
  • Download images Giải thuật (Đại học Cần Thơ)
  • Download images Giải thuật (Đại học Cần Thơ)
  • Download images Giải thuật (Đại học Cần Thơ)

Th.s. NGUYỄN VĂN LINH
GIẢI
THUẬT
Được biên soạn trong khuôn khổ dự án ASVIET002CNTT
”Tăng cường hiệu quả đào tạo và năng lực tự đào tạo của sinh viên
khoa Công nghệ Thông tin - Đại học Cần thơ”
ĐẠI HỌC CẦN THƠ - 12/2003
LỜI NÓI ÐẦU
N. Wirth, một nhà khoa học máy tính nổi tiếng, tác giả của ngôn
ngữ lập trình Pascal, đã đặt tên cho một cuốn sách của ông là
“Cấu trúc dữ liệu + Giải thuật =
Chương trình”.
Ðiều đó nói lên tầm quan trọng của giải thuật trong lập trình nói
iêng và trong khoa học máy tính nói chung. Vì lẽ đó giải thuật, với tư
cách là một môn học, cần phải được sinh viên chuyên ngành tin học
nghiên cứu một cách có hệ thống.
Môn
học
“Giải
thuật”
được

trí
sau
môn
“Cấu
trúc
dữ
liệu”
trong chương trình đào tạo kỹ sư tin học nhằm giới thiệu cho sinh viên
những
kiến
thức

ản
nhất,
những
kỹ
thuật
chủ
yếu
nhất
của
việc
PHÂN TÍCH và THIẾT KẾ giải thuật. Các kỹ thuật được trình bày ở
đây đã được các nhà khoa học tin học tổng kết và vận dụng trong cài đặt
các chương trình. Việc nắm vững các kỹ thuật đó sẽ rất bổ ích cho sinh
viên khi phải giải quyết một vấn đề thực tế.
Giáo trình này được hình thành trên cơ sở tham khảo cuốn sách
“Data
Structure
and
Algorithms”
của
A.V
Aho,
những
kinh
nghiệm
giảng dạy của bản thân và các bạn đồng nghiệp.
Mặc dù đã có nhiều cố gắng trong quá trình biên soạn nhưng chắc
chắn còn nhiều thiếu sót, rất mong nhận được sự đóng góp của quý bạn
đọc.
Cần thơ, ngày 8 tháng 12 năm 2003
Nguyễn Văn Linh
Giải thuật
Mục lục
MỤC LỤC
PHẦN TỔNG QUAN .................................................i
Chương 1:
KĨ THUẬT PHÂN TÍCH GIẢI THUẬT ..........................1
1.1
TỔNG QUAN................................................................................................................... 1
1.2
SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT....................................................... 2
1.3
THỜI GIAN THỰC HIỆN CỦA GIẢI THUẬT.............................................................. 2
1.4
TỶ SUẤT TĂNG VÀ ÐỘ PHỨC TẠP CỦA GIẢI THUẬT .......................................... 3
1.5
CÁCH TÍNH ÐỘ PHỨC TẠP.......................................................................................... 4
1.6
PHÂN TÍCH CÁC CHƯƠNG TRÌNH ÐỆ QUY............................................................. 7
1.7
TỔNG KẾT CHƯƠNG 1............................................................................................... 16
BÀI TẬP CHƯƠNG 1................................................................................................................. 16
Chương 2:
SẮP XẾP
.............................................18
2.1
TỔNG QUAN................................................................................................................. 18
2.2
BÀI TOÁN SẮP XẾP..................................................................................................... 19
2.3
CÁC PHƯƠNG PHÁP SẮP XẾP ÐƠN GIẢN.............................................................. 20
2.4
QUICKSORT ................................................................................................................. 25
2.5
HEAPSORT.................................................................................................................... 31
2.6
BINSORT....................................................................................................................... 39
2.7
TỔNG KẾT CHƯƠNG 2............................................................................................... 44
BÀI TẬP CHƯƠNG 2................................................................................................................. 44
Chương 3:
KĨ THUẬT THIẾT KẾ GIẢI THUẬT ...........................45
3.1
TỔNG QUAN................................................................................................................. 45
3.2
KĨ THUẬT CHIA ÐỂ TRỊ............................................................................................. 45
3.3
KĨ THUẬT “THAM ĂN”............................................................................................... 50
3.4
QUY HOẠCH ÐỘNG.................................................................................................... 56
3.5
KĨ THUẬT QUAY LUI ................................................................................................. 63
3.6
KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG........................................................................ 78
3.7
TỔNG KẾT CHƯƠNG 3............................................................................................... 82
BÀI TẬP CHƯƠNG 3................................................................................................................. 82
Chương 4:
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ
NGOÀI .........85
4.1
TỔNG QUAN................................................................................................................. 85
4.2
MÔ HÌNH XỬ LÝ NGOÀI............................................................................................ 85
4.3
ÐÁNH GIÁ CÁC GIẢI THUẬT XỬ LÝ NGOÀI......................................................... 86
4.4
SẮP XẾP NGOÀI........................................................................................................... 87
4.5
LƯU TRỮ THÔNG TIN TRONG TẬP TIN................................................................. 93
4.6
TỔNG KẾT CHƯƠNG 4............................................................................................. 103
BÀI TẬP CHƯƠNG 4............................................................................................................... 104
bởi admin lúc Mon, Apr 16 '18 11:38 AM

Giải thuật đóng vai trò quan trọng trong lập trình. Giáo trình này được biên soạn nhằm cung cấp một số kiến thức giải thuật trong lập trình, bao gồm kỹ năng phân tích bài toán, kỹ thuật thiết kế giải thuật, các cấu trúc dữ liệu thông dụng và một số thuật toán sắp xếp.
.pdf 773888.pdf
Kích thước: 1.38 mb
Lần tải: 0 lần
Download