Giải thuật ứng dụng trong kinh doanh: Cài đặt bằng ngôn ngữ lập trình Python (Tài liệu tham khảo) / Nguyễn Văn Thọ đcb

``

LỜI GIỚI THIỆU

Giải thuật ứng dụng trong kinh doanh (Tiếng Anh: Applied Algorithms in

Business) là môn học thuộc chương trình đào tạo các ngành: Hệ thống thông tin quản

lý, Tài chính-ngân hàng, Quản trị kinh doanh...của trường Đại học Ngân hàng

TPHCM. Với mong muốn có một tài liệu cho các em sinh viên tham khảo trong quá

trình học tập, nhóm tác giả đã tâm huyết biên soạn tài liệu Giải thuật ứng dụng trong

kinh doanh. Tài liệu này thể hiện được tính ưu việt hơn so với các tài liệu hiện có trên

thị trường: (1)Nội dung được viết rất cô đọng và sát với đề cương môn học thuộc

chương trình đào tạo đã được Ban giám hiệu phê duyệt; (2)Cấu trúc được trình bày

theo hướng tóm tắt lý thuyết, cho ví dụ minh họa được cài đặt bằng ngôn ngữ Python,

hướng dẫn giải bài tập từng bước. Với mỗi ví dụ và bài tập đều in kết quả sau khi

chạy chương trình để sinh viên dễ dàng nắm bắt và thực hành. Cuối mỗi chương có

trình bày tóm tắt nội dung chương cùng với các câu hỏi ôn tập và các bài tập thực hành

có hướng dẫn chi tiết. Ngoài ra tài liệu còn có các bài tập đề nghị sinh viên tự giải

nhằm giúp các em nâng cao khả năng tự học; (3)Các bài tập tình huống và bài tập tự

rèn luyện ở mỗi chương được chọn lọc kỹ, đó là những bài toán rất thực tế và phổ

biến trong lĩnh vực kinh doanh mà các doanh nghiệp đang áp dụng; (4)Đính kèm theo

sách này là các tập tin mã nguồn của chương trình đã được viết hoàn chỉnh bằng ngôn

ngữ lập trình Python nhằm giúp người học dễ dàng theo dõi. Độc giả có thể tải các

tập tin mã nguồn tại địa chỉ sau:

https://www.mediafire.com/file/6f4c0leiokbaqaj/Code_GTUD.rar/file

Nội dung tài liệu được chia thành 7 chương:

Chương 1: Tổng quan

Chương 2: Đệ quy

Chương 3: Danh sách

Chương 4: Cây

Chương 5: Đồ thị

Chương 6: Sắp xếp và tìm kiếm

Chương 7: Bảng băm

Nhóm biên soạn chân thành cảm ơn sự hỗ trợ của lãnh đạo trường Đại học

Ngân hàng Tp. Hồ Chí Minh, cảm ơn các nhà khoa học đã có những đóng góp ý kiến

quý báu để nhóm hoàn thành tài liệu này.

Mặc dù nhóm tác giả đã cố gắng rất nhiều nhưng không tránh khỏi những thiếu

sót, rất mong nhận được ý kiến đóng góp quý báu của Quý độc giả, Quý thầy cô và

các em sinh viên để lần ấn bản sau được hoàn chỉnh hơn.

Mọi thắc mắc và đóng góp về tài liệu, Quý độc giả vui lòng gửi mail theo địa

chỉ: [email protected] hoặc [email protected]

Xin chân thành cảm ơn

Nhóm biên soạn

i

MỤC LỤC

CHƯƠNG 1. TỔNG QUAN................................................................................................1

Một số định nghĩa về cấu trúc dữ liệu và giải thuật ....................................................2

Định nghĩa giải thuật............................................................................................2

Giải thuật ứng dụng trong kinh doanh .................................................................2

Định nghĩa cấu trúc dữ liệu và cấu trúc lưu trữ....................................................2

Vai trò của tổ chức dữ liệu và mối quan hệ giữa cấu trúc dữ liệu và giải thuật...3

Các kiểu dữ liệu cơ bản ...............................................................................................4

Các kiểu dữ liệu có cấu trúc ........................................................................................6

Phân tích và thiết kế giải thuật ....................................................................................7

Phương pháp chia để trị (divide- and-conquer) ...................................................8

Phương pháp quy hoạch động............................................................................10

Phương pháp quay lui (backtracking) ................................................................10

Ký hiệu BigO (Big-Oh Notation)..............................................................................10

Giới thiệu về ngôn ngữ lập trình Python ...................................................................15

Một số câu hỏi và bài tập có lời giải..........................................................................16

Một số câu hỏi và bài tập tự rèn luyện ......................................................................17

CHƯƠNG 2. ĐỆ QUY.......................................................................................................18

Giới thiệu đệ quy .......................................................................................................19

Khái niệm:..........................................................................................................19

Giải thuật đệ quy và hàm đệ quy...............................................................................19

Cơ chế hoạt động của giải thuật đệ quy .............................................................20

Thiết kế giải thuật đệ quy...................................................................................21

Ưu điểm và nhược điểm của giải thuật đệ quy...................................................22

Phân loại giải thuật đệ quy ........................................................................................22

Đệ quy tuyến tính ...............................................................................................22

Đệ quy nhị phân .................................................................................................23

Đệ quy phi tuyến ................................................................................................24

Đệ quy tương hỗ.................................................................................................24

Giải một số bài toán phổ biến bằng giải thuật đệ quy ...............................................25

Bài toán tháp Hà Nội [9]. ...................................................................................25

Bài toán tìm kiếm với đệ quy nhị phân ..............................................................27

Bài toán chia thưởng ..........................................................................................29

Một số câu hỏi và bài tập có lời giải..........................................................................30

Ứng dụng giải thuật đệ quy để giải bài toán trong kinh doanh .................................34

Sử dụng đệ quy để tính tiền lãi gửi tiết kiệm ngân hàng....................................34

ii

Sử dụng đệ quy để tính tiền thưởng ...................................................................35

Sử dụng đệ quy để tính tiền lãi phải trả hàng tháng khi vay ngân hàng.............36

Một số câu hỏi và bài tập tự rèn luyện.......................................................................37

CHƯƠNG 3. DANH SÁCH ..............................................................................................38

Giới thiệu danh sách ..................................................................................................39

Danh sách đặc ............................................................................................................39

Định nghĩa ..........................................................................................................39

Ưu và nhược điểm của danh sách đặc ................................................................40

Khai báo danh sách đặc ......................................................................................40

Các thao tác trên danh sách đặc..........................................................................40

Danh sách liên kết......................................................................................................45

Định nghĩa và phân loại......................................................................................45

Danh sách liên kết đơn .......................................................................................45

Danh sách liên kết đôi ........................................................................................53

Danh sách liên kết vòng .....................................................................................58

Danh sách đa liên kết..........................................................................................58

Ứng dụng của danh sách liên kết........................................................................59

Ngăn xếp....................................................................................................................59

Định nghĩa ..........................................................................................................59

Khai báo cấu trúc ngăn xếp ................................................................................60

Các thao tác trên ngăn xếp .................................................................................61

Ứng dụng của ngăn xếp......................................................................................63

Hàng đợi ....................................................................................................................64

Định nghĩa ..........................................................................................................64

Khai báo cấu trúc của hàng đợi ..........................................................................66

Các thao tác trên hàng đợi..................................................................................67

Ứng dụng của hàng đợi ......................................................................................69

Một số câu hỏi, bài tập có lời giải..............................................................................71

Ứng dụng danh sách để giải một số bài toán trong kinh doanh.................................72

Chương trình quản lý sinh viên bằng cấu trúc danh sách đặc ............................72

Chương trình quản lý sách sử dụng cấu trúc danh sách liên kết đơn .................77

Chương trình quản lý bệnh nhân sử dụng cấu trúc hàng đợi .............................80

Chương trình đảo ngược danh sách các cuốn sách sử dụng ngăn xếp ...............84

Một số câu hỏi và bài tập tự rèn luyện.......................................................................86

CHƯƠNG 4. CÂY..............................................................................................................88

Các khái niệm cơ bản.................................................................................................89

Khái niệm cây.....................................................................................................89

iii

Các thuật ngữ .....................................................................................................89

Cách biểu diễn cây.....................................................................................................90

Cây nhị phân..............................................................................................................91

Một số tính chất của cây nhị phân......................................................................91

Duyệt cây nhị phân.............................................................................................92

Cây nhị phân tìm kiếm ..............................................................................................95

Định nghĩa..........................................................................................................95

Khai báo cấu trúc cây nhị phân tìm kiếm...........................................................96

Các thao tác trên cây nhị phân tìm kiếm............................................................96

Duyệt cây ...........................................................................................................96

Cây nhiều nhánh ......................................................................................................101

Giới thiệu cây TRIE ................................................................................................102

Cấu trúc dữ liệu Heap..............................................................................................103

Minh họa thao tác nhập xuất cây nhị phân tìm kiếm...............................................104

Một số câu hỏi và bài tập có lời giải........................................................................107

Ứng dụng cấu trúc cây để giải bài toán trong kinh doanh.....................................108

Chương trình quản lý sinh viên bằng cấu trúc cây.........................................108

Chương trình quản lý hàng hóa bằng cấu trúc cây.........................................112

Chương trình quản lý sách bằng cấu trúc cây ................................................115

Một số câu hỏi và bài tập tự rèn luyện ..................................................................118

CHƯƠNG 5. ĐỒ THỊ......................................................................................................119

Định nghĩa về đồ thị ................................................................................................120

Đường đi ..........................................................................................................122

Chu trình...........................................................................................................122

Bậc của đỉnh ............................................................................................................122

Đồ thị liên thông......................................................................................................123

Đồ thị có trọng số ....................................................................................................123

Biểu diễn đồ thị .......................................................................................................123

Biểu diễn đồ thị bằng ma trận kề .....................................................................123

Biễu diễn đồ thị bằng danh sách kề..................................................................124

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

Duyệt theo chiều sâu - DFS .............................................................................125

Duyệt theo chiều rộng - BFS............................................................................127

Cây khung và cây khung nhỏ nhất ..........................................................................128

Cây khung ........................................................................................................128

Cây khung nhỏ nhất .........................................................................................129

Thuật toán Prim tìm cây khung nhỏ nhất.........................................................130

iv

Thuật toán Krusal tìm cây khung nhỏ nhất ......................................................133

Thuật toán Dijkstra tìm đường đi ngắn nhất............................................................138

Mô tả thuật toán................................................................................................138

Chương trình minh họa giải thuật Dijkstra.......................................................141

Ứng dụng của đồ thị ................................................................................................142

Một số câu hỏi và bài tập có lời giải......................................................................143

Ứng dụng đồ thị để giải bài toán trong kinh doanh ...............................................148

Quản lý đường bay .........................................................................................148

Bài toán vận chuyển hàng hóa........................................................................149

Mạng lưới giao thông .....................................................................................152

Lắp đặt hệ thống điện văn phòng ...................................................................152

Một số câu hỏi và bài tập tự rèn luyện...................................................................153

CHƯƠNG 6. SẮP XẾP VÀ TÌM KIẾM........................................................................155

Sắp xếp.....................................................................................................................156

Giới thiệu về bài toán sắp xếp ..........................................................................156

Giải thuật Bubble Sort......................................................................................156

Giải thuật Selection Sort...................................................................................163

Giải thuật Insertion Sort ...................................................................................165

Giải thuật Interchange Sort...............................................................................168

Giải thuật Merge Sort.......................................................................................172

Giải thuật Quick Sort........................................................................................174

Giải thuật Heap Sort.........................................................................................177

Giải thuật Radix Sort........................................................................................183

Giải thuật Topo Sort.......................................................................................185

Tìm kiếm..................................................................................................................188

Khái niệm và vai trò của tìm kiếm dữ liệu .......................................................188

Phân loại...........................................................................................................189

Một số câu hỏi, bài tập có lời giải............................................................................193

Ứng dụng giải thuật sắp xếp và tìm kiếm để giải bài toán trong kinh doanh ..........194

Chương trình quản lý sinh viên sử dụng giải thuật InterChange Sort..............194

Chương trình quản lý hóa đơn bán hàng ..........................................................196

Chương trình quản lý hàng hóa ........................................................................200

Tính thời gian tối thiểu để vận chuyển hàng ....................................................202

Một số câu hỏi và bài tập tự rèn luyện.....................................................................203

CHƯƠNG 7. BẢNG BĂM ..............................................................................................204

Tìm hiểu về bảng băm .............................................................................................205

Kỹ thuật băm ....................................................................................................205

v

Hàm băm..........................................................................................................206

Các kỹ thuật xử lý va chạm .....................................................................................208

Kỹ thuật tạo dây chuyền (separated chaining).................................................208

Kỹ thuật định địa chỉ mở (open addressing) ....................................................208

Ứng dụng bảng băm ................................................................................................210

Một số câu hỏi và bài tập có lời giải........................................................................211

Một số câu hỏi và bài tập tự rèn luyện ....................................................................214

TÀI LIỆU THAM KHẢO...................................................................................................1

PHỤ LỤC..............................................................................................................................2

vi

DANH MỤC HÌNH ẢNH

Hình 1. 1- Từ bài toán thực tế đến chương trình trên máy tính .............................................3

Hình 1. 2-Mối quan hệ giữa cấu trúc dữ liệu và giải thuật ....................................................4

Hình 1. 3- Quá trình từ bài toán thực tế đến chương trình.....................................................8

Hình 1. 4- Đồ thị mô tả độ phức tạp của giải thuật..............................................................11

Hình 1. 5- Độ phức tạp giải thuật qua các hàm....................................................................14

Hình 2. 1- Cơ chế hoạt động của giải thuật đệ quy..............................................................20

Hình 2. 2 - Cơ chế hoạt động của bài toán tính giai thừa ....................................................21

Hình 2. 3 – Mô tả đệ quy tương hỗ .....................................................................................24

Hình 2. 4- Minh họa đệ quy bài toán Tháp Hà Nội .............................................................25

Hình 2. 5- Quá trình thực hiện bài toán Tháp Hà Nội .........................................................26

Hình 2. 6- Cơ chế tìm kiếm với đệ quy nhị phân.................................................................27

Hình 2. 7- Cấu trúc của mảng một chiều .............................................................................40

Hình 3. 1-Cấu trúc danh sách liên kết với con trỏ pHead và pTail......................................45

Hình 3. 2- Danh sách liên kết đơn........................................................................................45

Hình 3.3-Thêm một phần tử vào vị trí ở đầu danh sách ......................................................47

Hình 3. 4-Thêm một phần tử vào vị trí ở cuối danh sách ....................................................47

Hình 3. 5- Thêm một phần tử vào sau nút q ........................................................................48

Hình 3. 6-Xóa một phần tử ở vị trí đầu danh sách...............................................................48

Hình 3. 7- Xóa một phần tử đứng sau nút q.........................................................................49

Hình 3. 8- Xóa một phần tử có giá trị X ..............................................................................49

Hình 3. 9-Danh sách liên kết đôi..........................................................................................53

Hình 3. 10-Thêm một phần tử vào danh sách liên kết đôi...................................................54

Hình 3. 11-Thêm một phần tử vào vị trí cuối danh sách .....................................................54

Hình 3. 12-Thêm một phần tử sau phần tử q .......................................................................55

Hình 3. 13-Xóa một phần tử ở vị trí đầu danh sách trong danh sách liên kết đôi................56

Hình 3. 14-Xóa một phần tử đứng sau vị trí phần tử q trong danh sách liên kết đôi...........56

Hình 3. 15-Xóa một phần tử có giá trị X trong danh sách liên kết đôi................................57

Hình 3. 16-Danh sách liên kết vòng là một danh sách liên kết đơn.....................................58

Hình 3. 17-Danh sách liên kết vòng là một danh sách liên kết đôi......................................58

Hình 3. 18-Cấu trúc của danh sách đa liên kết.....................................................................58

Hình 3. 19- Minh họa về một ngăn xếp ...............................................................................59

Hình 3. 20-Hai tác vụ Push và Pop của ngăn xếp................................................................59

Hình 3. 21-Các tác vụ trong ngăn xếp .................................................................................60

Hình 3. 22-Quá trình chuyển đổi cơ số thập phân sang nhị phân ........................................64

vii

Hình 3. 23- Minh họa thao tác Push và Pop trong bài toán đổi cơ số..................................64

Hình 3. 24- Minh họa cơ chế của hàng đợi qua việc xếp hàng tính tiền tại quầy...............65

Hình 3. 25-Cấu trúc của hàng đợi........................................................................................65

Hình 3. 26-Minh họa thao tác thêm phần tử vào hàng đợi ..................................................65

Hình 3. 27-Minh họa tác vụ xóa phần tử trong hàng đợi.....................................................66

Hình 3. 28-Quá trình cài đặt giải thuật Radix Sort bằng hàng đợi ......................................70

Hình 4. 1- Sơ đồ tổ chức của một công ty ...........................................................................89

Hình 4. 2-Cây biểu diễn biểu thức.......................................................................................89

Hình 4. 3-Mức của cây.........................................................................................................90

Hình 4. 4-Biểu diễn cây bằng đồ thị ....................................................................................90

Hình 4. 5-Biểu diễn cây bằng giản đồ .................................................................................90

Hình 4. 6-Biểu diễn cây bằng phương pháp indentatio .......................................................91

Hình 4. 7- Cấu trúc của một cây nhị phân ...........................................................................91

Hình 4. 8-Cây nhị phân hoàn chỉnh .....................................................................................92

Hình 4. 9-Cây nhị phân đầy đủ ............................................................................................92

Hình 4. 10-Quá trình duyệt cây theo thứ tự trước của biểu thức toán học ..........................93

Hình 4. 11-Kết quả duyệt cây nhị phân theo thứ tự trước với các số nguyên .....................93

Hình 4. 12-Quá trình duyệt cây theo thứ tự giữa của biểu thức toán học............................93

Hình 4. 13-Kết quả duyệt cây nhị phân theo thứ tự giữa với các số nguyên.......................94

Hình 4. 14-Kết quả duyệt cây nhị phân theo thứ tự sau của biểu thức toán học .................94

Hình 4. 15-Kết quả duyệt cây nhị phân theo thứ tự sau với các số nguyên.........................94

Hình 4. 16- Chuyển cây tổng quát thành cây nhị phân........................................................95

Hình 4. 17-Cấu trúc cây nhị phân tìm kiếm.........................................................................95

Hình 4. 18-Xóa phần tử là nút lá..........................................................................................99

Hình 4. 19-Xóa phần tử có một nút con ............................................................................100

Hình 4. 20-Nút nhỏ nhất của cây con bên phải..................................................................100

Hình 4. 21-Nút nhỏ nhất của cây con bên trái ...................................................................100

Hình 4. 22-Cây Trie biểu diễn cho tập S gồm các chuỗi {bear, bell, bid, bull, buy, hear,

see, sell, stock, stop}..........................................................................................................102

Hình 4. 23-Cấu trúc dữ liệu Heap......................................................................................103

Hình 5. 1-Cấu trúc của đồ thị.............................................................................................120

Hình 5. 2- Một số ví dụ về đồ thi trong thực tế .................................................................121

Hình 5. 3- Đường đi...........................................................................................................122

Hình 5. 4-Đường đi đơn.....................................................................................................122

Hình 5. 5-Chu trình............................................................................................................122

Hình 5. 6-Bậc của đỉnh ......................................................................................................122

Hình 5. 7-Đồ thị liên thông và đồ thị không liên thông.....................................................123

viii

Hình 5. 8-Đồ thị có trọng số ..............................................................................................123

Hình 5. 9-Đồ thị không có trọng số ...................................................................................123

Hình 5. 10-Biểu diễn đồ thị bằng ma trận kề .....................................................................123

Hình 5. 11-Biểu diễn đồ thị bằng danh sách kề .................................................................124

Hình 5. 12-Biểu diễn đồ thị không có trọng số với danh sách kề ......................................125

Hình 5. 13-Kết quả duyệt đồ thị theo DFS ........................................................................126

Hình 5. 14-Duyệt đồ thị theo chiều rộng ...........................................................................127

Hình 5. 15-Đồ thị gồm cá đỉnh ..........................................................................................128

Hình 5. 16-Đồ thị và cây khung.........................................................................................129

Hình 5. 17-Cây khung nhỏ nhất.........................................................................................129

Hình 6. 1- Minh họa giải thuật Bubble Sort.......................................................................157

Hình 6. 2- Minh họa giải thuật Insertion Sort....................................................................166

Hình 6. 3-Quá trình sắp xếp của giải thuật Merge Sort .....................................................173

Hình 6. 4-Cấu trúc Heap ....................................................................................................178

Hình 6. 5-Quá trình sắp xếp của giải thuật Radix Sort ......................................................184

Hình 6. 6-Minh họa giải thuật Topo Sort...........................................................................185

Hình 6. 7- Minh họa phương pháp tìm kiếm nhị phân với cuốn danh bạ điện thoại .........191

Hình 7. 1-Mô tả kỹ thuật băm............................................................................................205

Hình 7. 2-Hàm băm với phép chia dư cho 10 ....................................................................206

Hình 7. 3-HIện tượng va chạm ..........................................................................................208

Hình 7. 4-Kỹ thuật tạo dây chuyền ....................................................................................208

ix

DANH MỤC BẢNG BIỂU

Bảng 1-Các kiểu dữ liệu định sẳn trong Python ........................................................5

Bảng 2- Kiểu dữ liệu và ví dụ minh họa cho kiểu dữ liệu .........................................6

Bảng 3- Mô tả giải thuật duyệt theo chiều sâu (DFS)............................................126

Bảng 4- Quá trình duyệt theo chiều rộng (BFS)....................................................128

Bảng 5-Mô tả quá trình thăm dò tuyến tính ...........................................................209

Bảng 6-Mô tả quá trình chèn giá trị khóa theo phương pháp băm kép..................210

x

THUẬT NGỮ SỬ DỤNG

Tiếng Anh Tiếng Việt

Array Mảng

ASCII (American Standard Code for

Information Interchange) Chuẩn mã trao đổi thông tin Hoa Kỳ

Algorithm Giải thuật

BigO O lớn

BFS (Breadth First Search) Tìm kiếm theo chiều rộng

Circular linked list Danh sách liên kết vòng

Child Con

Class Lớp

Connected Liên thông (đồ thị)

CPU (Central Processing Unit) Bộ xử lý trung tâm

Data structure Cấu trúc dữ liệu

DB Indexing (Data Base Indexing) Chỉ mục cơ sở dữ liệu

Devide-and-conquer Chia để trị

Double linked list Danh sách liên kết kép

DFS (Depth First Search) Tìm kiếm theo chiều sâu

Dynamic programming Quy hoạch động

Edge list Danh sách cạnh

Input Đầu vào (dữ liệu)

Inorder traversal Duyệt theo thứ tự giữa

Graph Đồ thị

Hash table Bảng băm

Heap Đống (trong cấu trúc dữ liệu)

Output Đầu ra (dữ liệu)

LIFO (Last In First Out) Vào sau ra trước

FIFO (First In First Out) Vào trước ra trước

Linked list Danh sách liên kết

Minimum spanning tree Cây khung nhỏ nhất

Front Đầu (hàng đợi)

Matrix Ma trận

Multi-linked lists Danh sách đa liên kết

Node Nút

None Không (không có)

NULL Không tồn tại, không xác định

Parent Cha

Postorder traversal Duyệt theo thứ tự sau

Preorder Duyệt theo trung tự

Prefix Tiền tố

Queue Hàng đợi

Quick sort Sắp xếp nhanh

Selection sort Sắp xếp chọn lựa

Single linked list Danh sách liên kết đơn

xi

Stack Ngăn xếp

Rear Đuôi (hàng đợi)

Recursive Đệ quy

Root Gốc (của cây)

Top Đỉnh (stack)

Top-Down Design Thiết kế từ trên - xuống

Tree Cây