Luận văn: Nghiên cứu xây dựng phần mềm lập lịch thi đấu thể thao trên cơ sở các thuật toán đồ thị

Chia sẻ: Nhung Thi | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

93
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Khi giải quyết nhiều bài toán lý thuyết đồ thị, ta luôn phải duyệt qua tất cả các đỉnh của đồ thị đó. Cho nên, cần có thuật toán duyệt toàn bộ các đỉnh của đồ thị này. Gọi chung là thuật toán duyệt đồ thị. Trong đó có thuật toán duyệt theo chiều sâu và duyệt theo chiều rộng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn: Nghiên cứu xây dựng phần mềm lập lịch thi đấu thể thao trên cơ sở các thuật toán đồ thị

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG ----------------------------- NGUY N TH H I VY NGHIÊN C U XÂY D NG PH N M M L P L CH THI Đ U TH THAO TRÊN CƠ S CÁC THU T TOÁN Đ TH Chuyên ngành: Khoa h c máy tính Mã s : 60.48.01 TÓM TÁT LU N VĂN TH C S KHOA H C Đà N ng - Năm 2011
2 M Đ U 1. Lý do ch n ñ tài Lý thuy t ñ th là m t lĩnh v c nghiên c u ñã có t lâu và có nhi u ng d ng trong ngành công ngh thông tin. Hi n nay s phát tri n c a các thu t toán trên ñ th là m t trong các m i quan tâm chính c a ngành khoa h c máy tính. Vi c ng d ng lý thuy t ñ th ñ xây d ng các gi i thu t v n luôn là v n ñ ñư c nghiên c u sâu và phát tri n cho phù h p v i yêu c u c a công ngh hi n ñ i. T nhi u bài toán ng d ng c ñi n c a lý thuy t ñ th , ti p t c tìm ra các gi i pháp cho các bài toán ng d ng hi n ñ i là v n ñ c n quan tâm nghiên c u. Đ án ñ i m i giáo d c ñ i h c Vi t Nam ñang ñư c th c thi, vi c ng d ng công ngh thông tin và ñ i m i phương pháp gi ng d y, áp d ng phương ti n công ngh tiên ti n là m t trong nh ng n i dung quan tr ng trong n n giáo d c hi n nay. Đ i v i các trư ng năng khi u th thao, vi c d y h c và hu n luy n có vài s khác bi t so v i các trư ng khác nên cách qu n lý và gi ng d y cũng khác. Vi c ng d ng công ngh thông tin t lâu v n luôn ñư c s quan tâm c a lãnh ñ o ngành, tuy nhiên chưa có nhi u các ph n m m gi ng d y ph c v cho các trư ng năng khi u th thao này. Hư ng nghiên c u và k t qu c a ñ tài nh m ñóng góp m t ph n vào vi c ñưa ra gi i pháp và thu t toán ñ xây d ng ph n m m x p l ch thi ñ u th thao t i các trư ng năng khi u TDTT.
3 Vì v y, ñ tài: “Nghiên c u xây d ng ph n m m l p l ch thi ñ u th thao trên cơ s các thu t toán ñ th ” s là hư ng nghiên c u t t ñ tôi ch n làm ñ tài t t nghi p th c s c a mình. 2. M c ñích nghiên c u M c ñích chính c a ñ tài là: Nghiên c u lý thuy t ñ th và tìm hi u, nghiên c u quy trình, cách th c t ch c các gi i thi ñ u th thao. ng d ng các thu t toán ñ th ñ ñ ra gi i pháp, thu t toán cho bài toán x p l ch thi ñ u th thao. Xây d ng, thi t k ph n m m l p l ch thi ñ u th thao. 3. Đ i tư ng và ph m vi nghiên c u Đ i tư ng ñư c nghiên c u c th là: nghiên c u lý thuy t v ñ th , các thu t toán trên ñ th , bài toán tô màu và ng d ng l p l ch thi, tham kh o m t vài h th ng l p l ch hi n có. Trong ph m vi gi i h n c a ñ tài, lu n văn nghiên c u cách l p l ch thi ñ u Đi n kinh t i các trư ng năng khi u TDTT, t ñó ng d ng tri n khai thi t k và xây d ng ph n m m l p l ch thi ñ u Đi n kinh bi u di n trên máy tính d a trên cơ s các thu t toán c a ñ th . 4. Phương pháp nghiên c u S d ng phương pháp nghiên c u lý thuy t k t h p v i l p trình th c nghi m. - Nghiên c u lý thuy t v Lý thuy t ñ th , các gi i thu t trong ñ th và ng d ng, phân tích và t ng h p tài li u liên quan. - Tìm hi u, nghiên c u quy trình t ch c l p l ch thi ñ u m t gi i ñ u môn Đi n kinh. (Tìm hi u các ràng bu c c a bài toán) - Phân tích yêu c u bài toán, xây d ng gi i thu t phù h p. - Phân tích và thi t k ng d ng. - Xây d ng Demo ph n m m minh ho .
4 - Đánh giá k t qu theo yêu c u c a ñ tài. 5. Ý nghĩa khoa h c và th c ti n c a ñ tài Ph n nghiên c u lý thuy t s cung c p m t cách nhìn t ng quát v lý thuy t ñ th và các thu t toán trong lý thuy t ñ th . K t qu nghiên c u có th áp d ng cho các trư ng năng khi u th thao ho c các S văn hóa th thao du l ch. 6. C u trúc c a lu n văn Toàn b n i dung c a Lu n văn ñư c chia thành 3 chương như sau: Chương 1: Trình bày n i dung nghiên c u t ng quan v lý thuy t ñ th , m t s gi i thu t liên quan ñ n ñ tài và gi i thi u vài h th ng l p l ch hi n có. Chương 2: Gi i thi u m t vài nét v môn thi ñ u Đi n kinh, mô t bài toán x p l ch thi ñ u Đi n kinh. Phân tích thi t k h th ng l p l ch thi ñ u môn Đi n kinh và gi i thi u m t các thu t toán s d ng ñ xây d ng ph n m m. Chương 3: Gi i thi u ng d ng là ph n m m l p l ch thi ñ u môn Đi n kinh, cài ñ t ng d ng và ñưa ra m t s k t qu th c hi n c a ng d ng. ------------- CHƯƠNG 1 – NGHIÊN C U T NG QUAN
5 1.1. T NG QUAN V LÝ THUY T Đ TH 1.1.1. M t s khái ni m liên quan ñ n ñ th 1.1.1.1. Đ th , ñ nh, c nh, cung. Đ th là m t c u trúc r i r c g m t p h p các ñ nh và t p h p các c nh n i các ñ nh ñó. Ngư i ta phân lo i ñ th d a trên ñ c ñi m c a các c nh n i. - Đ th vô hư ng G = (V,E) g m m t t p V các ñ nh và t p E các c nh. M i c nh e ∈ E ñư c liên k t v i m t c p ñ nh v, w (không k th t ) v w e - Đ th có hư ng G = (V,E) g m m t t p V các ñ nh và t p E các c nh có hư ng g i là cung. M i cung e ∈ E ñư c liên k t v i m t c p ñ nh (v, w) có th t . v w e Đ th vô hư ng có th coi là ñ th có hư ng trong ñó m i c nh e = (v, w) tương ng v i hai cung (v, w) và (w, v). + Các c nh song song: n u có nhi u c nh liên k t v i cùng m t c p ñ nh. + Khuyên: là c nh có hai ñ nh liên k t trùng nhau. + Đ nh cô l p: Đ nh không k v i ñ nh khác. 1.1.1.2. B c, n a b c vào, n a b c ra Cho ñ th G = (V, E) - B c c a ñ nh v∈V là t ng s c nh liên thu c v i nó và ký hi u là d(v). N u ñ nh có khuyên thì m i khuyên ñư c tính là 2 khi tính b c. - N a b c: Cho G=(V,E) là ñ th có hư ng, v ∈ V. N a b c ra c a ñ nh v, ký hi u là d0(v), là s cung ñi ra t ñ nh v (v là ñ nh ñ u).
6 N a b c vào c a ñ nh v∈V, ký hi u là d1(v), là s cung ñi t i ñ nh v (v là ñ nh cu i). 1.1.1.3. Đư ng ñi, chu trình, tính liên thông Cho ñ th G = (V, E). Dây µ t ñ nh v ñ n ñ nh w là dãy các ñ nh và c nh n i ti p nhau b t ñ u t ñ nh v và k t thúc t i ñ nh w. S c nh trên dây µ g i là ñ dài c a dây µ. Dây µ t ñ nh v ñ n ñ nh w ñ dài n ñư c bi u di n như sau: µ = (v, e1, v1, e2, v2, ...., vn-1, en, w) trong ñó vi (i = 1,...,n-1) là các ñ nh trên dây và ei (i = 1,...,n) là các c nh trên dây liên thu c ñ nh k trư c và sau nó. Các ñ nh và c nh trên dây có th l p l i. - Đư ng ñi t ñ nh v ñ n ñ nh w là dây t ñ nh v ñ n ñ nh w, trong ñó các c nh không l p l i. - Chu trình là ñư ng ñi có ñ nh ñ u và ñ nh cu i trùng nhau. - Đư ng ñi có hư ng trong ñ th có hư ng là dãy có hư ng, trong ñó các cung không l p l i. Đ th vô hư ng g i là liên thông, n u m i c p ñ nh c a nó ñ u có ñư ng ñi n i chúng v i nhau. Đ th có hư ng g i là liên thông m nh, n u m i c p ñ nh c a nó ñ u có ñư ng ñi có hư ng n i chúng v i nhau. 1.1.2. Bi u di n ñ th trên máy tính 1.1.2.1. Bi u di n ñ th b ng ma tr n k 1.1.2.2. Bi u di n ñ th b ng ma tr n liên thu c 1.1.2.3. Bi u di n b ng danh sách k 1.1.3. Đ th ñ ng c u
7 1.1.4. Đ th ph ng 1.2. M T S GI I THU T LIÊN QUAN Đ N Đ TÀI 1.2.1. Tô màu b n ñ 1.2.2. Thu t toán tu n t ưu tiên ñ nh b c l n nh t Cho ñ th G=(V,E). Thu t toán sau s tô màu các ñ nh ñ th v i s màu k g n v i s c s χ(G). (i) L p danh sách các ñ nh ñ th E':= [v1, v2,... , vn] theo th t b c gi m d n d(v1) ≥ d(v2) ≥... ≥ d(vn) Đ t i:= 1 (ii) Tô màu i cho ñ nh ñ u tiên trong danh sách. Duy t l n lư t các ñ nh ti p theo và tô màu i cho ñ nh không k ñ nh ñã ñư c tô màu i (iii) N u t t c các ñ nh ñã ñư c tô màu thì k t thúc: Đ th ñã ñư c tô màu b ng i màu. Ngư c l i sang bư c (iv) (iv) Lo i kh i E' các ñ nh ñã tô màu, ñ t i:= i+1, và quay l i bư c (ii). 1.2.3. Tô màu ñ th ph ng 1.3. M T S BÀI TOÁN NG D NG 1.3.1. Bài toán l p l ch thi Gi s m i sinh viên ph i thi m t s môn trong n môn thi. Hãy l p l ch thi trong trư ng ñ i h c sao cho không có sinh viên nào thi hai môn cùng m t th i gian và s ñ t thi là ít nh t. Gi i pháp: Bài toán ñư c bi u di n b ng ñ th : - M i môn thi là m t ñ nh. - N u 2 môn thi nào ñư c d thi b i cùng m t sinh viên thì s ñư c n i b ng m t c nh.
8 - Cách l p l ch thi s tương ng v i bài toán tô màu c a ñ th này. Ví d . Có 7 môn thi c n x p l ch. Các môn h c ñư c ñánh s t 1 ñ n 7. Các c p môn thi sau có chung sinh viên: (1,2), (1,3), (1,4), (1,7), (2,3), (2,4), (2,5), (2,7), (3,4),(3,6), (3,7),(4,5),(4,6),(5,7),(6,7),(5,6) Đ th tương ng như sau: Hình 1.6 – Đ th minh h a bài toán l p l ch thi Áp d ng thu t toán ta tô màu các ñ nh ñ th có ñư c k t qu sau: Đ nh: 2 3 4 7 1 5 6 B c: 5 5 5 5 4 4 4 Màu: 1 2 3 3 4 2 1 Như v y ta có l ch thi g m 4 ñ t thi như sau: Đ t 1: Thi các môn 2, 6 Đ t 2: Thi các môn 3, 5 Đ t 3: Thi các môn 4, 7 Đ t 4: Thi môn 1 1.3.2. Bài toán phân chia t n s 1.3.3. Bài toán ñi u khi n ñèn hi u nút giao thông
9 1.4. ĐÁNH GIÁ M T VÀI H TH NG L P L CH HI N CÓ 1.4.1. L ch trình thi ñ u bóng ñá “2010 World Cup Final Tournament Schedule” 1.4.2. Bài toán tô màu và ng d ng xây d ng ph n m m x p l ch thi cho h c ch tín ch 1.4.3. Bài toán t o l ch thi ñ u Tennis theo thu t toán chia ñ tr . 1.4.4. Bài toán x p l ch thi ñ u môn Bóng ñá theo thu t toán chia ñ tr . ---------------- CHƯƠNG 2 - PHÂN TÍCH THI T K H TH NG L P L CH THI Đ U MÔN ĐI N KINH 2.1. T NG QUAN V MÔN ĐI N KINH 2.1.1 Đi n kinh là gì? 2.1.2. Đi u l thi ñ u m t gi i ñ u ñi n kinh 2.1.3. Qui trình l p l ch thi ñ u truy n th ng 2.2. MÔ T BÀI TOÁN X P L CH THI Đ U ĐI N KINH 2.2.1. Đ c t bài toán Đi n kinh là m t môn th thao bao g m nhi u n i dung thi ñ u (ch y, nh y, ñá c u, ñ y t …). M t gi i ñ u ñi n kinh ñư c t ch c thi theo các n i dung thi. N u v n ñ ng viên ñáp ng t t các yêu c u c a ñi u l thi ñ u có th ñăng ký tham gia gi i ñ u ñi n kinh. Ban t ch c gi i ñ u s thông báo các n i dung thi ñ các v n ñ ng viên có th ñăng ký tham gia. Sau khi có b ng danh sách chính
10 th c v các v n ñ ng viên ñăng ký, ban t ch c s ti n hành l p l ch thi ñ u cho toàn gi i. Như v y, m t v n ñ ng viên có th ñăng ký t i ña n n i dung thi ñ u (n là s lư ng n i dung thi mà m t v n ñ ng viên ñư c tham gia theo qui ñ nh c a ñi u l gi i). Vì v y, l ch thi c n ph i ñư c b trí ñ n u có m t v n ñ ng viên ñăng ký nhi u n i dung thi ñ u thì các n i dung thi này không ñư c thi cùng ngày. L ch thi ñư c chia thành nhi u ngày thi. Trong m t ngày, m t ñ a ñi m (sân v n ñ ng) có th t ch c nhi u n i dung thi. M i v n ñ ng viên s thi m t n i dung trong m t ngày thi. M i n i dung có th thi trong m t ngày ho c nhi u ngày (tùy gi i ñ u). 2.2.2. Xây d ng ñ th cho bài toán Cho ñ th N ñ nh (N
11 - Th i gian thi ñ u: t ngày … ñ n ngày........ 2.3.1.2. Các ràng bu c c a bài toán - S ngày thi là ít nh t. - Phân b các v n ñ ng viên thi ñ u vào các ngày thi sao cho chúng không xung ñ t nhau, v n ñ ng viên d thi không trùng l ch (không vi ph m ràng bu c là n u có v n ñ ng viên thi nhi u hơn 1 n i dung thì các n i dung thi này không ñư c thi cùng ngày v i nhau). - V n ñ ng viên thi ñ u theo gi i tính riêng, không có n i dung h n h p nam n . 2.3.1.3. D li u ñ u ra L ch thi g m: - Ngày thi - N i dung thi - Đ a ñi m thi - Thông tin chi ti t VĐV d thi t ng n i dung. 2.3.2. Phân tích h th ng và thi t k cơ s d li u: 2.3.2.1. Xác ñ nh các th c th 1. Th c th tblTest: - Ch a các thông tin chi ti t v các n i dung thi ñ u trong gi i ñ u Đi n kinh. - Các thu c tính: testCode, NameTest, Description - Mô t : M i n i dung thi ñ u có m t mã n i dung (testCode) duy nh t, m i testCode xác ñ nh m t tên n i dung thi ñ u (NameTest), m t mô t c th v n i dung thi ñ u ñó (Description). 2. Th c th tblAtheletes: - Ch a thông tin v v n ñ ng viên ñăng ký tham gia thi ñ u.
12 - Các thu c tính: athletesCode, athletesName, Sex, Birthday, Team, Address, Tel. - Mô t : M i v n ñ ng viên ñăng ký tham gia thi ñ u có m t mã v n ñ ng viên duy nh t (athletesCode), m i athletesCode xác ñ nh tên m t v n ñ ng viên (athletesName), gi i tính v n ñ ng viên (Sex), ngày sinh (Birthday), thu c ñ i thi nào (Team), ñ a ch v n ñ ng viên (Address), s ñi n tho i liên l c (Tel). 3. Th c th tblRegister: - Ghi nh n các thông tin ñăng ký d thi c a v n ñ ng viên. - Các thu c tính: athletesCode, testCode, ExamCode. - Mô t : Thông qua mã v n ñ ng viên (athletesCode), mã n i dung thi ñ u (testCode), mã kỳ thi (ExamCode), m i v n ñ ng viên có th tham gia ñăng ký m t ho c nhi u n i dung thi ñ u trong m t kỳ thi b t kỳ. 4. Th c th tblSchedule: - Mô t chi ti t các thông tin v l ch trình thi ñ u. - Các thu c tính: ExamCode, testCode, DateofTest, Stadium. - Mô t : Th c th này s tr v k t qu c a l ch thi là m i kỳ thi (thông qua mã kỳ thi ExamCode) s có các n i dung thi (thông qua mã n i dung thi testCode), các n i dung thi ñ u s ñư c phân chia vào t ng ngày thi tương ng (DateofTest), thi t i sân v n ñ ng nào (Stadium) 5. Th c th tblExamination: - Ch a các thông tin v kỳ thi ñ u Đi n kinh. - Các thu c tính: ExamCode, ExamName, Start, Finish. - Mô t : M i kỳ thi ñ u tương ng v i m t mã kỳ thi (ExamCode) duy nh t, m i ExamName xác ñ nh m t tên kỳ thi, th i gian b t ñ u (Start) và th i gian k t thúc kỳ thi (Finish) c a kỳ thi ñó.
13 2.3.2.2. Mô hình th c th quan h Hình 2.1- Mô hình th c th quan h Trong mô hình này bi u di n m t kỳ thi ñ u Đi n kinh b t kỳ (tblExamination) s t ch c nhi u n i dung thi ñ u (tblTest). M t v n ñ ng viên (tblAtheletes) s tham gia ñăng ký các n i dung thi trong kỳ thi này. Sau khi có các thông tin c n thi t, ban t ch c kỳ thi s t o ra m t l ch thi ñ u cho các v n ñ ng viên tham gia. K t qu c a l ch thi s th hi n rõ v n ñ ng viên thi n i dung nào thu c ngày thi nào, t i sân v n ñ ng nào.
14 2.3.2.3. Các ràng bu c toàn v n d li u Ta có cơ s d li u TDTT như sau: tblExamination (ExamCode, ExamName, Start, Finish) tblTest (testCode, NameTest, Description) tblAtheletes (athletesCode, athletesName, Sex, Birthday, Team, Address, Tel) tblRegister (ExamCode, testCode, athletesCode) tblSchedule (ExamCode, testCode, DateOfTest, Stadium) a. Toàn v n th c th : Qui t c toàn v n th c th yêu c u m i b ng quan h (th c th ) ph i có khóa chính, các thu c tính khóa ph i có giá tr duy nh t và khác null. Qui t c này không cho phép hai b n ghi trùng khóa. Trong bài vi t này, ta có các qui t c toàn v n th c th ràng bu c sau: - Trong quan h tblExamination, thu c tính khóa ExamCode là khóa chính nên không th nh n giá tr null và có giá tr không trùng nhau, không có kho ng tr ng. - Trong quan h tblTest, thu c tính khóa testCode là khóa chính nên không th nh n giá tr null và có giá tr không trùng nhau, không có kho ng tr ng. - Trong quan h tblAtheletes, thu c tính khóa athletesCode là khóa chính nên không th nh n giá tr null và có giá tr không trùng nhau, không có kho ng tr ng. - Trong quan h tblRegister, các thu c tính khóa (ExamCode, testCode, athletesCode) không th nh n giá tr null và có giá tr không trùng nhau.
15 - Trong quan h tblSchedule, c p thu c tính khóa (ExamCode, testCode) không th nh n giá tr null và có giá tr không trùng nhau. b. Toàn v n tham chi u Toàn v n tham chi u là ràng bu c ñ m b o tính h p l c a s tham chi u c a m t ñ i tư ng trong cơ s d li u (g i là ñ i tư ng tham chi u) ñ n ñ i tư ng khác (g i là ñ i tư ng ñư c tham chi u) trong cơ s d li u ñó. Các thu c tính tương ng g i là thu c tính c p ghép c a ràng bu c tham chi u. Qui t c toàn v n tham chi u ñư c xét ñ n trong khi c p nh t quan h tham chi u ho c quan h ñư c tham chi u. Ta có các toàn v n tham chi u sau: - Thu c tính athletesCode c a th c th tblRegister là khóa ngo i tham chi u ñ n khóa chính athletesCode c a quan h tblAtheletes: tblRegister.athletesCode tblAtheletes.athletesCode Quan h tblRegister là quan h tham chi u và quan h tblAtheletes là quan h ñư c tham chi u, v i c p ghép (tblRegister.athletesCode, tblAtheletes.athletesCode) - Thu c tính testCode c a th c th tblRegister là khóa ngo i tham chi u ñ n khóa chính testCode c a quan h tblTest: tblRegister.testCode tblTest.testCode Quan h tblRegister là quan h tham chi u và quan h tblTest là quan h ñư c tham chi u, v i c p ghép (tblRegister.testCode , tblTest.testCode) - Thu c tính ExamCode c a th c th tblRegister là khóa ngo i tham chi u ñ n khóa chính ExamCode c a quan h tblExamination:
16 tblRegister.ExamCode tblExamination.ExamCode Quan h tblRegister là quan h tham chi u và quan h tblExamination là quan h ñư c tham chi u, v i c p ghép (tblRegister.ExamCode, tblExamination.ExamCode) - Thu c tính testCode c a th c th tblSchedule là khóa ngo i tham chi u ñ n khóa chính testCode c a quan h tblTest: tblSchedule.testCode tblTest.testCode Quan h tblSchedule là quan h tham chi u và quan h tblTest là quan h ñư c tham chi u, v i c p ghép (tblSchedule.testCode, tblTest.testCode) - Thu c tính ExamCode c a th c th tblSchedule là khóa ngo i tham chi u ñ n khóa chính ExamCode c a quan h tblExamination: tblSchedule.ExamCode tblExamination.ExamCode Quan h tblSchedule là quan h tham chi u và quan h tblExamination là quan h ñư c tham chi u, v i c p ghép (tblSchedule.ExamCode, tblExamination.ExamCode) c. Mi n giá tr : Đây là lo i ràng bu c lên các giá tr h p l c a thu c tính. Mi n giá tr là t p h p t t c các lo i d li u và ph m vi giá tr ñư c thu c tính th a nh n. Trong cơ s d li u này, mi n giá tr xác ñ nh các tham s ñ c trưng c a các thu c tính như sau: Xét quan h tblTest (testCode, NameTest, Description) Tên Ý nghĩa Ki u d li u Đ dài Null support testCode Mã n i dung thi Ký t (nchar) 10 Non-null NameTest Tên n i dung thi ñ u Ký t (nvarchar) 50 Non-null Description Mô t chi ti t nvarchar 50 Null
17 Xét quan h : tblAtheletes (athletesCode, athletesName, Sex, Birthday, Team, Address, Tel). Khuôn Ph m vi Null Tên Ý nghĩa Ki u d li u Đ dài d ng support Mã v n ñ ng Ký t athletesCode 10 Non-null viên (nchar) Tên v n 50 Non-null athletesName Ký t (nvarchar) ñ ng viên ‘-’ n ‘+’ nam Non-null Sex Gi i tính Ký t 1 ‘0’ ñ ng tính < Ngày Birthday Ngày sinh smalldatetime Non-null hi n hành Team Đ i thi nvarchar 50 Non-null Address Đa ch nvarchar 50 Non-null Tel Đi n tho i Ký t (nchar) 12 Null Xét quan h tblExamination (ExamCode, ExamName, Start, Finish) Ph m vi Null Tên Ý nghĩa Ki u d li u Đ dài support ExamCode Mã kỳ thi Ký t (nchar) 10 Non-null ExamName Tên kỳ thi Ký t (nvarchar) 50 Non-null Start Ngày b t ñ u datetime Non-null Finish Ngày k t thúc datetime > = Start Non-null
18 Xét quan h tblSchedule (ExamCode, testCode, DateOfTest, Stadium) Ki u Đ Ph m vi Null Tên Ý nghĩa d li u dài support Start
19 2.4. CÁC THU T TOÁN S D NG XÂY D NG PH N M M 2.4.1. Gi i thu t t a ngôn ng - Nh p d li u ñ u vào: + dsVDV: danh sách v n ñ ng viên ñăng ký thi các n i dung. + dsNDthi: là danh sách các n i dung thi ñ u + dsExam: danh sách các gi i ñ u. - Đ u ra: + SoNgay: s lư ng ngày c n thi t t i ưu ñ t ch c thi ñ u. + MonThi: n i dung thi ñ u ñư c t ch c t i gi i ñ u. + dsSchedule: là danh sách l ch thi ñ u tương ng v i thông tin ngày thi, n i dung thi và s lư ng v n ñ ng viên d thi. Tư tư ng gi i thu t: - Bư c 1: Tính b c cho các ñ nh trên ñ th và s p x p các ñ nh này theo th t b c gi m d n vào m t m ng. Đ t i =1; - Bư c 2: Tô màu i cho ñ nh ñ u tiên có b c cao nh t trong m ng ñã s p x p bư c 1. Duy t l n lư t các ñ nh ti p theo và tô màu i cho ñ nh không k v i ñ nh ñã tô màu i. - Bư c 3: N u t t c các ñ nh ñã ñư c tô màu thì k t thúc, ñ th ñư c tô b ng i màu. Ngư c l i, sang bư c 4. - Bư c 4: Lo i ra kh i m ng các ñ nh ñã tô màu, s p x p l i các ñ nh theo th t b c gi m d n. Đ t i = i +1 và quay l i bư c 2. 2.4.2. Các bư c gi i thu t - Bư c 1: Xây d ng m t ñ th v i n ñ nh, t p ñ nh ñây chính là các n i dung thi ñ u và m i quan h c a các ñ nh này d a vào thông tin ñăng ký d thi ñ u vào c a các v n ñ ng viên.
20 n= dsLLich: s lư ng ñ nh c a ñ th arrSoThuTu[]: m ng ch a các ñ nh theo th t b c gi m d n. mau = cacMon[arrSoThuTu[i]].MauDaTo : ñ nh i có b c cao nh t c a ñ th ñư c tô màu là mau, ñ nh i tương ng v i n i dung thi ñ u i. N u mau nh n giá tr 0 t c là n i dung thi ñ u i chưa ñư c tô màu. - Bư c 2: Áp d ng bài toán tô màu trong l p l ch thi ñ u + Kh i t o cho màu hi n hành b ng 0 this.cacMon[i].MauDaTo = 0; 1. Tính b c cho các ñ nh trên ñ th : decimal[] arrBac = new decimal[cacMon.Length]; arrBac[i] = Convert.ToDecimal(cacMon[i].lstCacMon.Count); 2. S p x p các ñ nh vào m ng theo th t b c gi m d n: int[] arrSoThuTu = new int[cacMon.Length]; quickSort(ref arrSoThuTu, ref arrBac, 0, cacMon.Length- 1); 3. Tô màu cho ñ nh ñ u tiên có b c cao nh t trong m ng ñã s p x p: int mau = 1; for (int i = 0; i < arrSoThuTu.Length; i++) { if (i == 0) { cacMon[arrSoThuTu[i]].MauDaTo = mau; } …… 4. Duy t l n lư t các ñ nh ti p theo và tìm ñ nh j ñ tô màu gi ng i th a mãn ñi u ki n ñ nh j có s b c l n nh t mà không k v i i. mau = 0; for (int j = 0; j < i; j++)