Đồ án tốt nghiệp xây dựng thời khóa biểu C

Xây dựng phần mềm tạo thời khóa biểu tự động bằng C Hệ thống dữ liệu đảm bảo việc nhập dữ liệu, quản lý, khai thác dữ liệu được nhanh chóng, thuận tiện. Phần mềm giúp sắp xếp thời khóa biểu nhanh chóng giảm thiểu tối đa thời gian và công sức so với việc thực hiện thủ công. Phần mềm có giao diện hài hòa, dễ nhìn, linh hoạt, năng động hơn và đáp ứng được yêu cầu ngày càng cao trong công tác quản lý giáo viên, lớp học, môn học… và nhu cầu của người sử dụng.

LỜI CẢM ƠN

Em xin chân thành cảm ơn Khoa Công nghệ thông tin, trường Đại học QuangTrung đã tạo điều kiện cho em thực hiện Báo cáo đồ án tốt nghiệp này

Xin gửi lời cảm ơn chân thành đến thầy giáo TS Nguyễn Văn Phong đã tận tình

hướng dẫn, chỉ bảo trong suốt thời gian thực hiện đồ án tốt nghiệp Trong quá trìnhthực hiện chuyên đề em đã học hỏi được nhiều kiến thức bổ ích và kinh nghiệm quýbáu làm nền tảng cho quá trình làm việc và nghiên cứu sau này

Em cũng xin chân thành cảm ơn quý Thầy Cô trong Khoa Công nghệ thông tin

đã tận tình giảng dạy, trang bị cho em những kiến thức quan trọng trong những nămhọc vừa qua

Xin chân thành cảm ơn các bạn, đặc biệt là các thành viên trong lớp C10TH đãcùng đoàn kết, ủng hộ, giúp đỡ em trong suốt thời gian học tập tại trường và thời gianthực hiện đề tài này

Mặc dù đã cố gắng hoàn chỉnh chuyên đề trong phạm vi và khả năng cho phépnhưng chắc chắn sẽ không tránh khỏi những thiếu sót, rất mong nhận được sự thôngcảm, góp ý của quý Thầy Cô và các bạn

Em xin chân thành cảm ơn!

Quy Nhơn, ngày 14 tháng 4 năm 2017

Sinh viên thực hiện

Nguyễn Thành Vũ

LỜI CAM ĐOAN

Tôi xin cam đoan:

1 Những nội dung trong báo cáo này là do tôi thực hiện dưới sự hướng dẫn

trực tiếp của thầy giáo TS Nguyễn Văn Phong.

2 Mọi tham khảo dùng trong báo cáo này đều được trích dẫn rõ ràng tên tác giả, tên công trình, thời gian, địa điểm công bố.

3 Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, chúng tôi xin chịu hoàn toàn trách nhiệm.

Sinh viên

Nguyễn Thành Vũ

MỤC LỤC

LỜI CAM ĐOAN ii

MỤC LỤC iii

DANH MỤC HÌNH ẢNH vi

I Lý do chọn đề tài 1

II Mục đích nghiên cứu của đề tài1

III Đối tượng và phạm vi nghiên cứu 1

IV Phương pháp nghiên cứu 1

CHƯƠNG 1 TỔNG QUAN VỀ ĐỀ TÀI 3

1.1 Mô tả về đề tài 3

1.2 Một số mẫu thời khóa biểu THCS 3

1.3 Bảng tổng hợp danh sách môn học THCS 5

1.4 Quy trình tạo thời khóa biểu tại trường 5

CHƯƠNG 2 CƠ SỞ LÝ THUYẾT 7 2.1 Khái quát phân tích hệ thống hướng đối tượng 7

2.1.1 Giới thiệu UML 7

2.1.2 Mục đích của UML 7

2.1.3 Công dụng của UML 7

2.1.4 Các đặc trưng và khả năng của UML 8

2.1.5 Mô hình khái niệm của UML 9

2.1.6 Kiến trúc hệ thống trong UML 17

2.2 Ngôn ngữ lập trình C# 18

2.2.1 Giới thiệu về ngôn ngữ lập trình C# 18

2.2.2 Console application 20

2.2.3 Windows Form Application 23

2.3 Giải thuật di truyền và Tính tiến hóa 28

2.3.1 Giải thuật di truyền 28

2.3.2 Tính tiến hóa 36

CHƯƠNG 3 PHÂN TÍCH THIẾT KẾ HỆ THỐNG 45

3.1 Áp dụng thuật toán vào bài toán thời khóa biểu 45

3.1.1 Thuật toán tiến hóa cải tiến 45

3.1.2 Nhiễm sắc thể của bài toán Thời khóa biểu 45

3.1.3 Quần thể 47

3.1.4 Thuật toán sắp xếp thời khóa biểu 47

3.1.5 Khởi tạo quần thể 48

3.1.6 Thuật toán đánh giá độ thích nghi 50

3.1.7 Thuật toán Đột biến, Biến dị, Lai ghép Nhiễm sắc thể 52

3.1.8 Thuật toán khử vi phạm số buổi học của một môn học 52

3.1.9 Thuật toán khử vi phạm trùng lịch giáo viên 53

3.1.10 Thuật toán cân bằng số lượng tiết dạy của giáo viên 55

3.1.11 Các bước lập lịch 56

3.2 Đặc tả chức năng của hệ thống 57

3.2.1 Yêu cầu chức năng 57

3.2.2 Yêu cầu phi chức năng 57

4.2.1 Cấu hình Server 67

4.2.2 Trang dữ liệu phòng học 68

4.2.3 Trang dữ liệu lớp học 68

4.2.4 Trang dữ liệu giáo viên 69

4.2.5 Trang dữ liệu môn học 69

4.2.6 Trang phân thời khóa biểu 70

4.2.7 Trang thời khóa biểu lớp học 70

4.2.8 Trang lịch dạy giáo viên71

4.2.9 Trang quản lý người dùng 71

KẾT LUẬN 71

DANH MỤC TÀI LIỆU THAM KHẢO 73

DANH MỤC HÌNH ẢNH

Hình 1: Thời khóa biểu lớp 6 3

Hình 2: Thời khóa biểu lớp 7 4

Hình 3: Thời khóa biểu lớp 8 4

Hình 4: Thời khóa biểu lớp 9 4

Hình 5: Quy trình tạo TKB tại trường THCS 6

Hình 6: Lớp 10

Hình 7: Giao diện 10

Hình 8: Cộng tác 10

Hình 9: Ca sử dụng 11

Hình 10: Lớp hoạt động 11

Hình 11: Thành phần 11

Hình 12: Nút 11

Hình 13: Thông điệp 12

Hình 14: Máy trạng thái 12

Hình 15: Gói 12

Hình 16: Biểu đồ CA 14

Hình 17: Biểu đồ cộng tác 15

Hình 18: Thuật toán chương trình 30

Hình 19: Bánh xe xổ số 32

Hình 20: Sơ đồ hình cây của hai NST v1 và v2 40

Hình 21: Hướng tiếp cận của GA cổ điển 43

Hình 22: Hướng tiếp cận của Eps 43

Hình 23: Cấu trúc Nhiễm sắc thể (thời khóa biểu) và các đoạn Gens 46

Hình 24: Cấu trúc hoàn chỉnh của một Nhiễm sắc thể 47

Hình 25: Quần thể 47

Hình 26: Thuật toán phân thời khóa biểu 48

Hình 27: Thuật toán tạo quần thể 49

Hình 28: Quy định tiết được học trong thời khóa biểu 50

Hình 29: Thuật toán tính độ thích nghi của Quần thể và NST 51

Hình 30: Thuật toán khử vi phạm số buổi NST 53

Hình 31: Thuật toán khử vi phạm trùng lịch giáo viên 54

Hình 32: Thời khóa biểu trùng lịch dạy môn Toán 54

Hình 33: Thời khóa biểu sau khi hoán đổi hai môn Toán và Ngoại ngữ 55

Hình 34: Thuật toán lập lịch 56

Hình 35: Biểu đồ Ca sử dụng 58

Hình 36: Biểu đồ lớp 59

Hình 37: Biểu đồ hoạt động 61

Hình 38: Biểu đồ tuần tự 63

Hình 39: Mô hình cơ sở dữ liệu 64

Hình 40: Giao diện trang chính 67

Hình 41: Giao diện cấu hình Server 67

Hình 42: Giao diện dữ liệu phòng học 68

Hình 43: Giao diện dữ liệu lớp học 68

Hình 44: Giao diện dữ liệu giáo viên 69

Hình 45: Giao diện dữ liệu môn học 69

Hình 46: Giao diện phân thời khóa biểu 70

Hình 47: Giao diện thời khóa biểu lớp học 70

Hình 48: Giao diện lịch dạy giáo viên 71

Hình 49: Giao diện quản lý người dùng 71

DANH MỤC BẢNG

Bảng 1: Từ khóa của ngôn ngữ C# 19

Bảng 2: Kiểu dữ liệu trong C# 20

Bảng 3: Ký tự đặc biệt trong C# 20

Bảng 4: Thao tác trên chuỗi 22

Bảng 5: Các thuộc tính của Lable 24

Bảng 6: Các thuộc tính của TextBox 24

Bảng 7: Các thuộc tính của Button 25

Bảng 8: Các thuộc tính của CheckBox 25

Bảng 9: Các thuộc tính của Combobox 26

Bảng 10: Các thuộc tính của ListBox 26

Bảng 11: Các thuộc tính giống nhau của Control 27

Bảng 12: Các sự kiện của Control 28

Bảng 13: Mô tả các hoạt động của bánh xe xổ số 33

Bảng 14: Bảng giáo viên 64

Bảng 15: Bảng môn học 65

Bảng 16: Bảng lớp học 65

Bảng 17: Bảng phòng học 66

Bảng 18: Bảng thời khóa biểu 66

DANH MỤC TỪ VIẾT TẮT

MỞ ĐẦU

I Lý do chọn đề tài

Để đáp ứng mục tiêu cơ bản của các dự án Tin học hoá quản lý trong ngành giáodục, là tạo được một hệ thống thông tin thống nhất phục vụ điều hành và quản lý, tôichọn hướng phát triển phần mềm sắp xếp thời khóa biểu cho các trường THCS nhằm:

1 Tổ chức quản lý, lưu trữ dữ liệu trên hệ thống máy vi tính làm tăng tính antoàn

2 Sắp xếp, tính toán, phân chia TKB một cách nhanh chóng và chính xác

3 Chi phí đào tạo sử dụng phần mềm không tốn kém

4 Tổ chức quản lý, phù hợp với các ứng dụng triển khai trên diện rộng

5 Bảo trì, phát triển phần mềm, phát triển ứng dụng và tích hợp với các ứngdụng khác một cách dễ dàng nhanh chóng; nên việc mở rộng ít tốn kém nhất

II Mục đích nghiên cứu của đề tài

Hệ thống dữ liệu đảm bảo việc nhập dữ liệu, quản lý, khai thác dữ liệu đượcnhanh chóng, thuận tiện

Phần mềm giúp sắp xếp thời khóa biểu nhanh chóng giảm thiểu tối đa thời gian

và công sức so với việc thực hiện thủ công

Phần mềm có giao diện hài hòa, dễ nhìn, linh hoạt, năng động hơn và đáp ứngđược yêu cầu ngày càng cao trong công tác quản lý giáo viên, lớp học, môn học… vànhu cầu của người sử dụng

III Đối tượng và phạm vi nghiên cứu

Cán bộ giáo viên được phân công phụ trách lập TKB tại các trường THCS, cácthành phần tin học liên quan đến công tác quản lý bao gồm: hệ quản trị cơ sở dữ liệu,phân tích thiết kế hệ thống, ngôn ngữ lập trình C#

IV Phương pháp nghiên cứu

- Nghiên cứu thực tế: Tìm hiểu thực tế quy trình phân công TKB, thu thập dữ liệu

từ cán bộ giáo viên phụ trách phân công TKB, để có được cái nhìn khái quát và hiệuchỉnh cho phù hợp với hệ thống

- Nghiên cứu tài liệu: Tài liệu hệ quản trị cơ sở dữ liệu SQL Server và ngôn ngữlập trình C#

Cấu trúc đề tài bao gồm những phần sau:

Chương 1: Tổng quan về đề tài

Chương 2: Cơ sở lý thuyết

Chương 3: Phân tích thiết kế hệ thống

Chương 4: Xây dựng ứng dụng

CHƯƠNG 1 TỔNG QUAN VỀ ĐỀ TÀI

1.1 Mô tả về đề tài

Đề tài sẽ thực hiện nghiên cứu các tài liệu thu thập được từ trường THCS, khảosát thực tế trường học để hiểu được các nội dung trong việc quản lý dữ liệu, phần chiathời khóa biểu Phân tích khả năng có tiết kiệm được thời gian, công sức trước và saukhi đề tài có khả năng áp dụng vào thực tế hay không

Đầu tiên, dữ liệu thô sẽ được cấu trúc hóa để lưu trữ trong hệ quản trị CSDL SQLServer, dữ liệu được thiết kế có những thành phần ngoài khảo sát nhưng sẽ giúp việcquản lý và lập trình dễ dàng hơn

Sau đó, sẽ thiết kế giao diện để quản lý những danh mục dữ liệu đã thiết kế trước

đó Dữ liệu lưu trữ thời khóa biểu sẽ được thiết kế riêng theo thuật toán

Thuật toán sẽ thiết kế sau đó thử nghiệm và chỉnh sửa, cuối cùng sẽ có mộtthuật toán được đưa vào sử dụng Thuật toán sẽ lấy dữ liệu từ danh mục dữ liệu trước

đó, thực thi theo các bước để tạo thành một thời khóa biểu học và dạy ban đầu Người

sử dụng có được thời khóa biểu sẽ có thể sửa lại thủ công theo ý muốn của mình màkhông phụ thuộc vào thuật toán Lúc này khả năng chồng chéo về lịch dạy và học cóthể xảy ra

Để giải quyết vấn đề trùng lịch học hoặc dạy, tôi sẽ thiết kế một thuật toán khácchỉ nhằm một mục đích là cảnh báo những chồng chéo đang xảy ra cho người sử dụng

dễ thiết lập và quản lý

1.2 Một số mẫu thời khóa biểu THCS

- Thời khóa biểu lớp 6:

Hình 1: Thời khóa biểu lớp 6

- Thời khóa biểu lớp 7:

Hình 2: Thời khóa biểu lớp 7

- Thời khóa biểu lớp 8:

Hình 3: Thời khóa biểu lớp 8

- Thời khóa biểu lớp 9:

Hình 4: Thời khóa biểu lớp 9

1.3 Bảng tổng hợp danh sách môn học THCS

Danh sách môn học THCS

Bảng 1: Danh sách môn học THCS

1.4 Quy trình tạo thời khóa biểu tại trường

- Bước 1: thu thập thông tin về lớp, phòng học, môn học và giáo viên

- Bước 2: Cán bộ giáo viên được phân công tiến hành lập TKB bằng phươngpháp thủ công; chọn lớp, phòng học, môn học và giáo viên hợp lý

- Bước 3: trình TKB vừa lập cho Hiệu trưởng kiểm tra nếu sai Sót thì điềuchỉnh lại cho hợp lý rồi ban hành TKB cho học sinh và giáo viên

Hình 5: Quy trình tạo TKB tại trường THCS

Chọn Lớp

CBGV phân công TKB

Chọn Phòng Học Chọn Môn Chọn Giáo Viên

Thời Khóa Biểu

Hiệu trưởng kiểm tra TKB

Kết Thúc

Bắt đầu

N

YQuá TrìnhTạo Thời Khóa Biểu

CHƯƠNG 2 CƠ SỞ LÝ THUYẾT

2.1 Khái quát phân tích hệ thống hướng đối tượng

2.1.1 Giới thiệu UML

UML là ngôn ngữ mô hình hợp nhất, nó được hiểu như một ngôn ngữ thống nhấtnhững xu hướng và hình thái của cuộc cách mạng tri thức trong lĩnh vực CNTT Nó làmột phương tiện giúp cho các tổ chức có thể nhận thức một cách tốt nhất lợi thế cạnhtranh thông qua việc nắm bắt, truyền đạt, trao đổi và nâng cao tri thức trong lĩnh vựccông nghệ phần mềm Chính xác hơn UML là ngôn ngữ mô hình hoá chuẩn để thiết kếphần mềm hướng đối tượng, được dùng để đặc tả, trực quan hoá, xây dựng và làm tàiliệu cho các hệ thống phần mềm UML là ngôn ngữ đồ hoạ với các tập quy tắc và ngữnghĩa Các quy tắc và ngữ nghĩa của một mô hình được thể hiện bằng tiếng anh gọi làNgôn ngữ rang buộc đối tượng (OCL – Object Constraint Language) OCL là ngônngữ đặc tả sử dụng logic đơn giản để đặc tả các đặc tính của hệ thống

- Hỗ trợ khả năng sử dụng lại và kế thừa ở phạm vi rộng để xây dựng những hệthống phức tạp và nhạy cảm như: hệ thống tự động, hệ thống thời gian thực

- Tạo ra ngôn ngữ mô hình hoá sử dụng được cho cả người và máy tính

2.1.3 Công dụng của UML

- UML là ngôn ngữ chuẩn để viết kế hoạch chi tiết phần mềm

- Vạch ra cho hệ thống những chức năng chính của nó sử dụng các mô hình tìnhhuống sử dụng và các tác nhân

- Minh hoạ các use case bằng các biểu đồ tương tác (interaction diagram)

- Mô tả cấu trúc tĩnh của một hệ thống sử dụng các biểu đồ lớp (class diagram).

- Mô hình hoá trạng thái của đối tượng bằng các biểu đồ chuyển tiếp trạng thái

- Minh hoạ cấu trúc thi hành vật lý bằng các biểu đồ thành phần và triển khai Mởrộng chức năng bằng các mầu cung cấp sẵn (stereotype)

2.1.4 Các đặc trưng và khả năng của UML

 UML là ngôn ngữ mô hình đồ hoạ:

Ngôn ngữ cung cấp bảng từ vựng và tập các quy tắc để kết hợp các từ trong bảng

từ vựng để giao tiếp Ngôn ngữ mô hình là ngôn ngữ có từ vựng và quy tắc tập trung vào các biểu diễn về mặt vật lý và khái niệm của hệ thống UML là ngôn ngữ chuẩn công nghiệp để lập kế hoạch chi tiết phần mềm

Ngôn ngữ phải cho phép biểu diễn nhiều khung nhìn (views) khác nhau của kiếntrúc hệ thống trong suốt quá trình phát triển phần mềm Từ vựng và quy tắc ngôn ngữUML cho ta cách thức xây dựng mô hình và đọc mô hình, nhưng không cho biết môhình nào cần phải được lập và khi nào lập chúng mà phải dựa vào quy trình phát triểnphần mềm Các biểu diễn mô hình trong UML là các biểu diễn bằng đồ hoạ

 UML là ngôn ngữ đặc tả có cấu trúc:

Đặc tả là xây dựng mô hình chính xác, rõ rang, không nhập nhằng, hoàn thiện vàđầy đủ những điểm mấu chốt của vấn đề UML hướng tới đặc tả thiết kế, phân tích vàquyết định cài đặt trong quá trình phát triển và triển khai hệ thống phần mềm

 UML là ngôn ngữ trực quan:

Bằng hệ thống các kí hiệu đồ hoạ và các biểu đồ với các chú giải đi kèm, UML cho ta hình dung được hệ thống đang cần xây dựng từ nhiều góc độ khác nhau

 UML là ngôn ngữ làm tài liệu

UML hướng tới làm tài liệu kiến trúc hệ thống và các chi tiết của nó UML cho khả năng biểu diễn yêu cầu, thử nghiệm, mô hình hoá các hoạt động lập kế hoạch và quản lý sản phẩm

Thông qua UC biểu đồ trường hợp sử dụng, tác nhân để biết giới hạn và cácchức năng chính của hệ thống

Trong UML UC (User case) được miêu tả bằng biểu đồ logic Sử dụng biểu đồ

UC, tác nhân (Actor) có thể chia dự án thành các dự án nhỏ có thể quản lý được Nhìnvào biểu đồ đó và các tài liệu mô tả, người phân tích có thể biết hệ thống có khả nănglàm gì

Biểu diễn cấu trúc tĩnh của hệ thống bằng biểu đồ lớp Sử dụng biểu đồ trình tự

và cộng tác để thấy được trình tự và logic toàn bộ hệ thống và các thông báo giữa cácđối tượng

Mô hình hoá các hành vi đối tượng bằng biểu đồ chuyển trạng thái

Phản ánh kiến trúc cài đặt vật lý bằng biểu đồ thành phần và biểu đồ triển khai

Mở rộng chức năng bằng stereotypes

2.1.5 Mô hình khái niệm của UML

Để hiểu, đọc được UML và tạo ra một số mô hình cơ bản ta phải hình dung được

mô hình khái niệm của ngôn ngữ Muốn vậy đòi hỏi chúng ta phải nắm được ba vấn đềchính bao gồm:

 Các khối cơ bản để xây dựng mô hình

 Các quy tắc liên kết

 Các cơ chế chung được sử dụng cho ngôn ngữ

 Các khối cơ bản xây dựng mô hình

Các khối để hình thành mô hình UML gồm ba loại:

 Phần tử cấu trúc

Phần tử cấu trúc là các danh từ trong mô hình UML, là bộ phận tĩnh của mô hình

để biểu diễn các thành phần khái niệm hay vật lý

 Giao diện (Interface)

Giao diện là một tập hợp các thao tác đặc tả một dịch vụ của lớp hay thành phần.Giao diện mô tả hành vi thấy được từ ngoài của thành phần Biểu diễn toàn bộ hay mộtphần hành vi của lớp và được gắn vào lớp hay thành phần thực hiện

Hình 7: Giao diện

 Cộng tác (Collaboration)

Sự cộng tác định nghĩa một tương tác và một bộ các nguyên tắc và các phần tửkhác làm việc cùng nhau để tạo ra một hành vi cộng tác lớn hơn tổng hành vi của cácphần tử

Hình 8: Cộng tác

Tên lớpThuộc tínhThao tácOpen()Close()

Tên cộng tác

 Ca sử dụng (Use case)

Ca sử dụng là tậo hợp các hành động mà hệ thống thực hiện để đạt được một kếtquả cho tác nhân cụ thể

Hình 9: Ca sử dụng

Lớp hoạt động (Active class)

Lớp tích cực là lớp có đối tượng làm chủ một hay nhiều tiến trình hay luồng Đốitượng của nó biểu diễn các thành phần có hành vi đang tương tranh với các thành phầnkhác Kí pháp đồ hoạ giống lớp thông thường nhưng biên hình chữ nhật tô đậm

Tên Use case

File.cpp

Máy chủ

 Máy trạng thái (State machine)

Máy trạng thái là hành vi chỉ ra trật tự các trạng thái mà đối tượng hay tương tác

sẽ đi qua để đáp ứng sự kiện Hành vi của lớp hay cộng tác của lớp có thể được xácđịnh bằng máy trạng thái Máy trạng thái kích hoạt nhiều phần tử, bao gồm trạng thái,chuyển tiếp từ trạng thái này sang trạng thái khác, sự kiện và các hoạt động (đáp ứng

Các đối tượng GUI

Chờ

Hình 15: Gói

 Chú thích (Annotational)

Phần tử chú thích là bộ phận chú giải của một mô hình UML Là lời giải thích ápdụng để mô tả các phần tử khác trong mô hình Hay còn gọi là lời ghi chú

 Các quan hệ trong UML

 Quan hệ phụ thuộc (dependency)

Phụ thuộc là quan hệ ngữ nghĩa giữa hai phần tử trong đó thay đổi phần tử độclập sẽ tác động đến ngữ nghĩa của phần tử phụ thuộc

 Quan hệ kết hợp (association)

Kết hợp là quan hệ cấu trúc để mô tả tập liên kết (một liên kết là kết nốigiữa cácđối tượng) Khi đối tượng của lớp này gửi / nhận thông điệp thì gọi chúng có quan hệkết hợp

 Khái quát hoá (generalization)

Khái quát hoá là quan hệ đặc biệt hoá / khái quát hoá mà trong đó đối tượng cụthể sẽ kế thừa các thuộc tính và phương pháp của đối tượng tổng quát hoá

 Hiện thực hoá (realization)

Hiện thực hoá là quan hệ ngữ nghĩa giữa giao diện và lớp (hay thành phần) hiệnthực lớp

 Kiểu dữ liệu

Kiểu dữ liệu không phải là phần tử mô hình trong UML kiểu dữ liệu cơ sở làkiểu dữ liệu không có cấu trúc

Có các kiểu sau:

- Boolean: kiểu đếm với true/false

- Biểu thức (Expression): là xâu ký tự có cú pháp

- Tính nhiều (Multiplicity): tập không rỗng của các số nguyên dương và ký tự *

- Tên (Name): là xâu ký tự có khả năng đẩct phần tử

- Số nguyên (Integer): Là kiểu cơ bản và là phần tử của tập vô hạn các số nguyên

âm và dương

- Xâu (String): là trật tự của các ký tự, được sử dụng làm tên

- Thời gian (Time): xâu ký tự biểu diễn giá trị tuyệt đối hay khoảng tương đối

- Không lý giải (Unintepreted): là cái gì đó mà ý nghĩa của nó phụ thuộc vào lĩnhvực

 Biểu đồ trong UML

Biểu đồ là biểu diễn đồ hoạ tập các phần tử mô hình Vẽ biểu đồ để biểu diễn hệthống đang xây dựng dưới các góc độ quan sát khác nhau UML cho khả năng xâydựng một vài kiểu biểu đồ trực quan để biểu diễn các khía cạnh khác nhau của hệthống, bao gồm:

 Biểu đồ ca sử dụng (Use case diagram)

Chỉ ra tương tác giữa các UC và các tác nhân UC biểu diễn các chức năng hệthống Tác nhân là con ngườig hay hệ thống khác cung cấp hay thu nhận thông tin từ

hệ thống đang được xây dựng Chỉ ra tác nhân nào khởi độngUC và khi nào tác nhânnhận thông tin từ hệ thống

Biểu đồ UC chỉ ra chức năng tổng thể của hệ thống đang phát triển

Modify Existing Order Salesperson

Accounting System Enter New Order

Hình 16: Biểu đồ CA

 Biểu đồ tương tác (Interaction diagram)

Biểu đồ tương tác bao gồm hai dạng là biểu đồ trình tự và cộng tác

 Biểu đồ trình tự (sequence)

Biểu đồ trình tự chỉ ra luồng chức năng xuyên qua các UC, nó là biểu đồ mô tảtương tác giữa các đối tượng và tập trung vào mô tả trật tự các thông điệp theo thờigian

Biểu đồ trình tự là biểu đồ tương tác theo trật tự thời gian của các giao tiếp bằngthông điệp giữa các đối tượng Biểu đồ được đọc từ đỉnh xuống đáy Mỗi UC có nhiềuluồng dữ liệu Mỗi biểu đồ trình tự biểu diễn một luồng

 Biểu đồ cộng tác (Collaboration)

Biểu đồ cộng tác chỉ ra các thông tin như biểu đồ trình tự nhưng theo cách khác,

nó tập trung vào tổ chức cấu trúc các đối tượng gửi và nhận thông điệp Biểu đồ cộngtác và trình tự có thể biến đổi qua lại.Biểu đồ cộng tác đối tượng được đặt trong hìnhchữ nhật, tác nhân là người hình cây như biểu đồ trình tự Biểu đồ cộng tác khôngquan tâm đến thời gian Các đối tượng giao tiếp với nhau thể hiện bằng đường nốiBiểu đồ cộng tác chỉ ra luồng sự kiện xuyên qua kịch bản của UC Biểu đồ nàycho khả năng dễ quan sát các đối tượng nhưng khó quan sát về trình tự thông tin

: Salesperson

Order Options Form

Order Detail Form

5: Create new, blank order

6: Set the order number, customer, order item

7: Save the order

Hình 17: Biểu đồ cộng tác

 Biểu đồ lớp (Class diagram)

Biểu đồ lớp chỉ ra tương tác giữa các lớp trong hệ thống Các lớp được xem như

kế hoạch chi tiết của các đối tượng Đường nối giữa các phần tử biểu đồ lớp là quan hệgiao tiếp giữa chúng Phía trái của một số thuộc tính và thao tác có gắn biểu tượngkhoá, có nghĩa rằng đó là các thuộc tính và thao tác riêng

Trong biểu đồ lớp có các loại lớp sau;

- Lớp tham số: là lớp được sử dụng để tạo ra họ các lớp khác Còn có tên là lớpmẫu (template)

- Lớp hiện thực: là lớp tham số mà đối số của nó có giá trị

- Lớp tiện ích: Là tập hợp các thao tác

- Lớp tiện ích tham số: Là lớp tham số chứa tập các thao tác Đó là mẫu để tạolập ra lớp tiện ích

- Lớp tiện ích hiện thực: là lớp tiện ích tham số mà đối số của chúng có giá trị

- Metaclass: là lớp mà hiện thực của nó là lớp chứ không phải đối tượng

Ngoài ra trong biểu đồ lớp, Stereotype là cơ chế để phân nhóm lớp Lớp biên(boundary class), Lớp thực thể (Entity class), Lớp điều khiển (Control class)

 Biểu đồ chuyển trạng thái (state transition diagram)

o Biểu đồ chuyển trạng thái mô tả vòng đời của đối tượng, từ khi nó được sinh

ra đến khi bị phá huỷ Biểu đồ cung cấp cách thức mô hình hoá các trạng thái khácnhau của đối tượng Trong khi biểu đồ lớp cung cấp bức tranh tĩnh về các lớp và quan

hệ thì biểu đồ chuyển trạng thái được sử dụng để mô hình hoá các hành vi động của hệthống, chỉ ra hành vi động của đối tượng

Thông thường không tạo lập biểu đồ chuyển trạng thái cho mọi lớp mà chỉ chocác lớp phức tạp

o Biểu đồ chuyển trạng thái bao gồm các thông tin về các trạng thái khác nhaucủa đối tượng, thể hiện các đối tượng chuyển đổi từ trạng thái này sang trạng thái khácthế nào

o Biểu đồ trạng thái có điểm khởi đầu (hình tròn đen) và vài điểm kết thúc (hìnhtròn đen có đường bao) Các hoạt động trong biểu đồ thì được đặt trong chữ nhật góctròn

 Biểu đồ hoạt động (Activity diagram)

Biểu đồ hoạt động là một dạng đặc biệt của biểu đồ trạng thái, nó chỉ ra mộtluồng các hoạt động diễn ra từ hoạt động này đến hoạt động khác Biểu đồ hoạt độnghướng đến khung nhìn của hệ thống

 Biểu đồ thành phần (Component diagram)

Biểu đồ thành phần cho ta cái nhìn vật lý của mô hình Cho ta thấy các thànhphần phần mềm trong hệ thống và quan hệ giữa chúng Có hai loại thành phần đó làthành phần khả thực và thư viện

Biểu đồ thành phần là biểu đồ UML hiển thị các thành phần của hệ thống và phụthuộc giữa chúng

 Biểu đồ triển khai (Deployment diagram)

Biểu đồ triển khai chỉ ra bố trí vật lý của mạng và các thành phần hệ thống sẽ đặt

ở đâu

Thông qua biểu đồ triển khai mà người quản lý dự án, người sử dụng, kiến trúc

sư và đội ngũ triển khai hiểu phân bổ vật lý của hệ thống và các hệ thống con sẽ đượcđặt ở đâu

2.1.6 Kiến trúc hệ thống trong UML

Kiến trúc hệ thống phần mềm được mô tả bằng các khung nhìn Các khung nhìnánh xạ vào tổ chức và cấu trúc hệ thống, mỗi khung nhìn tập trung vào khía cạnh cụthể của hệ thống

 Khung nhìn ca sử dụng (UC view)

Khung nhìn UC mô tả các chức năng, hành vi và nhiệm vụ của hệ thống Khungnhìn này thể hiện mọi yêu cầu của hệ thống, do vậy khung nhìn này luôn đứng trướcmọi khung nhìn khác, được sử dụng để điều khiển, thúc đẩy và thẩm định các côngviệc của tất cả các giai đoạn trong quá trình phát triển phần mềm

 Khung nhìn thiết kế (Design view)

Khung nhìn thiết kế cảu một hệ thống biểu diễn tổ chức logic các lớp và các quan

hệ của chúng với nhau Khung nhìn này mô tả cấu trúc tĩnh của các lớp, các đối tượng

và sự liên kết của chúng thể hiện mối liên kết động thông qua trao đổi các thông điệp

và được thể hiện trong các biểu đồ lớp, biểu đồ đối tượng, biểu đồ tương tác Khungnhìn thiết kế tập trung vào cấu trúc của hệ thống, từ đó nhận biết được các bộ phận cơ

bản cấu thành hệ thống và thể hiện mọi quá trình trao đổi, xử lý thông tin cơ bản trong

hệ thống

 Khung nhìn cài đặt (Implemetation view)

Khung nhìn cài đặt hay còn gọi là khung nhìn thành phần, khung nhìn thực hiệnbao gồm các thành phần và các file được sử dụng để kết hợp và đưa ra các hệ thốngvật lý Khung nhìn thành phần bao gồm thành phần, biểu đồ thành phần và gói trong

đó một vài thành phần là thư viện còn một số khác là mã trình khả thực (.exe) và thưviện (.dll)

Người quan tâm đến khung nhìn này là người có trách nhiệm quản lý mã trình,dịch chương trình và triển khai ứng dụng

 Khung nhìn triển khai (Employment view)

Khung nhìn này tập trung vào phân bổ vật lý của tài nguyên và phân bổ nhiệm vụgiữa các tài nguyên Liên quan đến triển khai vật lý của hệ thống, khác với kiến trúclogic

 Khung nhìn tiến trình (Process view)

Biểu diễn phân tách các luồng thực hiện chương trình, đồng bộ giữa các luồng,

phân bổ các đối tượng và lớp cho các luồng thực hiện khác nhau Khung nhìn triếntrình tập trung vào các nhiệm vụ tương tranh với nhau như thế nào trong hệ thống đanhiệm

Trong biểu đồ của Rose không có khung nhìn này

2.2 Ngôn ngữ lập trình C#

2.2.1 Giới thiệu về ngôn ngữ lập trình C#

Ngôn ngữ C# được phát triển bởi đội ngũ kỹ sư của Microsoft, trong đó ngườidẫn đầu là Anders Hejlsberg và Scott Wiltamuth Cả hai người này điều là nhữngngười nổi tiếng, trong đó Anders Hejlsberg được biết đến là tác giả của Turbo Pascal,một ngôn ngữ lập trình PC phổ biến Và ông đứng đầu nhóm thiết kế Borland Delphi,một trong những thành công đầu tiên của việc xây dựng môi trường phát triển tích hợp(IDE) cho lập trình client/server

Ngôn ngữ C# là một ngôn ngữ được dẫn xuất từ C và C++, nhưng nó được tạo từnền tảng phát triển hơn Microsoft bắt đầu với công việc trong C và C++ và thêm vàonhững đặc tính mới để làm cho ngôn ngữ này dễ sử dụng hơn

C# là ngôn ngữ sử dụng giới hạn những từ khóa Phần lớn các từ khóa được sửdụng để mô tả thông tin Chúng ta có thể nghĩ rằng một ngôn ngữ có nhiều từ khóa thì

sẽ mạnh hơn Điều này không phải sự thật, ít nhất là trong trường hợp ngôn ngữ C#,chúng ta có thể tìm thấy rằng ngôn ngữ này có thể được sử dụng để làm bất cứ nhiệm

vụ nào Bảng sau liệt kê các từ khóa của ngôn ngữ C#

Bảng 1: Từ khóa của ngôn ngữ C#

Các đặc tính của ngôn ngữ C#:

- C# là ngôn ngữ hiện đại;

- C# là ngôn ngữ hướng đối tượng;

Bảng 2: Kiểu dữ liệu trong C#

+ NET cung cấp một thư viện các class rất đồ sộ, trong đó Console là một classnhỏ trong thư viện các class này.

+ Mỗi class có một tên riêng, vì vậy người lập trình không thể nào nhớ hết têncác class trong .NET Để giải quyết vấn đề này là việc tạo ra một namespace,namespace sẽ hạn chế phạm vi của một tên, làm cho tên này chỉ có ý nghĩa trong vùng

đã định nghĩa

- Từ khóa using:

+ Để không phải viết namespace cho từng đối tượng, ta dùng từ khóa using.+ Ta có thể dùng dòng lệnh using System ở đầu chương trình; Khi đó, thay vì viếtđầy đủ System.Console ta chỉ cần viết Console

- Phân biệt chữ thường và chữ hoa:

C# là ngôn ngữ phân biệt chữ thường với chữ hoa

- Toán tử '.':

Toán tử '.' được sử dụng để truy cập đến phương thức hay dữ liệu trong một class

và ngăn cách giữa tên class đến một namespace

Ví dụ: System.Console.WriteLine()

- Câu lệnh (statement):

Một chỉ dẫn lập trình đầy đủ được gọi là một câu lệnh

Ví dụ: int bankinh = 5; // một câu lệnh

- Kiểu chuỗi ký tự:

Kiểu chuỗi ký tự là một mảng các ký tự

+ Khai báo chuỗi hằng:

string <Tên_chuỗi_hằng> = <"Noi dung chuoi hang">;

Ví dụ: string tentuong = "Nhat Nghe";

+ Khai báo biến kiểu chuỗi:

string <Biến_chuỗi> [= "Noi dung chuoi hang"];

Ví dụ: string hoten = "Nguyen Van Teo";

Ví dụ: System.Console.WriteLine("Do dai cua chuoi la:");

+ Một số thao tác trên chuỗi:

Bảng 4: Thao tác trên chuỗi

2.2.3 Windows Form Application

2.2.3.1 Các thao tác với Form

- Thêm một Form mới vào Project:

+ Bước 1:

Cách 1: Vào menu Project | Add New Item …

Cách 2: Chọn công cụ Add New Item trên thanh Standart

+ Bước 2: Khai báo

Categories: chọn Windows Forms

Templates: chọn Windows Form

Name: đặt tên Form

+ Bước 3: Nhắp Add

- Thêm một Form có sẵn vào Project:

+ Bước 1: Vào menu Project | Add Existing Item …

+ Bước 2: Chọn Form

+ Bước 3: Nhắp Add

- Xóa bỏ một Form đang có trong Project:

+ Bước 1: Chọn Form cần gỡ bỏ (ở cửa sổ Solution Explorer)

+ Bước 2: Vào menu Edit | Delete

Khi nhắp chuột lên button, chương trình nhận được tín hiệu Click và lệnhđược thi hành.

Bảng 9: Các thuộc tính của Combobox

Bảng 10: Các thuộc tính của ListBox

2.2.3.3 Properties (thuộc tính) và Event (sự kiện) của Control

- Thuộc tính của Control:

+ Properties là những thông tin mà ta có thể thay đổi nội dung, cách trình bày …của người thiết kế để ứng dụng vào control

+ Mỗi lớp (class) có nhiều property khác nhau Tuy nhiên, vẫn có một sốproperty giống nhau được xây dựng từ lớp ban đầu

Bảng 11: Các thuộc tính giống nhau của Control

- Event (sự kiện) của Control:

+ Sự kiện là những phản ứng của đối tượng Nói cách khác, sự kiện là những tínhiệu phát ra khi người dùng thao tác trên đối tượng

+ Nhờ có event, người lập trình sẽ nhận được những tín hiệu và xử lý những tínhiệu đó để phản hồi lại cho người dùng, tạo nên sự nhịp nhàng cho chương trình

Bảng 12: Các sự kiện của Control

2.3 Giải thuật di truyền và Tính tiến hóa

2.3.1 Giải thuật di truyền

2.3.1.1 Ý tưởng

Giải thuật di truyền (GA- Genetic Algorithm) là mô phỏng theo quá trình tiếnhóa tự nhiên của sinh vật theo thuyết Darwin Trong quá trình tiến hóa, mỗi cá thể đềuphải tự tìm cách thích nghi tốt nhất với môi trường sống rất phức tạp và luôn luôn thayđổi Cá thể nào có khả năng thích nghi với môi trường cao hơn thì sẽ có khả năng tồntại, phát triển và sinh sản cao hơn, ngược lại cá thể nào có khả năng thích nghi thấp sẽ

có nhiều nguy cơ bị tiêu vong hoặc phát triển chậm Sự thích nghi đó được đúc kết vàghi lại trong cấu trúc của nhiễm sắc thể của chúng

Việc giải bài toán thực tế có thể xem là việc tìm kiếm trong một thời gian các lờigiải tiềm năng nhằm tìm ra lời giải tốt nhất hoặc chấp nhận được mà ta có thể gọi làquá trình tối ưu hóa

Đối với không gian tìm kiếm nhỏ, đơn giản nhất là dùng kỹ thuật “vét cạn”,nghĩa là liệt kê toàn bộ lời giải tiềm năng, sau đó kiểm tra điều kiện để chọn ra lời giải.Đối với không gian tìm kiếm khá lớn thì kỹ thuật vét cạn có độ phức tạp rất lớn, khóchấp nhận được Khi đó, giải thuật di truyền được xem là thích hợp cho việc giải quyếtbài toán tìm kiếm lời giải tối ưu

GA không chú trọng đến giải pháp duy nhất và chính xác như các phương thức

cổ điển, trái lại GA xét đến toàn bộ các giải pháp và chọn lấy giải pháp tương đối tốtnhất

GA dựa trên tính ngẫu nhiên như trong thế giới tự nhiên của sinh vật, nhưngđược hướng dẫn bởi hàm thích nghi

2.3.1.2 Đặc trưng

GA làm việc với một mã hóa của tập hợp tham số mà không phải một tham số

GA tìm kiếm từ một quần thể các điểm chứ không phải một điểm hoặc một vàiđiểm như phương pháp tìm kiếm leo đồi

GA đánh giá thông tin với hàm mục tiêu mà không đưa vào đạo hàm hay thôngtin bổ sung khác

GA sử dụng các luật biến đổi theo xác suất mà không sử dụng luật quyết định(Anh, 2011)

dạng về kiểu hình của một quần thể sinh học Quá trình phát triển của mỗi quần thểtuân theo quy luật chọn lọc tự nhiên mà tiến hóa qua các thế hệ nối tiếp nhau Trong

đó, các hậu duệ được sinh ra từ thế hệ trước thông qua quá trình sinh sản (di truyền vàbiến dị) cạnh tranh tự nhiên với nhau, cá thể nào có kiểu hình (và do đó kiểu gen) thíchnghi cao hơn trong môi trường phát triển thì sẽ có khả năng cao hơn tồn tại và sinh sảncon cháu Do đó, kiểu gen này sẽ tiến hóa và hoàn thiện Quá trình tiến hóa này đượclặp đi lặp lại, các cá thể có kiểu gen phù hợp sẽ sống sót và phát triển, các cá thể yếu

sẽ bị loại bỏ dần

GA là kỹ thuật tối ưu dựa trên khái niệm chọn lọc tự nhiên và di truyền Do vậy,lời giải của bài toán được trình bày như các gen trong nhiễm sắc thể GA mô tả mộtnhóm các lời giải tiềm năng được đề cử Qua tiến hóa và chọn lọc tự nhiên các nhiễmsắc thể với độ thích nghi tốt hơn sẽ xuất hiện

Chọn lọc tự nhiên đảm bảo cho cá thể độ thích nghi tốt nhất sẽ được truyền lạicho các thế hệ con cháu (các quần thể tương lai) Phép lai ghép kết hợp các gen từ hai

cá thể bố mẹ để tạo thành hai cá thể con mới với độ thích nghi có chiều hướng cao hơn

bố mẹ Phép biến dị cho phép tạo tra chất liệu di truyền mới, tạo ra những đột phátrong tìm kiếm thông tin mới

GA cung cấp sự cải tiến thế hệ về độ thích nghi của các cá thể và sau nhiều thế hệ

sẽ tạo ra các cá thể chứa những thiết lập biến đổi đã được tối ưu

Mỗi cá thể trong GA thường chỉ gồm một nhiễm sắc thể Do vậy thuật ngữ cá thể

và nhiễm sắc thế được dùng không phân biệt ngữ nghĩa (Anh, 2011).Đánh giá độ thích nghi của

P(t)

t=t+1 Chọn Q (t) từ P (t-1)// chọn lọc Roulette

Tái tạo P (t) từ Q (t)// bởi các toán tử di truyền

Đánh giá độ thích nghi của P (t) và chọn cá thể tốt nhất

Kiểm tra điều kiện kết thúc thuật toán thỏa mãn chưa N

t=0Khởi tạoBắt đầu

Trong đó:

- P (t) là quần thể tại thế hệ thứ t

- Q (t) là quần thể trung gian

Hình 18: Thuật toán chương trình

2.3.1.4 Nhiễm sắc thể và quần thể

Trong GA, mỗi cá thể (hay nhiễm sắc thể) được mã hóa bởi chuỗi nhị phân

Ví dụ: mỗi NST gồm 8 gens như sau:

Mỗi cá thể (một nhiễm sắc thể cụ thể) biểu thị một lời giải tiềm năng của bàitoán Một quá trình tiến hóa được thực hiên trên một quần thể (một tập hợp các cá thể)tương đương với sự tìm kiếm một không gian các lời giải tiềm năng

GA thực hiện việc tìm kiếm theo nhiều hướng bằng cách duy trì một tập lời giảitiềm năng, khuyến khích sự hình thành và trao đổi thông tin giữa các hướng Tập lờigiải qua quá trình tiến hóa và cuối cùng cho ta một lời giải đủ tốt theo yêu cầu Tại mỗithế hệ, các lời giải tương đối tốt được tái sinh, và các lời giải tương đối xấu bị loại bỏdần Để đánh giá mức độ tốt xấu của từng lời giải, người ta xây dựng hàm thích nghi,hàm này đóng vai trò như môi trường sống trong thuyết tiến hóa của Darwin

Mã hóa nhiễm sắc thể: biểu diễn mã nhị phân của mỗi lời giải tiềm năng Ta cócông thức: (bi – ai)*10p 2m i – 1

Trong đó:

- 10p sai số đến p chữ số thập phân

- bi là điểm cuối trên miền giới hạn

- ai là điểm đầu trên miền giới hạn

- mi là độ dài chuỗi nhị phân

Ví dụ: tìm giá trị cực đại của hàm số hai biến:

f(x1,x2) = 10+x1*sin x1+x2*sin x2 trên miền với sai sốcác biến là 10-2

Hàm đánh giá