LUẬN VĂN:MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ

Chia sẻ: Sunflower Sunflower_1 | Ngày: | Loại File: PDF | Số trang:84

Thêm vào BST

Báo xấu

554
lượt xem 101
download

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

Nội dung luận văn được chia thành 3 chương:Chương I. Những kiến thức cơ bản về thuật toán.Ở chương này, chúng tôi trích nêu khái niệm về bài toán và thuật toán. Các tính chất của thuật toán, xác định độ phức tạp của thuật toán…Cuối cùng, chúng tôi giới thiệu ba thuật toán quan trọng trên đồ thị mà học sinh THPT sẽ được học.

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:MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHINH MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ LUẬN VĂN THẠC SĨ Hà Nội - 2011 Trang 3
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHINH MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HỒ CẨM HÀ Hà Nội - 2011 Trang 4
LỜI CAM ĐOAN Tôi xin cam đoan, kết quả luận văn hoàn toàn là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu dưới sự hướng dẫn của TS. Hồ Cẩm Hà. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. Học viên Nguyễn Thị Chinh Trang 5
LỜI CẢM ƠN Trước hết, tôi muốn gửi lời cảm đến các Thầy, Cô trong khoa Công nghệ thông tin- Trường Đại học Công nghệ - Đại học Quốc gia Hà nội đã truyền đạt các kiến thức quý báu cho tôi trong suốt thời gian học tập tại trường. Đặc biệt, tôi xin gửi lời cảm ơn sâu sắc tới cô giáo hướng dẫn TS Hồ Cẩm Hà, người đã tận tình chỉ bảo và hướng dẫn về mặt chuyên môn cho tôi trong suốt quá trình thực hiện luận văn này. Cũng qua đây, tôi xin gửi lời cảm ơn đến Ban Giám hiệu trường THPT Chuyên Đại học Sư phạm Hà Nội, nơi tôi đang công tác đã tạo mọi điều kiện thuận lợi cho tôi trong thời gian học tập cũng như trong suốt quá trình thực hiện luận văn tốt nghiệp. Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn ủng hộ, động viên tôi rất nhiều để tôi yên tâm nghiên cứu và hoàn thành luận văn. Trong suốt quá trình làm luận văn, bản thân tôi đã cố gắng tập trung tìm hiểu, nghiên cứu và tham khảo thêm nhiều tài liệu liên quan. Tuy nhiên, do thời gian hạn chế và bản thân còn chưa có nhiều kinh nghiệm trong nghiên cứu khoa học, chắc chắn bản luận văn vẫn còn nhiều thiếu sót. Tôi rất mong được nhận sự chỉ bảo của các Thầy Cô giáo và các góp ý của bạn bè, đồng nghiệp để luận văn được hoàn thiện hơn. Hà Nội, ngày 12 tháng 06 năm 2011 Nguyễn Thị Chinh Trang 6
MỤC LỤC LỜI CẢM ƠN ................................................................................................... 6 LỜI NÓI ĐẦU ................................................................................................. 10 Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN .................... 12 1. Khái niệm bài toán Tin học ....................................................................... 12 2. Khái niệm thuật toán ................................................................................. 12 3. Các tính chất của thuật toán ...................................................................... 13 4. Độ phức tạp và xác định độ phức tạp của thuật toán.................................. 14 5. Chi phí thực hiện thuật toán ...................................................................... 18 6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường Trung học Phổ thông Chuyên .................................................................................. 18 6.1. Một số khái niệm cơ bản về đồ thị ...................................................... 18 6.1.1. Khái niệm đồ thị (Graph) .............................................................. 18 6.1.2. Các khái niệm cơ bản ................................................................... 19 6.2. Bài toán tìm kiếm trên đồ thị .............................................................. 21 6.2.1. Phát biểu bài toán ......................................................................... 21 6.2.2. Giới thiệu thuật toán tìm kiếm DFS và BFS ................................. 22 6.2.3. Độ phức tạp tính toán của thuật toán DFS và BFS ........................ 24 6.3. Bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số ...................... 24 6.3.1. Phát biểu bài toán ......................................................................... 24 6.3.2. Giới thiệu thuật toán Ford - Bellman ............................................ 25 6.2.3. Giới thiệu thuật toán thuật toán Dijkstra ....................................... 26 6.3.4. Độ phức tạp .................................................................................. 28 6.4. Các thuật toán tìm kiếm trên cây khung .............................................. 28 6.4.1. Bài toán cây khung ....................................................................... 28 6.4.2. Giới thiệu thuật toán Prim ............................................................ 29 6.4.3. Giới thiệu thuật toán Kruskal ........................................................ 30 6.4.5. Độ phức tạp ................................................................................. 31 Trang 7
6.5. Bài toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị ........... 32 6.5.1. Phát biểu bài toán ......................................................................... 32 6.5.2. Giới thiệu thuật toán tìm chu trình Hamilton: ............................... 33 Chương 2 MÔ PHỎNG THUẬT TOÁN .......................................................... 34 1. Khái niệm và chức năng của mô phỏng ..................................................... 34 2. Lịch sử của mô phỏng thuật toán............................................................... 35 3. Hiệu quả của mô phỏng thuật toán trong giảng dạy ................................... 37 4. Một số yêu cầu đối với mô phỏng thuật toán ............................................. 41 4.1. Mô phỏng đúng theo thuật toán .......................................................... 41 4.2. Cho phép thực hiện theo từng bước .................................................... 41 4.3. Mô phỏng thuật toán phải có tính động ............................................... 41 4.4. Có thể thực thi với mọi bộ dữ liệu đầu vào ......................................... 43 4.5. Có sự phân cấp người học ................................................................... 43 5. Quy trình mô phỏng thuật toán.................................................................. 43 5.1. Nghiên cứu và phân tích giải thuật ...................................................... 43 5.2. Mô phỏng dữ liệu vào và kết quả đầu ra ............................................. 44 5.3. Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước .. 45 5.4. Tổng hợp mô phỏng theo các bước ..................................................... 47 5.5. Sơ đồ cấu trúc chung của hệ thống mô phỏng ..................................... 47 6. Đề xuất lựa chọn công cụ để phát triển chương trình mô phỏng thuật toán 48 6.1. Một số hệ thống mô phỏng thuật toán chung ...................................... 49 6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt ................................ 52 6.3. Xây dựng hệ thống từ đầu ................................................................... 53 Chương 3 PHÂN TÍCH THIẾT KẾ HỆ THỐNG MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ ....................................................................... 54 1. Mục đích ................................................................................................... 54 2. Những yêu cầu thực tế .............................................................................. 54 3. Đề xuất cho hệ thống mới ......................................................................... 55 4. Thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị ......................... 56 Trang 8
4.1. Lựa chọn công cụ lập trình ................................................................. 57 4.2. Chức năng mô phỏng của các thuật toán được cài đặt ......................... 59 4.2.1 Mô phỏng thuật toán tìm kiếm ....................................................... 59 4.2.2. Mô phỏng thuật toán Dijkstra ....................................................... 61 4.2.3. Mô phỏng thuật toán Ford – Bellman ........................................... 63 4.2.4. Mô phỏng thuật toán Prim ............................................................ 63 4.2.5. Mô phỏng thuật toán Kruskal ....................................................... 65 4.2.6. Thuật toán tìm chu trình Hamilton ................................................ 66 5. Giới thiệu chương trình ............................................................................. 66 5.1. Tổng quan về hệ thống........................................................................ 66 5.1.1. Các đối tượng xây dựng cấu trúc đồ thị ........................................ 67 5.1.2. Công cụ vẽ hình ảnh để mô phỏng ................................................ 70 5.1.3.Chức năng chi tiết của các công cụ hỗ trợ cho quá trình mô phỏng 70 5.2. Giới thiệu các công cụ hỗ trợ mô phỏng do người dùng cài đặt .......... 71 Chương 4 KẾT LUẬN ..................................................................................... 80 1. Những kết quả đạt được ............................................................................ 80 2. Hướng phát triển ....................................................................................... 81 DANH MỤC TÀI LIỆU THAM KHẢO .......................................................... 82 PHỤ LỤC ........................................................................................................ 84 Trang 9
LỜI NÓI ĐẦU Cách đây gần ba thập kỉ (khoảng những năm 80 của thế kỉ XX), ở nhiều nước trên thế giới mô phỏng thuật toán đã được sử dụng trong việc giảng dạy các môn Khoa học máy tính như một công cụ hữu hiệu để mô tả thuật toán một cách trực quan, khoa học. Không những vậy nó còn cho người học biết chi tiết từng bước hoạt động của thuật toán cùng với cấu trúc dữ liệu đi kèm thông qua việc mô tả bằng đồ họa. Những năm gần đây, ở Việt Nam môn Tin học đã được đưa vào chương trình của học sinh trung học phổ thông như là một môn học chính thức. Tuy nhiên trên thực tế, một số trường chuyên trên cả nước đã tuyển sinh học sinh chuyên Tin từ cuối những năm 80 của thế kỉ XX. Những học sinh này cần nắm chắc kiến thức cơ bản về Tin học như: các cấu trúc dữ liệu trừu tượng: stack, queue, cây, cây nhị phân, cây nhị phân tìm kiếm, các chiến lược thiết kế thuật toán: tham lam, quay lui, quy hoạch động… Trong đó, lý thuyết về đồ thị và thuật toán trên đồ thị là một lĩnh vực rộng và phức tạp. Việc hiểu và cài đặt tốt các thuật toán đó đòi hỏi thời gian và công sức rất lớn. Hiện nay, việc truyền đạt các thuật toán trên đồ thị cho học sinh chuyên Tin gặp rất nhiều khó khăn. Có nhiều rất nhiều lý do: Các thuật toán đó khó hình dung, việc tổ chức dữ liệu cho nó cũng phức tạp, thời gian giảng dạy trên lớp có hạn, tài liệu tham khảo có thể tự đọc, tự học vẫn còn ít…. Trong khuôn khổ đề tài này, chúng tôi xây dựng một chương trình nhằm mô phỏng hoạt động của ba thuật toán giải ba bài toán cơ bản trên đồ thị theo phân phối chương trình của Bộ Giáo dục với hai mục đích: để học sinh có thể dễ dàng nắm bắt tư tưởng cũng như từng bước hoạt động cụ thể của các thuật toán, để giáo viên có thể làm cho bài giảng về các thuật toán này trở nên dễ hiểu, dễ tiếp thu hơn. Nội dung luận văn được chia thành 3 chương: Trang 10
Chương I. Những kiến thức cơ bản về thuật toán. Ở chương này, chúng tôi trích nêu khái niệm về bài toán và thuật toán. Các tính chất của thuật toán, xác định độ phức tạp của thuật toán…Cuối c ùng, chúng tôi giới thiệu ba thuật toán quan trọng trên đồ thị mà học sinh THPT sẽ được học. Chương II. Mô phỏng thuật toán. Chương này chúng tôi trình bày khái niệm mô phỏng, các chức năng của mô phỏng và các vấn đề liên quan như: lịch sử mô phỏng, nghiên cứu về hiệu quả của nó trong giảng dạy và một số yêu cầu đối với việc mô phỏng thuật toán nói chung. Chương III. Phân tích thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị. Ở chương 3, chúng tôi trình bày về quá trình phân tích, thiết kế và xây dựng hệ thống mô phỏng trên ba thuật toán: thuật toán tìm kiếm (tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng), thuật toán tìm đường đi ngắn nhất (thuật toán Dijsktra) và thuật toán tìm cây khung cực tiểu trên đồ thị vô hướng có trọng số (thuật toán Prim)… Trang 11
Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN 1. Khái niệm bài toán Tin học Trong phạm vi tin học, người ta quan niệm bài toán là một công việc nào đó mà con người muốn máy tính thực hiện. [xem 1] Khi dùng máy tính để giải bài toán, ta cần quan tâm tới 2 vấn đề: Dữ liệu cần được đưa vào máy tính (Input) là gì và cần lấy ra (Output) thông tin gì? Nói một cách khác, cho một bài toán là việc mô tả rõ Input và Output của bài toán. Vấn đề còn lại là: Làm thế nào để từ Input ta có được Output? 2. Khái niệm thuật toán Khác với Toán học (các yêu cầu của bài toán thường là chứng minh sự tồn tại đáp án chứ không yêu cầu tìm một cách chi tiết để tìm ra đáp án đó), giải một bài toán Tin học là việc đi tìm một lời giải cụ thể, tường minh để đưa ra Output của bài toán dựa trên Input đã cho. Việc chỉ ra một cách tìm Output của bài toán được gọi là một thuật toán. Có nhiều cách phát biểu khái niệm về thuật toán. Dưới đây là cách phát biểu được chọn để đưa vào sách giáo khoa Tin học phổ thông: Khái niệm về thuật toán: thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự nhất định để sau khi thực hiện dãy các thao tác đó, từ input ta có output cần tìm [xem 1]. Trong lĩnh vực máy tính, cụm từ “thuật toán” đôi khi người ta dùng bằng một từ khác: “giải thuật”. Ví dụ về một thuật toán: Nhập vào một số nguyên dương N, kiểm tra số đó có là số nguyên tố hay không? Lời giải: Input: Số nguyên dương N. Output: Có/không tương ứng với N có là nguyên tố hay không? Trang 12
Ý tưởng: Một số nguyên gọi là nguyên tố khi nó chỉ có ước là 1 và chính nó. Từ định nghĩa suy ra: - Nếu N = 1 thì thông báo là N không nguyên tố rồi kết thúc; - Nếu 1< N < 4 thì thông báo N là số nguyên tố rồi kết thúc; - Nếu N  4 và không có ước trong khoảng từ 2 đến [ N ] thì N là nguyên tố. Thuật toán: Có nhiều cách mô phỏng khác nhau. Dưới đây là cách mô phỏng thuật toán dạng liệt kê các bước: Bước 1. Nhập số nguyên dương N; Bước 2. Nếu N = 1 thì thông báo là N không nguyên tố rồi kết thúc; Bước 3. Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc; Bước 4. i  2; Bước 5. Nếu i  [ N ](*) thì thông báo N là nguyên tố rồi kết thúc; Bước 6. Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc; Bước 7. i  i + 1 rồi quay lại bước 5; 3. Các tính chất của thuật toán Dựa trên khái niệm về thuật toán và ví dụ ở trên ta thấy các thao tác trong thuật toán phải được mô tả đủ chi tiết để một đối tượng cứ tiến hành thực hiện theo đúng thứ tự các thao tác đó là có thể cho ra output dựa trên input tương ứng. Một thuật toán phải đảm bảo được các tính chất sau: Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để thực hiện tiếp theo. Trang 13
Tính đúng đắn: Sau khi thực hiện thuật toán ta phải nhận được đúng Output cần tìm. Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện. Tính tổng quát: Thuật toán là đúng đắn với mọi bộ dữ liệu đầu vào của bài toán. Tính hiệu quả: - Hiệu quả về thời gian: Ta quan tâm tới thời gian cần thiết để thực hiện xong thuật toán đó. Thời gian đó phải nằm trong giới hạn cho phép. - Hiệu quả về không gian: Dung lượng bộ nhớ cần thiết để lưu trữ các đối tượng như bộ Input, bộ Output, kết quả trung gian và chương trình được dùng để thực hiện thuật toán. - Dễ cài đặt: thuật toán đó liệu có chuyển được thành chương trình bằng một ngôn ngữ lập trình nào đó hay không. Trước khi xây dựng thuật toán cho một bài toán nào đó, trước tiên phải xác định được Input và Output là gì, thử trên một số ví dụ cụ thể để định hướng cho việc xây dựng thuật toán. [xem 1] 4. Độ phức tạp và xác định độ phức tạp của thuật toán Một thuật toán chỉ có thể giải một bài toán, nhưng một bài toán có thể giải bằng nhiều thuật toán khác nhau. Làm thế nào để lựa chọn một thuật toán tốt để giải một bài toán đã cho? Tất nhiên, người lập trình thường chọn thuật toán dễ hiểu, dễ cài đặt. Theo đó, chương trình viết ra ít có khả năng có lỗi, việc nâng cấp chương trình dễ dàng và nhiều người có thể thực hiện được. Nhưng nếu hiệu quả của thuật toán (về mặt thời gian và không gian nhớ) là yêu cầu quan trọng thì cần chọn một thuật toán chạy nhanh và sử dụng tài nguyên có sẵn một cách hiệu quả. Như vậy dựa vào đâu để có thể kết luận thuật toán này “nhanh” hơn thuật toán kia? Trang 14
Có một cách để biết được thuật toán nào nhanh hơn bằng cách viết các chương trình bằng cùng một ngôn ngữ lập trình cho các thuật toán rồi so sánh trên các bộ Input giống nhau trên cùng một hệ thống để kết luận thuật toán nào nhanh, thuật toán nào chậm. Tuy nhiên cách này không chính xác và tốn nhiều thời gian. Một cách khác để đánh giá thuật toán là dựa vào tiêu chí mỗi câu lệnh của chương trình nguồn sẽ thực hiện bao nhiêu lần trên một tập dữ liệu vào. Việc đánh giá đó không chỉ đánh giá, so sánh trong việc lựa chọn thuật toán mà còn có thể hiệu chỉnh, cải tiến thuật toán đã có tốt hơn. Khi đánh giá thời gian thực hiện thuật toán ta chú ý đặc biệt đến các phép toán mà số lần thực hiện không ít hơn các phép toán khác – ta gọi là phép toán tích cực của thuật toán. Cách đánh giá thời gian thực hiện thuật toán độc lập với hệ thống máy tính dẫn đến khái niệm về Độ phức tạp của thuật toán. Thời gian thực hiện một thuật toán bằng chương trình máy tính phụ thuộc vào rất nhiều yếu tố. Một yếu tố cần chú ý nhất đó là kích thước của dữ liệu đầu vào. Dữ liệu càng lớn thì thời gian xử lý càng chậm. Nếu gọi n là kích thước dữ liệu đưa vào thì thời gian thực hiện của một thuật toán có thể biểu diễn một cách tương đối như một hàm của n: T(n). Thực tế, T(n) không những chỉ phụ thuộc vào kích thước n mà còn phụ thuộc vào đặc tính, tình trạng thực tế của bộ dữ liệu đầu vào. Ví dụ, với thuật toán sắp xếp dãy số đã cho thành dãy tăng dần thì thời gian sắp xếp còn phụ thuộc vào dãy đầu vào đã là dãy tăng dần, dãy được sinh ngẫu nhiên hay được sắp xếp theo thứ tự ngược lại. Vì thế cần phải xem xét các trường hợp tốt nhất, trung bình và xấu nhất. [Xem 2] Việc xác định độ phức tạp của một thuật toán bất kỳ có thể rất phức tạp. Tuy nhiên, trong thực tế, đối với một số thuật toán ta có thể phân tích bằng một số quy tắc đơn giản: 4.1. Quy tắc max Trang 15
Nếu thuật toán T có thời gian thực hiện T(n) =O(f(n)+g(n)) thì có thể coi T có độ phức tạp là O(max(f(n), g(n))) 4.2. Quy tắc tổng Nếu thuật toán T gồm hai đoạn thuật toán liên tiếp T1 và T2 và nếu T1 có thời gian thực hiện T1(n) = O(f(n)), T2 có thời gian thực hiện là T2(n) = O(g(n)) thì thời gian thực hiện T sẽ là: T(n) = T1(n) + T2(n) = O(f(n)+ g(n)) 4.3. Quy tắc nhân Nếu đoạn chương trình T có thời gian thực hiện là T(n) = O(f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình T với k(n) = O(g(n)) thì độ phức tạp sẽ là O(g(n).f(n)) 4.4. Một số tính chất Theo định nghĩa về độ phức tạp tính toán ta có một số tính chất: a) Nếu một thuật toán có độ phức tạp là hằng số, tức là thời gian thực hiện không phụ thuộc vào kích thước dữ liệu vào thì ta ký hiệu độ phức tạp tính toán của thuật toán đó là O(1). b) Với một thuật toán có độ phức tạp cấp logarit của f(n), người ta ký hiệu là O(logf(n)) mà không cần ghi cơ số của logarit. c) Với P(n) là một đa thức bậc k thì O(P(n)) = O(nk). Vì thế, một thuật toán có độ phức tạp cấp đa thức, người ta thường ký hiệu là O(nk) d) Một thuật toán có cấp là các hàm như 2n, n!, nn được gọi là một thuật toán có độ phức tạp hàm mũ. Những thuật toán như vậy trên thực tế thường có tốc độ rất chậm. Các thuật toán có cấp là các hàm đa thức hoặc nhỏ hơn hàm đa thức thì thường nhanh hơn các thuật toán hàm mũ. Tuy nhiên, khi chọn một thuật toán để giải một bài toán thực tế phải có một sự mềm dẻo nhất định dựa vào những điều kiện thực tế cho phép. Trang 16
Dưới đây là một số hàm số hay dùng để ký hiệu độ phức tạp tính toán và bảng giá trị của chúng để tiện theo dõi sự tăng của hàm theo đối số n. N2 N3 2n Hàm logN NlogN N 1 0 0 1 1 2 2 1 2 4 8 4 4 2 8 16 64 16 8 3 24 64 512 256 16 4 64 256 409 65536 32 5 160 1024 32768 4292967296 Ví dụ: Tính giá trị của đa thức P(x)=anxn+an-1xn-1+ ... +a1x+a0 với a0, a1, ..., an, x nhập từ bàn phím. Thuật toán 1: 1.Input n, a0, a1,a2,…an, x; 2. S:=a0; 3.for i := 1 to n do begin 3.1 p:=1; 3.2 for j := 1 to i do p:= p*x; 3.3 S:= S+ai*p; End; 4. Output s; Với mỗi giá trị i của vòng lặp 3, vòng lặp 3.2 thực hiện i vòng lặp nên khi n(n  1) n = i nó thực hiện đủ n vòng lặp. Vậy vòng lặp 3 thực hiện lần câu lệnh 2 sau do nên thời gian tính toán tỉ lệ thuận với n2. Vậy độ phức tạp tính toán của thuật toán trên là O(n2). Thuật toán 2: Vì xn =x * xn-1 nên có thể tận dụng kết quả của lần tính trước cho lần tính sau: Trang 17
1. Input n, a0, a1,a2,…an, x; 2. S := a0;P:=1; 3. for i := 1 to n do begin 3.1 P:=p*x; 3.1 S:= S+p; End; 4. Output S; Hai lệnh 2 và 4 đều có độ phức tạp tính toán là O(1). Vòng lặp 3 cần thực hiện n lần hai thao tác tính S và p.Vậy số lần thực hiện lệnh 3 là 2n. Do vậy, độ phức tạp tính toán của thuật toán trên là O(n). 5. Chi phí thực hiện thuật toán Khái niệm độ phức tạp tính toán đặt ra là để đánh giá chi phí thực hiện một thuật toán về mặt thời gian. Nhưng chi phí thực hiện thuật toán còn có rất nhiều yếu tố khác nữa: không gian bộ nhớ phải sử dụng là một ví dụ. Tuy nhiên, trên phương diện phân tích lý thuyết, ta chỉ có thể xét tới vấn đề thời gian bởi việc xác định các chi phí khác nhiều khi rất mơ hồ và phức tạp. Đối với người lập trình thì khác, một thuật toán với độ phức tạp dù rất thấp cũng sẽ là vô dụng nếu như không thể cài đặt được trên máy tính, chính vì vậy khi bắt tay cài đặt một thuật toán, ta phải biết cách tổ chức dữ liệu một cách khoa học, tránh lãng phí bộ nhớ không cần thiết. Có một quy luật tương đối khi tổ chức dữ liệu: Tiết kiệm được bộ nhớ thì thời gian thực hiện thường sẽ chậm hơn và ngược lại. Biết cân đối, dung hoà hai yếu tố đó là một kỹ năng cần thiết của người lập trình. [Xem 2] 6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường Trung học Phổ thông Chuyên 6.1. Một số khái niệm cơ bản về đồ thị 6.1.1. Khái niệm đồ thị (Graph) Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức: G = (V, E). Trong đó: Trang 18
V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh của V. Một số hình ảnh của đồ thị: Đồ thị vô hướng Đồ thị có hướng 6.1.2. Các khái niệm cơ bản Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E: Cho đồ thị G = (V, E). Ta có một số khái niệm sau [xem 3- tập 1]: Đơn đồ thị: G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v. Đa đồ thị: G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v. Đồ thị vô hướng: G được gọi là đồ thị vô hướng nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự (u, v)  (v, u) Đồ thị có hướng: G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính t hứ tự: (u, v)  (v, u). Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô Trang 19
hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, v bất kỳ tương đương với hai cung (u, v) và (v, u). Ví dụ: 3 1 2 5 4 Vô hướng Có hướng Vô hướng Có hướng Đơn đồ thị Đa đồ thị Cạnh liên thuộc, đỉnh kề, bậc Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e  E, nếu e = (u, v) thì ta nói hai đỉnh u và v là kề nhau (adjacent) và cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v. Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v, ký hiệu deg(v) là số cạnh liên thuộc với v. Dễ thấy rằng trên đơn đồ thị thì số cạnh liên thuộc với v cũng là số đỉnh kề với v. Đối với đồ thị có hướng G = (V, E). Xét một cung e  E, nếu e = (u, v) thì ta nói u nối tới v và v nối từ u, cung e là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u khi đó được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của cung e. Với mỗi đỉnh v trong đồ thị có hướng, ta định nghĩa: Bán bậc ra của v ký hiệu deg+(v) là số cung đi ra khỏi nó; bán bậc vào ký hiệu deg-(v) là số cung đi vào đỉnh đó Trang 20
Đường đi: Một đường đi độ dài k từ đỉnh u đến đỉnh v là dãy (u = x0, x1, ..., xk = v) thoả mãn (xi, xi+1)  E (là 1 cạnh của đồ thị) với i: (0  i  k). Đỉnh u gọi là đỉnh xuất phát, v gọi là đỉnh kết thúc của đường đi. Đường đi không có cạnh nào đi qua hơn 1 lần gọi là đường đi đơn. Chu trình: Đường đi có đỉnh xuất phát trùng với đỉnh kết thúc gọi là chu trình. tương tự ta có khái niệm chu trình đơn. 6.2. Bài toán tìm kiếm trên đồ thị 6.2.1. Phát biểu bài toán Cho đồ thị G = (V, E) và s và t là hai đỉnh của đồ thị. Yêu cầu: Hãy chỉ ra một đường đi từ s đến t (nếu có). Ví dụ: Xét một đồ thị vô hướng và một đồ thị có hướng dưới đây: Trên cả hai đồ thị, (1, 2, 3, 4) là đường đi đơn độ dài 3 từ đỉnh 1 tới đỉnh 4. Bởi (1, 2) (2, 3) và (3, 4) đều là các cạnh (hay cung. Làm sao để duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó? Vấn đề này đưa về một bài toán liệt kê mà yêu cầu của nó là không được bỏ sót hay lặp lại bất kỳ đỉnh nào. Vì vậy, cần phải xây dựng những thuật toán cho phép duyệt một cách hệ thống các đỉnh, những thuật toán như vậy gọi là những thuật toán tìm kiếm trên đồ thị. Trong lý thuyết đồ thị, người ta quan Trang 21
tâm đến hai thuật toán cơ bản nhất: thuật toán tìm kiếm theo chiều sâu và thuật toán tìm kiếm theo chiều rộng. 6.2.2. Giới thiệu thuật toán tìm kiếm DFS và BFS a. Thuật toán tìm kiếm theo chiều sâu DFS (Depth – First – Search) Tư tưởng của thuật toán có thể trình bày như sau: Bắt đầu từ s, mọi đỉnh u kề với s tất nhiên sẽ đến được từ s. Với mỗi đỉnh u đó, những đỉnh v kề với u cũng đến được từ s... Ý tưởng đó gợi ý cho ta viết một thủ tục đệ quy DFS(u) mô tả việc duyệt từ đỉnh u bằng cách thông báo thăm đỉnh u và tiếp tục quá trình duyệt DFS(v) với v là một đỉnh chưa thăm kề với u. Để quá trình duyệt không lặp lại bất kì đỉnh nào, ta dùng kỹ thuật đánh dấu, khi thăm một đỉnh, ta sẽ đánh dấu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không thăm lại đỉnh đó nữa. Vấn đề còn lại: Để in ra được đường đi từ đỉnh xuất phát s, trong quá trình duyệt DFS(u), trước khi gọi đệ quy DFS(v) với v là một đỉnh kề với u mà chưa đánh dấu, ta lưu lại “vết” đường đi từ u tới v bằng cách đặt trace[v] := u, tức là trace[v] là đỉnh liền trước v trong đường đi từ s tới v. Khi quá trình tìm kiếm theo chiều sâu kết thúc, đường đi từ S tới F sẽ là: t  Trace[t]  …. Trace[u1] ... Trace[s]  s. Truy ngược đường đi này sẽ cho ta hành trình đi từ s đến t. Có thể mô tả thủ tục DFS dạng giả mã như sau: Procedure DFS(uV); Begin < 1. Thông báo tới được u >; < 2. Đánh dấu u là đã thăm>; < 3. Xét mọi đỉnh v kề với u mà chưa thăm, với mỗi đỉnh v đó >; Begin Trace[v] := u; {Truy vết đường đi} DFS(v); {Gọi đệ quy duyệt bắt đầu với v} Trang 22