Đồ án Xây dựng chương trình hỗ trợ giảng dạy môn học cấu trúc dữ liệu và giải thuật

Sự ra đời của máy tính đã làm thay đổi diện mạo của cuộc sống con người. Máy tính không phải chỉ là công cụ “để tính toán cho nhanh”, mà cùng với sự phát triển như vũ bão của khoa học công nghệ, máy tính đã trở thành một công cụ đắc lực trợ giúp con người trong rất nhiều lĩnh vực. Để thực hiện một đề án tin học tức là ta phải chuyển bài toán thực tế thành bài toán có thể giải quyết trên máy tính. Mà trong một bài toán bất kỳ đều bao gồm các đối tượng dữ liệu và những yêu cầu cần xử lý trên dữ liệu đó. Vì thế trong xây dựng mô hình tin học để phản ánh bài toán thực tế cần phải chú ý đến : Một là, tổ chức biểu diễn các đối tượng thực thể, tức là phải tổ chức, xây dựng các cấu trúc thích hợp nhất để có thể phản ánh chính xác dữ liệu thực tế và có thể dễ dàng xử lý trong máy tính. Hai là, xây dựng các thao tác xử lý dữ liệu, ta tìm ra các giải thuật tương ứng để xác định trình tự các thao tác máy tính phải thực hiện. Do vậy cấu trúc dữ liệu và giải thuật là môn học rất quan trọng đối với sinh viên ngành công nghệ thông tin. Thường với những người lập trình hay có khuynh hướng chỉ chú trọng đến việc xây dựng giải thuật mà quên đi tầm quan trọng của việc tố chức dữ liệu trong bài toán. Bởi giải thuật phản ánh các phép xử lý, còn đối tượng xử lý của giải thuật lại là dữ liệu. Nên trong khi xây dựng chương trình để xác định giải thuật phù hợp cần phải biết đối tượng dữ liệu nó tác động, và khi lựa chọn cấu trúc dữ liệu cần biết những thao tác nào tác động đến nó. Ta có thể thấy mối quan hệ đó như sau : Cấu trúc dữ liệu + Giải thuật = Chương trình. Qua trên ta có thể thấy rất rõ tầm quan trọng của môn học này, để học viên có thể nắm và tiếp thu bài nhanh, ngoài việc truyền thụ trên lớp của các thầy, cô giáo theo cách thông thường, và cùng với áp dụng của khoa học kỹ thuật hỗ trợ người giáo viên trong các bài giảng của mình. Vì thế trong quá trình học tập tại trường và tìm hiểu nhu cầu cần thiết có chương trình phục vụ trong công tác giảng dạy. Trước thực tế đó nên trong quá trình làm đồ án tốt nghiệp cuối khoá, cùng với sự hướng dẫn của thầy giáo Đại tá TS. Nguyễn Nam Hồng em đã chọn đề tài “xây dựng chương trình hỗ trợ giảng dạy môn học cấu trúc dữ liệu và giải thuật ”. Nhằm hỗ trợ giáo viên trong công tác giảng dạy, truyền đạt những kiến thức đến học viên. Và mô phỏng những quá trình xử lý ví dụ trong bài học diễn ra. Như vậy cùng với kiến thức giáo viên truyền thụ, và những hình ảnh mô phỏng quá trình sẽ giúp học viên học tập đạt hiệu quả tốt hơn Mục tiêu của đề tài : - Xây dựng chương trình nhằm hỗ trợ tốt nhất quá trình giảng dạy của giáo viên. - Hỗ trợ cho học viên có thể tiếp thu kiến thức môn học nhanh nhất và nắm được vấn đề ngay tại lớp. - Nâng cao chất lượng giảng dạy và đào tạo. - Hướng phát triển của đề tài, phát triển trên mạng nhằm mục đích ứng dụng học tập trong phòng Lab và học tập trao đổi trên mạng. Hoàn thiện thành hệ thống chương trình hỗ trợ giảng dạy cho tất cả các môn học. Nội dung cần đạt được trong đồ án : - Xây dựng hệ thống cơ sở dữ liệu trên Oracle, với mục đích sử dụng lâu dài và phát triển trên mạng. - Xây dựng hệ thống chương trình giảng dạy môn học, với các thao tác linh hoạt dễ dàng. Có đầy đủ nội dung chính của môn học và các demo cần thiết. Chương trình đảm bảo cập nhật dữ liệu nhanh chóng, chính xác. Hỗ trợ truy vấn, kết xuất thông tin. - Chương trình được xây dựng trên cơ sở dữ liệu Oracle nên có thể quản lý người dùng theo từng dữ liệu riêng của họ. Nên việc phân quyền sử dụng rất thuận tiện đối với hệ thống. Công việc thực hiện đồ án sẽ đạt được những nội dung sau : (1) Khảo sát hiện trạng công tác đào tạo hiện nay. (2) Tìm hiểu chung về môn học cấu trúc dữ liệu và giải thuật. (3) Giới thiệu hệ quản trị cơ sở dữ liệu Oracle. (4) Phân tích và thiết kế hệ thống chương trình hỗ trợ giảng dạy môn học cấu trúc dữ liệu và giải thuật. (5) Tổ chức xây dựng chương trình. (6) Đánh giá, nhận xét, hướng phát triển đồ án.

doc70 trang | Chia sẻ: tuandn | Ngày: 04/05/2013 | Lượt xem: 2094 | Lượt tải: 1download
Bạn đang xem nội dung tài liệu Đồ án Xây dựng chương trình hỗ trợ giảng dạy môn học cấu trúc dữ liệu và giải thuật, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
MỞ ĐẦU Sự ra đời của máy tính đã làm thay đổi diện mạo của cuộc sống con người. Máy tính không phải chỉ là công cụ “để tính toán cho nhanh”, mà cùng với sự phát triển như vũ bão của khoa học công nghệ, máy tính đã trở thành một công cụ đắc lực trợ giúp con người trong rất nhiều lĩnh vực. Để thực hiện một đề án tin học tức là ta phải chuyển bài toán thực tế thành bài toán có thể giải quyết trên máy tính. Mà trong một bài toán bất kỳ đều bao gồm các đối tượng dữ liệu và những yêu cầu cần xử lý trên dữ liệu đó. Vì thế trong xây dựng mô hình tin học để phản ánh bài toán thực tế cần phải chú ý đến : Một là, tổ chức biểu diễn các đối tượng thực thể, tức là phải tổ chức, xây dựng các cấu trúc thích hợp nhất để có thể phản ánh chính xác dữ liệu thực tế và có thể dễ dàng xử lý trong máy tính. Hai là, xây dựng các thao tác xử lý dữ liệu, ta tìm ra các giải thuật tương ứng để xác định trình tự các thao tác máy tính phải thực hiện. Do vậy cấu trúc dữ liệu và giải thuật là môn học rất quan trọng đối với sinh viên ngành công nghệ thông tin. Thường với những người lập trình hay có khuynh hướng chỉ chú trọng đến việc xây dựng giải thuật mà quên đi tầm quan trọng của việc tố chức dữ liệu trong bài toán. Bởi giải thuật phản ánh các phép xử lý, còn đối tượng xử lý của giải thuật lại là dữ liệu. Nên trong khi xây dựng chương trình để xác định giải thuật phù hợp cần phải biết đối tượng dữ liệu nó tác động, và khi lựa chọn cấu trúc dữ liệu cần biết những thao tác nào tác động đến nó. Ta có thể thấy mối quan hệ đó như sau : Cấu trúc dữ liệu + Giải thuật = Chương trình. Qua trên ta có thể thấy rất rõ tầm quan trọng của môn học này, để học viên có thể nắm và tiếp thu bài nhanh, ngoài việc truyền thụ trên lớp của các thầy, cô giáo theo cách thông thường, và cùng với áp dụng của khoa học kỹ thuật hỗ trợ người giáo viên trong các bài giảng của mình. Vì thế trong quá trình học tập tại trường và tìm hiểu nhu cầu cần thiết có chương trình phục vụ trong công tác giảng dạy. Trước thực tế đó nên trong quá trình làm đồ án tốt nghiệp cuối khoá, cùng với sự hướng dẫn của thầy giáo Đại tá TS. Nguyễn Nam Hồng em đã chọn đề tài “xây dựng chương trình hỗ trợ giảng dạy môn học cấu trúc dữ liệu và giải thuật ”. Nhằm hỗ trợ giáo viên trong công tác giảng dạy, truyền đạt những kiến thức đến học viên. Và mô phỏng những quá trình xử lý ví dụ trong bài học diễn ra. Như vậy cùng với kiến thức giáo viên truyền thụ, và những hình ảnh mô phỏng quá trình sẽ giúp học viên học tập đạt hiệu quả tốt hơn Mục tiêu của đề tài : - Xây dựng chương trình nhằm hỗ trợ tốt nhất quá trình giảng dạy của giáo viên. - Hỗ trợ cho học viên có thể tiếp thu kiến thức môn học nhanh nhất và nắm được vấn đề ngay tại lớp. - Nâng cao chất lượng giảng dạy và đào tạo. - Hướng phát triển của đề tài, phát triển trên mạng nhằm mục đích ứng dụng học tập trong phòng Lab và học tập trao đổi trên mạng. Hoàn thiện thành hệ thống chương trình hỗ trợ giảng dạy cho tất cả các môn học. Nội dung cần đạt được trong đồ án : - Xây dựng hệ thống cơ sở dữ liệu trên Oracle, với mục đích sử dụng lâu dài và phát triển trên mạng. - Xây dựng hệ thống chương trình giảng dạy môn học, với các thao tác linh hoạt dễ dàng. Có đầy đủ nội dung chính của môn học và các demo cần thiết. Chương trình đảm bảo cập nhật dữ liệu nhanh chóng, chính xác. Hỗ trợ truy vấn, kết xuất thông tin. - Chương trình được xây dựng trên cơ sở dữ liệu Oracle nên có thể quản lý người dùng theo từng dữ liệu riêng của họ. Nên việc phân quyền sử dụng rất thuận tiện đối với hệ thống. Công việc thực hiện đồ án sẽ đạt được những nội dung sau : Khảo sát hiện trạng công tác đào tạo hiện nay. Tìm hiểu chung về môn học cấu trúc dữ liệu và giải thuật. Giới thiệu hệ quản trị cơ sở dữ liệu Oracle. Phân tích và thiết kế hệ thống chương trình hỗ trợ giảng dạy môn học cấu trúc dữ liệu và giải thuật. Tổ chức xây dựng chương trình. Đánh giá, nhận xét, hướng phát triển đồ án. Trong thời gian làm đồ án cùng với sự giúp đỡ của bộ môn khoa học máy tính - Khoa công nghệ thông tin và đặc biệt là thầy giáo : TS. Nguyễn Nam Hồng, em đã hoàn thành báo cáo đồ án tốt nghiệp của mình. Tuy nhiên không tránh khỏi những thiếu xót mong được sự quan tâm chỉ bảo của thầy giáo. Em xin chân thành cảm ơn. Dưới đây là phần báo cáo đồ án của em. KHẢO SÁT HIỆN TRẠNG CÔNG TÁC ĐÀO TẠO HIỆN NAY. Để làm cơ sở cho xây dựng được một hệ thống quy mô, chất lượng tốt đáp ứng được yêu cầu thực tế, đặc biệt yêu cầu ứng dụng ngay đối với hệ thống hỗ trợ giảng dạy môn học cấu trúc dữ liệu và giải thuật tại Học viện Kỹ thuật quân sự, chúng ta cần khảo sát kỹ hệ thống thực. Trong phần dưới đây trình bày những nét đặc trưng cơ bản của hệ thống mà ta cần khảo sát. Công tác giảng dạy chung hiện nay. Như trong thực tế ta đã thấy việc giảng dạy các môn học tại các trường đại học và cao đẳng trên toàn quốc không theo một tiêu chuẩn nào hết, mà tuỳ thuộc vào từng loại hình đào tạo, mục tiêu đào tạo của trường để có những tài liệu giảng dạy cho thích hợp với yêu cầu của trường đó. Vì thế trong một môn học mà các tác giả đề cập theo nhiều khía cạnh khác nhau nên đối với những sinh viên mới làm quen với môn học rất khó khăn trong việc lựa chọn tài liệu thích hợp để phục vụ học tập. Hiện nay đa số việc giảng dạy phổ biến là người thầy lên lớp dựa trên các tài liệu như bài giảng, tài liệu in (phục vụ cho máy chiếu ), các Slide để giảng dạy cho sinh viên. Với giáo án dưới dạng vở ghi thì việc để vẽ một hình minh hoạ giáo viên mất rất nhiều thời gian. Nếu là tài liệu in thì việc lật trang phải được thực hiện liên tục với thao tác bằng tay, tiến bộ hơn phương pháp viết bảng ở đây là không phải ghi lên bảng mà thông qua máy chiếu. Với bài giảng dưới dạng các Slide thì cần nhiều thời gian để soạn thảo và chuẩn bị bài giảng và cần phải thiết kế các Slide cho phù hợp để khi lật trang được thuận tiện. Vì thế đòi hỏi cần phải có một chương trình thật sự hữu dụng nhằm mục đích giúp người dạy và học đạt hiệu quả cao nhất. Thực tế công tác giảng dạy tại Học viện. Qua việc học tập, và khảo sát thực tế tại Học viện Kỹ thuật quân sự, thì việc giảng dạy môn học cấu trúc dữ liệu và giải thuật thường bắt đầu vào kỳ II của năm thứ hai (đối với hệ đào tạo dài hạn 5 năm). Trước đó đã được cung cấp các kiến thức về các môn học phục vụ cho môn học này như : Tin học đại cương, toán rời rạc. Môn học được giao cho giáo viên của Bộ môn Khoa học máy tính - Khoa công nghệ thông tin đảm nhiệm giảng dạy. Kế hoạch giảng dạy này được thông qua bộ môn - khoa và gửi lên Phòng đào tạo. Khi được phân công giảng dạy môn học giáo viên chuẩn bị tài liệu, tiến hành chuẩn bị bài giảng để phục vụ công việc giảng dạy của mình. Tuy nhiên do chưa thống nhất giáo trình nên với mỗi giáo viên sẽ có những tài liệu khác nhau để phục vụ việc giảng dạy. Còn học viên sẽ bị động về mặt giáo trình, nên học viên sẽ không thể tiếp cận môn học trước theo cách thức tự học ở nhà, chỉ đến khi môn học được giảng dạy giáo viên đưa ra các yêu cầu về giáo trình và tài liệu chủ yếu dùng để tham khảo thì khi đó học viên mới có thể chủ động với môn học được. Bên cạnh đó phương pháp truyền thụ còn nhiều hạn chế, kiến thức được truyền đạt chưa được hết do chỉ dùng phấn viết bảng kết hợp với bài giảng, nên nhiều thông tin cần mô phỏng trong quá trình giảng dạy sẽ không được giáo viên đưa ra, nếu có chỉ là những hình vẽ minh hoạ. Tuy vậy ở một số bộ môn hay môn học các thầy cũng đã bỏ ra công sức xây dựng các Slide hay các bài giảng in để phục vụ cho việc giảng dạy tốt hơn và có thể tiết kiệm thời gian viết bảng không cần thiết. Nhưng đó cũng chưa phải là một phương pháp thật sự tốt nhất và đáp ứng trước nhu cầu thực tế của thời đại ngày nay thời đại của công nghệ thông tin. Vì thế mà ban giám đốc đã phát động các thầy giáo và sinh viên nên xây dựng chương trình hỗ trợ giảng dạy trong học viện. Hiện nay trong trường đang có hệ thống mạng QSNET đây là mạng cục bộ của trường, nếu ta có thể cài đặt cơ sở dữ liệu các bài giảng và dùng hệ quản trị cơ sở dữ liệu Oracle thì việc quản trị dữ liệu và bảo mật rất thuận tiện. Trong hệ quản trị này với mỗi user chỉ có các quyền với cơ sở dữ liệu của chính mình, còn với cơ sở dữ liệu của các user khác sẽ không nhìn thấy và không truy nhập được. Như được biết tại giảng đường mạng đã triển khai và có các đầu ra để nối với Husb hoặc máy tính, nhưng hiện tại chưa triển khai một dự án nào phục vụ công tác giảng dạy. Khi các dữ liệu được quản lý tại máy chủ, và tại các phòng học có các thiết bị phục vụ học tập như máy tính, máy chiếu thì thầy giáo chỉ cần Login vào cơ sở dữ liệu của mình và có thể lấy bài giảng ra phục vụ cho việc giảng dạy. Đây là một xu hướng rất tốt và cần được triển khai. Với hệ thống chương trình hỗ trợ giảng dạy cần phải đạt được mục đích như thế. Xu thế của thời đại. Từ những yêu cầu trong công tác giảng dạy hiện đại thì việc xây dựng một chương trình hỗ trợ giảng dạy và học tập đối với môn học là rất cần thiết, khi đó sẽ có một giáo trình chung thống nhất để khi được phân công giảng dạy môn học, giáo viên có thể sử dụng chương trình này để giảng dạy hoặc làm tài liệu tham khảo cho công việc giảng dạy của mình. Với chương trình khi đã hoàn thành chỉ cần có máy chiếu Projector và máy tính thì công tác giảng dạy sẽ được hỗ trợ rất nhiều, các ví dụ được mô phỏng các thuật toán làm cho việc nắm bài của học viên nhanh hơn. Nếu trong phòng học chuyên dụng (Lab) thì sinh viên có thể theo dõi trực tiếp trên màn hình của mình. Vì thế với mỗi đối tượng học tập có thể thay đổi bài giảng, các mô phỏng cho phù hợp với yêu cầu giảng dạy. Qua đó ta thấy được kiến thức truyền đạt tới học viên sẽ lớn hơn rất nhiều so với công việc giảng dạy hiện nay. Học viên sẽ tiếp cận một cách trực quan hơn, kết quả học tập sẽ tốt hơn, môn học không bị nhàn chán. Vì vậy việc xây dựng một chương trình hỗ trợ giảng dạy môn học là một yêu cầu cần thiết trong công tác giảng dạy hiện đại. Qua đó nâng cao chất lượng giảng dạy cũng như đào tạo sinh viên, khi đó nó sẽ giúp tiết kiệm thời gian, công sức trong quá trình nghiên cứu tiếp cận môn học của giáo viên, sinh viên. Trong chương trình hỗ trợ giảng dạy sẽ bao gồm các đặc điểm sau : Phần lý thuyết, bao gồm đầy đủ nội dung trong môn học cần truyền đạt kiến thức đến sinh viên, có các hình ảnh và demo minh hoạ một cách trực quan, sinh động. Cuối mỗi phần lý thuyết có các bài thực hành yêu cầu cần hoàn thành để củng cố kiến thức vừa học. Do hiệu quả rất thiết thực với quá trình đào tạo, đặc biệt trong công tác giảng dạy, nó đáp ứng với yêu cầu của công cuộc giảng dạy trong tương lai có tiềm năng sử dụng lâu dài và đạt hiệu quả cao. Do nó có tính ổn định cao, có khả năng mở rộng nâng cao chất lượng phù hợp với sự phát triển của công nghệ, do được cập nhật nội dung đổi mới thường xuyên để đáp ứng với yêu cầu của môn học. Qua sự phân tích thực tế và hiện trạng trong việc giảng dạy hiện nay ta thấy được những ưu điểm mà chương trình hỗ trợ giảng dạy đem lại. Nó không chỉ là xu thế của thời đại mà nó rất thiết thực trong công tác giảng dạy hiện nay. Trong quá trình thực hiện nội dung làm đồ án em đi vào giải quyết một số vấn đề cơ bản nhất cần có trong một chương trình hỗ trợ giảng dạy môn học “cấu trúc dữ liệu và giải thuật ” và tập trung vào một số điểm sau: Nội dung lý thuyết của môn học cần giảng dạy. Các demo ví dụ cần minh học trong quá trình giảng dạy. Các bài tập thực hành, gồm cả lý thuyết và bài tập. (4) Tổ chức và thực hiện xây dựng chương trình. TÌM HIỂU CHUNG VỀ MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT. Giới hiệu môn học. Trong môn học này chúng ta sẽ làm quen với các phương pháp tổ chức và những thao tác cơ sở trên từng cấu trúc dữ liệu, kết hợp với việc phát triển tư duy giải thuật để hình thành nên chương trình máy tính. Mô tả các khái niệm cấu trúc dữ liệu, giải thuật; các phương pháp thiết kế giải thuật, mảng và danh sách tuyến tính; Stack và Queue; Cấu trúc cây, đồ thị, tìm kiếm, . . . Đây là giai đoạn thứ hai trong chu trình phần mềm tức là việc chọn lựa cấu trúc dữ liệu và thiết kế thuật toán. Vì thế môn học này là nghiên cứu một cách chi tiết hai khía cạnh nói trên của phát triển chương trình. Dữ liệu xử lý bởi chương trình cần được tổ chức thành các cấu trúc sao cho nó phản ánh mối quan hệ giữa các mục dữ liệu và cho phép xử lý dữ liệu một cách có hiệu quả. Do thế việc chọn lựa cấu trúc dữ liệu để lưu trữ chúng và việc thiết kế thuật toán để xử lý chúng không thể tách rời nhau, chúng phải được tiến hành song song. Để có thể hiểu rõ hơn ta minh hoạ quá trình tổ chức và cấu trúc hoá dữ liệu trong một vấn đề cho trước, chúng ta xét ví dụ như sau : Giả sử Hãng hàng không VietNamAriline cần điều hành một chiếc máy bay 300 hành khách. Và họ muốn hiện đại hoá công việc đó. Bước đầu tiên cần một chương trình xác định những ghế nào còn trống cho mỗi chuyến bay để có thể đặt chỗ ngồi được. Trong vấn đề này, thông tin đầu vào rõ ràng là tập hợp 300 chỗ ngồi, và đối với mỗi ghế cần có một báo hiệu ghế đó còn trống hay không. Chúng ta phải thực hiện những phép toán sau : (1) kiểm tra các ghế xem ghế nào còn trống; (2) đặt trước một chỗ ngồi; (3) xoá chỗ ngồi đã được đăng ký. Để thực hiện những phép toán trên, một cách thích hợp là các chỗ ngồi được tổ chức trong một danh sách. Theo tìm hiểu môn học có 60 tiết, trong đó bài giảng 40 tiết và thực hành 20 tiết. Khi đó cấu trúc chương trình và phân bố thời gian sẽ như sau: STT  Tên các phần chương, mục  Số tiết  Hình thức huấn luyện   1  Chương 1. Biến mảng và biến con trỏ.  4  3LT + 1TH   1.1  Khai báo mảng.  0.5    1.2  Các thao tác với mảng.  0.5    1.3  Khái niệm về biến con trỏ.  1    1.4  Làm việc với các biến con trỏ.  1    1.5  Thực hành chương 1.  1    2  Chương 2. Danh sách liên kết.  4  3LT + 1TH   2.1  Khái niệm về danh sách.  0.5    2.2  Cài đặt danh sách liên kết đơn.  0.5    2.3  Tìm kiếm trên danh sách.  1    2.4  Các loại danh sách liên kết khác.  1    2.5  Thực hành chương 2.  1    3  Chương 3. Ngăn xếp.  5  4LT + 1TH   3.1  Khái niệm về ngăn xếp.  1    3.2  Các thao tác với ngăn xếp.  1    3.3  Tính giá trị biểu thức dạng hậu tố.  1    3.4  Chuyển đổi biểu thức trung tố sang dạng hậu tố.  1    3.5  Thực hành chương 3.  1    4  Chương 4. Hàng đợi.  5  4LT + 1TH   4.1  Khái niệm về hàng đợi.  1    4.2  Các thao tác với hàng đợi.  1    4.3  Vấn đề mô phỏng các hàng đợi.  1    4.4  Các thuật toán tạo các số giả ngẫu nhiên.  1    4.5  Thực hành chương 4.  1    5  Chương 5. Các giải thuật đệ quy.  4  3LT + 1TH   5.1  Khái niệm về đệ quy.  0.5    5.2  Một số ví dụ về giải thuật đệ quy.  1    5.3  Cấu trúc chung của một thủ tục đệ quy.  1    5.4  Tính đúng đắn của các giải thuật đệ quy.  0.5    5.5  Thực hành chương 5.  1    6  Chương 6. Các thuật toán sắp xếp.  7  4LT + 3TH   6.1  Sắp xếp chọn.  1    6.2  Sắp xếp chèn.  1    6.3  Sắp xếp nổi bọt.  1    6.4  Sắp xếp nhanh (Quick Sort).  1    6.5  Thực hành chương 6.  3    7  Chương 7. Bảng băm.  6  4LT + 2TH   7.1  Khái niệm về bảng băm.  1    7.2  Các hàm băm.  1    7.3  Xích ngăn cách.  1    7.4  Dò tuyến tính.  1    7.5  Thực hành chương 7.  2    8  Chương 8. Các cấu trúc cây.  6  4LT + 2TH   8.1  Khái niệm về cây.  1    8.2  Các thao tác với cây.  1    8.3  Các phép duyệt cây.  1    8.4  Cây quyết định.  1    8.5  Thực hành chương 8.  2    9  Chương 9. Cây nhị phân.  6  4LT + 2TH   9.1  Khái niệm cây nhị phân.  1    9.2  Cây nhị phân đầy đủ.  1    9.3  Cây nhị phân hoàn toàn.  1    9.4  Cây biểu thức.  1    9.5  Thực hành chương 9.  2    10  Chương 10. Các thuật toán tìm kiếm.  7  4LT + 3TH   10.1  Tìm kiếm tuần tự.  1    10.2  Tìm kiếm nhị phân.  1    10.3  Tìm kiếm nội suy.  1    10.4  Các dạng bài toán tìm kiếm khác.  1    10.5  Thực hành chương 10.  3    11  Chương 11. Cây tìm kiếm nhị phân.  6  4LT + 2TH   11.1  Khái niệm cây tìm kiếm nhị phân.  1    11.2  Các thao tác với cây tìm kiếm nhị phân.  1    11.3  Cây cân bằng AVL.  1    11.4  Các thao tác với cây cân bằng.  1    11.5  Thực hành chương 11.  2    Trong mỗi chương đều đưa ra định nghĩa, các thuật toán (nếu có), các ví dụ đi kèm, và xây dựng các chương trình mô phỏng quá trình hoạt động của thuật toán. Sự mô phỏng được thực hiện bằng giải thuật thông qua ví dụ đã mô tả trong phần lý thuyết. Cơ sở soạn thảo nội dung của môn học dựa trên các tài liệu chính sau : (1). Lê Minh Trung, Lập trình nâng cao bằng Pascal với các cấu trúc dữ liệu, Nhà xuất bản Đà Nẵng 1997. (2). Đinh Mạnh Tường, Cấu trúc dữ liệu và thuật toán, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội 2001. (3). Đỗ Xuân Lôi, Cấu trúc dữ liệu & giải thuật, Nhà xuất bản thông kê 1996. (4). Nguyễn Trung Trực, Cấu trúc dữ liệu, Nhà xuất bản Trường Đại học Bách khoa TP. Hồ Chí Minh, 1997. Kiểu dữ liệu và cấu trúc dữ liệu. Kiểu dữ liệu và cấu trúc dữ liệu. Kiểu dữ liệu. Trong các ngôn ngữ lập trình bậc cao, các dữ liệu được phân lớp thành các lớp dữ liệu dựa vào bản chất của dữ liệu. Mỗi lớp dữ liệu được gọi là một kiểu dữ liệu. Như vậy một kiểu T là một tập hợp nào đó, các phần tử của tập hợp được gọi là các giá trị của kiểu. Khi nói đến một kiểu dữ liệu ta cần chú ý tới hai đặc trưng sau : (1). Tập hợp các giá trị thuộc kiểu. (2). Với mỗi kiểu dữ liệu, cần xác định một tập hợp nào đó các phép toán có thể thực hiện được trên các dữ liệu của kiểu. Kiểu dữ liệu đơn : các giá trị của kiểu này được xem là các đơn thể đơn giản nhất không thể phân tách thành các thành phần đơn giản hơn được nữa. Cấu trúc dữ liệu. Khi giải quyết bài toán phức tạp, chỉ sử dụng các dữ liệu đơn là không đủ, ta phải cần đến các cấu trúc dữ liệu. Một cấu trúc dữ liệu bao gồm một tập hợp nào đó các dữ liệu thành phần, mà chúng được liên kết với nhau theo một phương pháp nào đó. Các dữ liệu thành phần có thể là dữ liệu đơn, hoặc cũng có thể là một cấu trúc dữ liệu đã được xây dựng. Các kiểu dữ liệu cơ bản trong ngôn ngữ Pascal. Kiểu integer ( Số nguyên). Kiểu integer gồm tập hợp con của các số nguyên có độ lớn từ -32768 (215) đến +32767 (215 - 1). Kích thước lưu trữ 16 bit. Kiểu real( số thực). Kiểu real gồm một tập hợp con của các số thực có độ lớn từ -263 đến +263 - 1. Kích thước lưu trữ 64 bit. Kiểu boolean. Kiểu boolean gồm hai giá trị True hoặc False. Kiểu char( Ký tự). Kiểu char gồm một tập hợp các ký tự in được. Các ký tự thường dùng là: 26 chữ Latin, 10 ký tự số, một số ký tự đặc biệt. Kiểu liệt kê. Kiểu liệt kê gồm một tập hợp các giá trị bằng cách liệt kê các danh hiệu chỉ định các giá trị này. Kiểu liệt kê được định nghĩa như sau : Type T =(c1,c2, . . ., cn). Trong đó c1, c2, . . ., cn là các danh hiệu chỉ định các giá trị của kiểu. Kiểu đoạn con. Có trường hợp một biến có giá trị chỉ nằm trong một khoảng xác định nào đó của một kiểu. Được định nghĩa như sau : Type T = min . . max. Trong đó min, max là những giới hạn của kiểu miền con. Kiểu String. Kiểu chuỗi gồm một tập hợp các chuỗi ký tự. Các chuỗi ký tự này được ghi trong hai dấu nháy đơn (‘) và có tối đa 255 ký tự. Các kiểu dữ liệu đệ quy trong ngôn ngữ Pascal. Kiểu mảng (array). Giả sử T0 là một kiểu đã cho, ta sẽ gọi T0 là kiểu thành phần mảng. Giả sử I là một kiểu đoạn con hoặc kiểu liệt kê, ta sẽ gọi I là kiểu chỉ số mảng. Khi đó ta có thể tạo nên kiểu mản

Các file đính kèm theo tài liệu này:

  • docprint DA.doc
  • docbiachinh.doc
  • docbiaphu.doc
  • docMr Tan - NhiemVu.doc
  • docoracle.doc