Tài liệu Báo cáo tốt nghiệp phong cách lập trình

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Ж  KHOA TOÁN – CƠ – TIN _____________ Bài thu hoạch Tổng kết các bài báo cáo nhóm Giảng viên: Nguyễn Thị Bích Thủy Sinh viên : Nguyễn Thị Linh Lớp : K52A3 TT Ứng Dụng Hà Nôi, Năm 2009 1 Danh sách các nhóm: 1. Nguyễn Văn Đức 2. Bách-Phượng-Mai Phong cách lập trình Phân tích bài toán theo modul 3. Nghĩa-Hưng-Học Đặc tả hình thức trong phân tich hệ thống 4. Nguyệt-Sính-T.T.Trang Cấu trúc dữ liệu và cách sắp xếp(Dịch ) 5. Thơm-T.T.Hiền-Dung Cây nhị phân 6. Nhung-Thủy Thuật toán đồ thị (Dịch sách) 7. Đạt-Hiếu-Đ.Q-Hưng 8. P.T.Hiền-Thư-Vân Thuật giải Heuristic và phương pháp tìm kiếm. Thuật toán tìm kiếm trên đồ thị 9. Chiến-Hoàng-N.K.Anh Quy hoach động 10. Lê.T.Long-Hiệp Kỹ thuật chia để trị (dịch sách) 11. Liên-Hiên-Hà Chia để trị 12. Tình-Thay-Thể Bảng băm 13. N.T.Linh-N.Đ.Giang-T.K.Anh Tổng quan kỹ thuật đệ quy 14. Quyền-Phú-Thành Kỹ thuật sắp xếp trong lập trình 15. Cường-L.T.Trang-B.K.Linh Bài toán liệt kê 16. K.Dương-N.TrungLâm-Thắng Thủ thuật sử dụng thư viện đồ họa 17. Hạnh-Đỗ.T.T.Hiền-Lâm Các phương pháp lập trình 18. Nhân-Hoa-Sơn Lập trình hướng đối tượng 19. Tuấn-Thiện-Xuất Kiểm chứng chương trình 20. Lê.N.Duy-T.V.Tài Kiểm chứng chương trình 2 21. L.V.Hùng-Đ.Long-N.V.Hùng Quan máy học 22. Phạm Thanh Hòa Lập trình điều khiển trên máy CNC 23. Ngọc-N.P.Long-L.Đ.Long Ứng dụng ngắt trong lập trình nhúng 3 MỤC LỤC 1 Phần 1:Phong cách lập trình.........................................................5 Phong cách lập trình (Nguyễn Văn Đức)....................................................5 Phần 2:Các giai đoạn phần mềm..................................................7 1 Giai đoạn phân tích bài toán................................................7 1.1 Phân tích bài toán theo Modul ...........................................................7 2 Giai đoạn thiết kế bài toán....................................................8 2.1 Các công cụ thiết kế............................................................................8 2.2 Các ngôn ngữ đặc tả.............................................................................8 2.2.1Đặc tả hình thức trong phân tích hệ thống.........................................8 3 Giai đoạn viết mã lệnh........................................................10 3.1 Tính chất dữ liệu................................................................................10 3.1.1 Cấu trúc dữ liệu và cách sắp xếp (Dịch )...........................................10 3.1.2 Cây nhị phân........................................................................................11 3.2 Thuật toán ..........................................................................................12 3.2.1 Thuật toán đồ thị(dich).......................................................................12 3.2.2 Thuật giải Heuristic và phương pháp tìm kiếm................................13 3.2.3 Thuật toán tìm kiếm trên đồ thị.........................................................14 3.3 Kỹ thuật lập trình...............................................................................16 3.3.1 Quy hoach động...................................................................................16 3.3.2 Kỹ thuật chia để trị (dịch sách)..........................................................17 3.3.3 Kỹ thuật chia để trị.............................................................................17 1 Trên đây là mục lục bản báo cáo, em đã cố phân loại đẻ có cái nhì khái quát về các bài báo cáo của các nhóm 4 3.3.4 Bảng băm.............................................................................................18 3.3.5 Tổng quan kỹ thuật đệ quy................................................................19 3.3.6 Kỹ thuật sắp xếp trong lập trình........................................................20 3.3.7 Bài toán liệt kê.....................................................................................21 3.3.8 Thủ thuật sử dụng thư viện đồ họa....................................................22 3.4 Phương pháp lập trình.......................................................................23 3.4.1 Các phương pháp lập trình................................................................23 3.4.2 Lập trình hướng đối tượng.................................................................24 4 Kiểm chứng..........................................................................25 4.1 Kiểm chứng chương trình(nhóm Tài-Duy …)..................................25 4.2 Kiểm chứng chương trình(nhóm Tuấn …).......................................25 5 Ứng dụng..............................................................................26 5.1 Lập trình điều khiển trên máy CNC..................................................26 5.2 Quan máy học.....................................................................................27 5.3 Ứng dụng ngắt trong lập trình nhúng...............................................28 5 Tổng kết các bài báo cáo Trước thế kỷ của công nghệ thông tin bùng nổ rộng khắp, nhu cầu sử dung máy tính ngày càng tăng lên, đòi hỏi ngày càng nhiều các ứng dụng chương trình. Vì vậy, sự ra tăng số lương các phần mềm ứng dụng ngày càng nhiều, và thu hút nhiều người làm việc trong lĩnh vực này. Nhu cầu học tập cũng tăng lên với nhiều môn học. Tuy nhiên, để có thể lập trình tốt chúng ta không thể nào không học và tìm hiểu về Kỹ Thuật Lập Trình Trong học kỳ qua, dưới sự nỗ lực học tập và tìm hiểu của bản thân, em và các bạn đã tìm hiểu được nhiều kỹ thuật để học và chia sẻ cho nhau.Dưới đây là bản tổng kết về kết quả làm việc của các bạn và sự thu nhận kiến thức của bản thân. Phần 1:Phong cách lập trình I. Bài báo cáo: Phong cách lập trình NTH: Nguyễn Văn Đức a. Tóm tắt báo cáo: Bài báo cáo có những nội dung chính sau:  Tên hàm hay tên biến  Tên hàm: nêu cách đặt tên và yêu cầu của tên( nhất quán...)  Tên biến: cách đặt tên  Biểu thức và phát biểu Để tạo sự tường minh cho biểu thức nên: Canh chỉnh lề, dùng dấu ngoặc để tránh tối nghĩa, đơn giản cụ thể hóa biểu thức và mang tính tự nhiên  Tính nhất quán và các đặc ngữ Tính nhất quán giúp ta xây dựng được các chương trình tốt, sáng sủa. Để tạo được sự nhất quán : canh chỉnh lề, dùng dấu ngoặc móc, đặc ngữ  Các số tối nghĩa: Trong phần này nêu được khái niệm số tối nghĩa, cách đặt tên và các quy tăc hạn chế dùng số tối nghĩa  Chú thích.  Khái niêm chú thích:  Quy tắc  Không chú thích những điều hiển nhiên.  Chú thích cho hàm và dữ liệu toàn cục.  Đừng chú thích những đoạn mã nguồn dở mà hãy viết lại nó.  Đừng phủ nhận mã nguồn.  Rõ ràng, không gây nhầm lẫn.  Vì sao phải lo lắng về phong cách lập trình?  Mã nguồn chương trình được viết tốt sẽ dễ đọc và dễ hiểu hơn, hầu như lỗi ít hơn, và giúp chương trình có kích thước nhỏ hơn so với mã nguồn được chắp vá cẩu thả và không hề trau chuốt.  Quan điểm cơ bản tạo phong cách lập trình tốt là thói quen b. Nhận xét Đọc bài báo cáo tôi có nhân xét sau:  Đề tài: Phong cách lập trình luôn đi kèm với phong cách cá nhân, luôn thể hiện “cái tôi” của người lập trình. Tuy nhiên, không phải vì thế mà nó không có 6 những quy tắc chung mà hơn thế, nhờ những quy tắc đó mã nguồn sẽ sáng sủa, dễ hiểu, ít lỗi và dễ sửa chữa vì thế luôn là một vấn đề cần được chú ý. Dẫu vậy, rất ít người, đặc biệt là những người mới bước vào nghề lập trình để ý tới. Vì thế, theo tôi, đề tài này rất lý thú, đáng lưu ý; bài báo cáo này có thể giúp bạn có một phong cách lập trình chuyên nghiệp, nhưng cũng mang đậm phong cách cá nhân.  Ưu điểm:  Qua bản báo cáo, về cơ bản người đọc có thể hình dung một phần về phong cách lập trình làm sao cho code được sáng sủa, dễ hiểu.  Nêu được mục đích, ý nghĩa sự cần thiết của phong cách lập trình  Nhược điểm  Bản báo cáo không cho thấy được cái nhìn khái quát về phong cách lập trình giúp lập trình hiệu quả.  Bài báo cáo rất sơ sài, nhiều vấn đề cần được bổ sung, thêm mới  Trình bày rất lủng củng, lộn xộn thiếu sự rõ ràng, VD: Nhìn từ mục lục ta thấy: sau khi người viết nói rất nhiêu về quy tắc viết: hàm, biến, biểu thức v.v.v. cuối cùng đề cập đến vì sao phải lo lắng về phong cách lập trình. Trong khi đó, vấn đề này nên được nói ngay từ đầu Thêm vào đó, đề tài là phong cách lập trình nhưng ngay khi bắt đầu bài báo cáo đã đề cập luôn đến: hàm, biến, biểu thức…Khiến người đọc, đặc biệt là người mới học, có thể thắc mắc không hiểu sự liên quan gì của những vấn đề này tới phong cách lập trình  Trong nhiều phần, nội dung trong từng tựa đề không thấy được sự liên quan rõ ràng hay làm sáng tỏ tựa đề, những tiểu ý để lẫn lộn với ý lớn khiến người đọc không hiểu phần này định làm sáng tỏ ý lớn nào, hoặc hai phần của một ý phải viết liền thì chia ra như hai ý riêng biệt. VD: Trong phần, các số tối nghĩa có chia làm ba ý lớn.  Đặt tên cho các số tối nghĩa.  Dùng các hằng số dạng ký tự, không dùng dạng số nguyên.  Dùng chính ngôn ngữ đó để tính toán kích thước của đối tượng. Trong khi đó, hai nội dung cuối cùng làm sáng tỏ cách hạn chế dùng số tối nghĩa. Vì thế nên cho hai ý này thành ý nhỏ trong ý lớn: các quy tắc hạn chế dùng số tối nghĩa.  Bổ sung.  Bài báo cáo nên được trình bày và đề cập đến nội dung sau: a) Vì sao phải lo lắng về phong cách lập trình:  Mục đích của phong cách lập trình  Lợi ích của việc áp dụng các quy tắc lập trình b) Các yếu tố của phong cách lập trình tốt: oTrình bày mã nguồn:  Quy tắc lùi đầu dòng  Quy tắc viết code theo hàng dọc 7  Quy tắc xuống dòng, khoảng trống  Quy tắc dùng tab  Quy tắc chú thích oQuy tắc đặt tên, logic và các kỹ thuật cao  Cách nhận biết kiểu và tên hàm người lập trình định nghĩa: hàm, thủ tục, tên biến, biểu thức và phát biểu, các số tối nghĩa,  Cách dung giá trị bolean trong câu trúc  Cách viết câu lênh so sánh tối ưu  Cách viết cấu trúc vòng lặp tối ưu oPhong cách lập trình nên đảm bảo: Tính nhât quán.v.v.  Trong mỗi phần đề cập tới nên nêu ra: khái niệm, quy tắc VD: trong Biểu thức và phát biểu:  Khái niệm về biểu thức và phát biểu  Cách trình bày và quy tắc thể hiện biểu thức… Phần 2:Các giai đoạn phần mềm 6 Giai đoạn phân tích bài toán I.1. Bài báo cáo: Phân tích bài toán theo modul NTH:Nguyễn Quang Bách-Dương Thị Phương Mai-Nguyễn Thị Ánh Phượng I.1.1.Tóm tắt:nội dung chính: Trong thực tế, để giải quyết những bài toán lớn, chương trình phức tạp, do đó kỹ thuật phân tích bài toán theo module ra đời.  Khái niệm: kĩ thuật thiết kế phần mềm chia chương trình thành những thành phần riêng biệt (những module) được nối vào chương trình chính thông qua các giao diện  Triển khai bài toán theo module:  Phân tích bài toán xác định các module  Xác định input và ouput cho từng module  Tạo mối liên hệ giữa các module  Liên kết tất cả các module với chương trình chính :  Đánh giá kỹ thuật o Ưu điểm  Hạn chế và dễ phát hiện lỗi  Giữ được điều khiển trên từng hàm  Chương trình có cấu trúc dễ viết, dễ bảo dưỡng o Nhược điểm  Dễ làm mất tính thống nhất trong nhóm  Mất nhiều thời gian để sửa chữa chuong trình. 8 o Kỹ thuật liên quan: Chia để trị và lập trình hướng đối tượng(OOP) I.1.2. Nhận xét:  Về đề tài: Đây là một đề tài khá quen thuộc, tương đối gần gũi. Nội dung khá cơ bản, không có gì nổi bật, khác lạ.  Về ưu điểm: o Nổi bật được các bước triển khai bài toán theo modul o Nêu được ưu, nhược điểm của kỹ thuật o Trình bày khá thoáng, dễ đọc, ví dụ đơn giản luôn lấy ra ngay khi phân tich một vấn đề giúp nắm bắt nội dung  Về nhược điểm: o Đôi chỗ trình bày rất lủng củng, lộn xôn, tách và ghép ý lung tung, không làm nổi bật được các ý chính, khó khăn trong việc thu nhận thông tin : VD phần nhược điểm o Việc đề cập các kỹ thuật liên quan(cụ thể là KT OOP) nhưng chưa cho thấy sự liên quan của KT đó với việc phân tích bài toán theo modul . Mặt khác OOP một kỹ thuật lập trình hoàn toàn độc lập so với kỹ thuật phân tích bài toán theo Module. o Chưa đưa ra được kỹ thuật sử dụng các biến riên, biến cục, để tạo sự thống nhất trong các modul. Hay phạm vi áp dụng, ngôn ngữ dùng… o Chưa đưa ra được cách sử dụng kỹ thuật modul trong một project lớn  Bố sung: o Cần nói rõ hơn về các kỹ thuật liên quan o Bổ sung thêm về vấn đề sử dụng hàm biến , cách làm việc với nhiều Modul trên nhiều tệp rời rạc của một project lớn. o Nói thêm về vấn đề phạm vi sử dụng Lập trình Modul : ngôn ngữ chấp nhận một cách chính thức khái niệm Modul gồm có: IBM/360 Assembler, COBOL, RPG và PL/1, Ada, D, F, Fortran, Haskell, Pascal(vài phiên bản ML, Modula-2, Erlang, Perl, Python and Ruby. Hệ thống IBM (aka AS/400 and iSeries) cũng sử dụng Modules trong RPG, COBOL và CL, khi lập trình trong môi trường ILE I. Giai đoạn thiết kế bài toán II.1. Bài báo cáo: Ngôn ngữ đặc tả UML (Unifield Modeling Language ) NTH: Lê Văn Hưng-Nguyễn Tiến Nghĩa-Vữ Thái Học II.1.1.Tóm tắt: Trong bài báo cáo này ta nắm được a. Sự ra đời của ngôn ngữ UML: b. Khái niệm UML UML là một ngôn ngữ mô hình hoá thống nhất có phần chính bao gồm những ký hiệu hình học, được các phương pháp hướng đối tượng sử dụng để thể hiện và miêu tả các thiết kế của một hệ thống. Nó là một ngôn ngữ để đặc tả, trực quan hoá, xây dựng và làm sưu liệu cho nhiều khía cạnh khác nhau của một hệ thống có nồng độ phần mềm cao. UML có thể được sử dụng làm công cụ giao tiếp giữa người dùng, nhà phân tích, nhà thiết kế và nhà phát triển phần mềm. 9 Ngôn ngữ mô hình hoá bao gồm các ký hiệu và một tập các quy tắc:Syntactic (Cú pháp) Semantic (Ngữ nghĩa) và Pragmatic, c. Các thành phần chủ yếu của ngôn ngữ UML  Hướng nhìn (view): Khái niệm và các loại hướng nhìn (Use case, logic...)  Biểu đồ (diagram): Khái niệm và các loại biểu đồ (Use case, lớp…)  Phần tử mô hình hóa (model element):  Cơ chế chung: d. Khả năng mở Rộng UML và sự phát triển công cụ trợ giúp trong UML e. Ứng dụng vào quá trình xây dựng phần mềm(4 giai đoạn và thử nghiệm) II.1.2. Nhận xét:  Đề tài: Mặc dù UML đã xuất hiện từ lâu với những ứng dụng hiệu quả của nó đến nghành công nghệ phần mềm, nhưng không phải ai cũng biết đến, đặc biệt là các bạn sinh viên, Vì thế, đây là một đề tài khá mới mẻ, lý thú, có sự hấp dẫn cao  Ưu điêm của bài báo cáo:  Bài báo cáo được viết khá toàn diện, cơ bản và chi tiết về UML, giúp người đọc có sự hiểu biết khá đầy đủ về UML.  Trình bày tương đối rõ ràng, mạch lạc, khoa học. Lý thuyết đi kèm hình ảnh minh họa giúp người đọc dễ nắm bắt nội dung.  Ví dụ đưa ra và cách phân tích ví dụ khá tôt, phản ánh và củng cố được nội dung lý thuyết.  Nhược điểm:  Chưa đưa ra được sự khác biệt giữa UML và sự thiết lập biểu đồ của một hệ thống.  Chưa đưa được nhận xét về ưu, nhược điểm của ngôn ngữ UML, và so với các ngôn ngữ khác,  Bổ sung: bài báo cáo nên cần được bổ sung thêm để có kiến thức hoàn chỉnh .  Trong thành phần chủ yếu của ngôn ngữ UML, phần biểu đồ: có thể nói UML (2.0) có 13 kiểu đồ thị với ba loại khác nhau:  Biểu đồ tĩnh hay cấu trúc (Structure diagrams): gồm biểu đồ lớp; đối tượng; thành phần; biểu đồ cấu trúc hỗn hợp; biểu đồ khai triển; biểu đồ gói  Biểu đồ động(Behavior diagrams): Biểu đồ hoạt động; Biểu đồ trạng thái; Biểu đồ Use case.  Biểu đồ tương tác(Interaction diagrams): Biểu đồ giao tiếp; Biểu đồ miêu tả tương tác; Biểu đồ trình tự; Biểu đồ định giờ.  Bổ sung thêm phần nhược điểm hay sự thiếu xót của UML:  Khả năng hình dung, tưởng tượng yếu (Weak visualization)  Khó khăn trong việc học và tiếp thu (Problems in learning and adopting)  Chỉ có duy nhất một mã đồng bộ với mã đó (Only the code is in sync with the code)  Tích trữ lại sự mở rộng và sự mở rộng kết hợp ( mà không dùng đến) (Cumulative Impedance/Impedance Mismatching)  Có sự mâu thuân về mặt thẩm mỹ (Aesthetically Inconsistent) 10  Cố gắng đem đến tất cả mọi thứ cho tất cả các nhà lập trình (Tries to be all things to all programmers)  Bổ sung thêm phần ưu điểm UML:  Cung cấp cho người sử dụng một ngôn ngữ mô hình hoá trực quan có sẵn và gợi tả  Cung cấp các kỹ thuật chuyên môn mở rộng để mở rộng các khái niệm cốt lõi (core concepts)  Độc lập với các ngôn ngữ lập trình riêng biệt (particular) và các tiến trình phát triển  Những điểm ngoài phạm vi UML  UML không là một phương thức  UML không xác định/hướng vào (address) toàn bộ quá trình  UML không quy định cách tiếp cận vào việc xác định các lớp,các phương thức và phân tích các mô hình...  UML không bao gồm bất kỳ quy tắc thiết kế hay cách thức giải quyết vấn đề nào II. Giai đoạn viết mã lệnh III.1. Bài báo cáo: Cấu trúc dữ liệu và cách sắp xếp (Dịch ) NTH: Nguyễn Thị Nguyệt, Bùi Thị Sính, Trần Thị Thu Trang II.1.1. Tóm tắt: Bài dịch này nói về nội dung chính sau a. Cấu trúc dữ liệu và cách phân loại Những điểm mấu chốt trong chương :  Xây dựng các thuật toán qua các cấu trúc dữ liệu(CTDL) để có một cấu trúc cân đối và một sự thực thi tốt.  Lựa chọn cần phải kỹ càng, tránh nhầm CTDL cho công việc  Sự sắp xếp, phân loại nằm ở trung tâm của nhiều thuật toán khác nhau.  Sự sắp xếp có thể được minh họa chủ yếu bằng các mô hình thiết kế thuật toán. Kĩ thuật cấu trúc dữ liệu, chia để trị, thuật toán ngẫu nhiên.v,v,v. Các loại dữ liệu chủ yếu  Containers: Khái niệm, chức năng, thao tác căn bản và các loại phổ biến của Containers  Dictionary: Khái niệm, chức năng, thao tác căn bản của Dictionary  Binary Search Trees (cây tìm kiếm nhị phân( BST)): Cấu trúc BTS và thuật toán dung đệ quy tìm kiếm trong cây nhị, và nhiệm vụ của BST (hỗ trợ tất cả các thao tác Dictionary nhanh chóng)  Priority Queues ( Hàng đợi ưu tiên): Ưu điểm, và nhiệm vụ của Priority Queues:chèn, tìm hoặc xóa giá tri max, min Cấu trúc dữ liệu chuyên sâu (specializer data structeres)  Cấu trúc dữ liệu tập hợp ( Set data structures)  Cấu trúc dữ liệu kiểu hình học(Geometric data structures)  trúc dữ liệu đồ họa( Graph data structures)  Cấu trúc dữ liệu kiểu xâu (Strings data structures) 11 b. Cách sắp xếp và phân loại: Lý do cần sắp xếp(4 lý do) Ứng dụng của sắp xếp: tìm kiếm, cặp gần nhau nhất, phần tử đơn nhất . sự phân phối thường xuyên, sự lựa chọn, những vỏ lồi Phương pháp sắp xếp: Cấu trúc dữ liệu, Chèn tăng, chia để trị, Kĩ thuật BUCKETING, Thuật toán ngẫu nhiên II.1.2. Nhận xét  Ưu điểm:  Bản dịch tương đối sát nghĩa, nêu được nội dung của phần dịch, biết chọn nghĩa từ sao để đảm bảo đúng thuật ngữ khoa học. Có thể nhận thấy người dịch có am hiểu hoặc cố gắng tìm tòi các vấn đề liên quan đến nội dung để dịch chuẩn.  Trình bày bản dich và bài báo cáo tương đối tốt, dễ đọc, dễ hiểu nội dung phần dịch  Nhược điểm:  Vân còn một số chỗ dịch lủng củng, không thoát ý, dịch theo kiểu word by word, nên có thể gây đến nội dung dich không đúng Vì đây là bản dich nên tôi chỉ khuyên rằng nên dịch nhiều hơn và tìm hiểu về nội dung dich sẽ có bản dich tốt hơn Có thể nói đây là bản dịch tốt nhất trong tât cả các nhóm tham gia dich bài III.2. Bài báo cáo: Cây nhị phân NTH: Trần Thị Thơm- Trịnh Thị Hiền- Đỗ Thùy Dung II.2.1. Tóm tắt: a. Cây Định nghĩa: Cây là cấu trúc dữ liệu có thứ bậc, lưu trữ 1 tập các phần tử, mỗi phần tử có 1 giá trị và trừ gốc, nó được trỏ và có thể trỏ đến 1 hay nhiều phần tử khác. Một số khái niệm cơ bản về cây: bậc của một node,của một cây,node gốc,node lá, node nhánh, mức, chiều dài, chiều cao của cây b. Cây nhị phân( Binary Tree-BT) Định nghĩa: một dạng của cấu trúc cây mà mọi node trên cây chỉ có tối đa 2 node con. Một số định nghĩa khác về cây nhị phân: theo DS liên kết, DS tuyến tính Đặc tính quan trọng của cây nhị phân: hai cây nhị phân tuơng tự và cây nhị phân tương đương Một số dạng đặc biệt của cây nhị phân: Biểu diễn cây nhị phân: theo DS liên kết, DS tuyến tính Các thao tác trên cây nhị phân: Cấp phát bộ nhớ,giải phóng node, tạo node,xoá node, khởi tạo cây nhị phân, kiểm tra tính chất cây nhị phân c. Phép duyệt cây nhị phân Là phương pháp thăm các node có hệ thống chỉ một lần. Có 3 phép duyệt cây nhị phân đó là: 12  Duyệt theo thứ tự trước ( Preorder Traversal);  Dưyệt theo thứ tự giữa ( Inorder Traversal);  Duyệt theo thứ tự sau ( Postorder Traversal); d. Nhận xét về cây nhị phân  Ưu điểm: trong một số trường hợp dùng cây nhị phân tìm kiếm nhanh hơn danh sách tuyến tính  Nhược điểm: dung đến thuât toán đệ quy III.2.2. Nhận Xét  Về đề tài: Đây là một đề tài khá quen thuộc, gần gũi, được nhiều người biết đến  Ưu điểm: Là một bài báo cáo khá đầy đủ và chi tiết về cây nhị phân. Cho thấy cái nhìn toàn diện về cây nhị phân.  Nhược điểm:  Trình bày thiếu khoa học, lộn xộn: phân chia đề mục không rõ ràng  Trong mốt số đề mục chưa nói tới nội dung cần đề cập => gây cảm giác dường như đề mục và nội dung không liên quan đến nhau  Đặc tính quan trọng của cây nhị phân: nêu khái niệm về hai cây nhị phân tuơng tự và cây nhị phân tương đương. Nội dung và đề mục dường như không liên quan.  Phần ưu, nhược điểm, không rõ ràng, chính xác, nói đúng hơn là nội dung phần này chưa đi đến ý cần nói, mới chỉ phần rìa của nó  Trong phần ứng dụng của cây nhị phân, nêu lên cây mã tiền tố ,cây biểu thức là chưa chính xác, vì hai loại cây này là một loại của cây nhị phân, mà không đề cập gi đến ứng dụng của cây nhị phân cả.  Bổ sung  Bổ sung thêm phần mục lục, sặp xếp lại các đề mục: o Phân định nghĩ và một số định nghĩa khác về cây nhị phân nên để gần nhau chứ không để cách quãng bởi các đề mục khác o Trong các thao tác trên cây nhị phân: nên viết như sau chứ không nên để chúng nằm ngang hang nhau(lấy ví dụ phần xoá) 1) Xóa node: a. Xóa node gốc b. Xóa node con bên trái c. Xóa node con bên phải  Có thể bổ sung thêm các loại cây nhị phân o Cây mã Huffman o Cây biêu thức o Cây mã tiền tố.v.v.  Nên viết lai và bổ sung về ưu và nhược điểm. của cây nhị phân  Nên viết lại và bổ sung thêm ứng dụng của cây nhị phân. o Tìm kiếm. 13 o o Ứng dụng trong tính toán Ứng dụng trong kỹ thuật mật mã III.3. Bài báo cáo: Thuật toán đồ thị NTH: Trần Thị Thanh Nhung-Nguyễn Thu Thủy II.3.1. Tóm tắt: Nội dung cần nắm được:  Đồ thị có thể mô hình hóa các cấu trúc, mối quan hệ đa dang và rộng rãi.  Được thiết lập một cách đúng đắn, hầu hết các ứng dụng của đồ thị có thể giảm bớt thuộc tính chuẩn và dùng các thuật toán phổ biến,  Tìm kiếm theo chiều ngang và chiều sâu cung cấp cho thiết bị máy duyệt các đỉnh và cạnh của đồ thị. Chứng tỏ giải thuật đồ thị hiệu quả và đơn giản  Đồ thị bạn bè( Friendship graph) Thông qua bài toán Friendship graph, nói đến các loại đồ thị(vô hướng, có hướng, trọng sô) , mảng liên thông, thành phần liên thông, bậc của một đỉnh, đồ thị con, chu trinh, chu trinh đơn, chu trinh halminton  Cấu trúc dữ liệu cho đồ thị: dùng danh sách kề và ma trận kề. So sánh 2 cấu trúc này với nhau  Duyệt đồ thị: Duyêt theo chiều sâu và chiều rộng:  Ứng dụng đồ thị :  Mảng liên thông  Tìm cây và chu trình.  Đồ thị có sắc số bằng 2.  Phân loại theo hình học Topo.  Đỉnh khớp.  Vấn đề mô hình hóa đồ thị  Các bài toán đồ thị điển hình: cây bao trùm nhỏ nhất( TT Prim và kruskas và đường đi ngắn nhất( TT Dijksas- Flow) II.3.2.Nhận xét  Ưu điểm Về cơ bản, bản dich nói chung là được, thể hiên được nội dung phần dịch  Nhược điểm Người dịch mới chỉ đơn thuần dịch theo kiểu word by word, nhiều chỗ cho thấy chưa hiểu hết nội dung, kiến thức ngoại ngữ chưa đủ: chưa nắm vững từ loại, các kiểu từ ghép trong câu…, văn phong (lựa chọn nghĩa không hợp) nên nhiều chỗ dich chưa chính xác, không thoát ý, tối nghĩa. Trình bày báo cáo chưa đạt phong cách văn bản  Bổ sung Một lời khuyên dành cho nhóm là nên tìm thêm tài liệu thông tin để hiêu nội dung phân dich, trau dồi kiến thức để lựa chọn nghĩa từ và biêt loại từ để dịch cho chuẩn xác. 14 III.4. Bài báo cáo: Thuật giải Heuristic và phương pháp tìm kiếm NTH: Đậu Quang Hưng-Đỗ Tiến Đạt-Nguyễn Hữu Hiếu III.4.1. Tóm tắt  Các nguyên lý cơ bản của giải thuật Heuristic: oKhái niệm thuật giải Heuritic: một sự mở rộng khái niệm thuật toán oXây dựng thuật giải Heuristic cần dựa vào các nguyên lý cơ bản: nguyên lý vét cạn thông minh, nguyên lý tham lam Greedy, hàm Heuristic, nguyên lý thứ tự  Các phương pháp tìm kiếm Heuristic. o Cấu trúc chung của bài toán tìm kiếm: tập hợp trạng thái-nút đồ thị o Tìm kiếm chiều rộng (BFS) o Tìm kiếm chiều sâu (DFS) o Tìm kiếm leo đồi:  Hàm Heuristic:là một hàm xác định ước lượng chi phí để biến đổi từ trạng thái này sang trạng thái khác  Tìm kiếm leo đồi đơn giản:một kiểu DFS nhưng không sử dụng kĩ thuật quay lui mà là một hàm Heuristic để tính toán lựa chọn trạng thái tiếp theo Tư Tưởng: chọn con đường tốt hơn đầu tiên thấy để đi.  Leo đồi dốc đứng:chọn con đường tốt nhất trong tất cả con đường tốt hơn để đi  Nhược điểm của tìm kiếm leo đồi:có thể không tìm ra kết quả do không gian tìm kiếm: có điểm cực đại địa phương hoặc có đoạn đơn điệu ngang o Tìm kiếm ưu tiên tối ưu (BFS): nêu lên tư tưởng và các cài đặt BFS  Thuật giải AT: là phiên bản của BFS với độ tốt của trạng thái là tổng chiều dài đã đi từ trạng thái bắt đầu đến trạng thái hiện tại; nêu lên cách cài đặt AT  Thuật giải AKT:mở rộng của TG AT, bằng việc thêm hàm ước lượng  Thuật giải A*:cải tiến của thuật giải AKT dùng để áp dụng cho đồ thị. III.4.2.Nhận xét  Về đề tài: Đây là một thuật giải áp dụng cho trí tuệ nhân tạo, nên rất mới mẻ, khá hấp dẫn, nhưng cũng khó tiếp cận  Ưu điểm:  Trình bày khoa học  Nội dung chính xác và khá đầy đủ và cơ bản  Nhược điểm:  Chưa nêu được nhược điểm của thuật giải Heuristic  Chưa nêu được ứng dụng của thuật giải Heuristic trong thực tiễn  Chưa so sánh giữa các phương pháp tìm kiếm  Bổ sung  Bổ sung thêm nhược điểm của thuật giải Heuristic  Bổ sung thêm so sánh giữa các phương pháp tìm kiếm  Nêu lên mối tương quan giữa các phương pháp tìm kiếm Heuristic: 4 kiểu tìm kiếm chiều rộng (BFS),chiều sâu (DFS), leo đồi và tối ưu (BFS): có thể xem như là 4 thái cực của không gian liên tục bao gồm các chiến lược khác nhau. 15  thuật giải Heuristic và các phương pháp tìm kiếm Heuristic ứng dụng trong Trí tuệ nhân tạo III.5. Bài báo cáo: Thuật toán tìm kiếm trên đồ thị NTH: Phạm Thanh Hiền-Bùi Thị Thư-Hà Thị Thanh Vân III.5.1. Tóm tắt  Các khái niêm cơ bản oĐịnh nghĩa đồ thị: 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 oPhân loại đồ thị:  Dựa vào số lượng, có hai loại: Đơn đồ thị và Đa đồ thị  Dựa vào đặc tính, có hai loại: Đồ thị vô hướng và Đồ thị có hướng oĐường đi ,tính liên thông trong đồ thị oBiểu diễn đồ thị: có 3 kiểu là ma trận kê,danh sách kề và danh sách cạnh  Thuật toán tìm kiếm trên đồ thị: oThuật toán tìm kiếm theo chiều sâu (DFS):cài đặt chương trình dưa vào đệ quy và không đệ quy-ngăn xếp(tư tưởng và xây dựng thuật giải hai cách này) oThuật toán tìm kiếm theo chiều rộng (BFS): cài đặt chương trình dưa vào hang đợi và thuật toán loang(tư tưởng và xây dựng thuật giải hai cách này) oĐộ phức tạp của DFS và BFS  Biểu diễn đồ thị bằng danh sách kề, cả hai thuật toán BFS và DFS đều có độ phức tạp tính toán là O(n+m)= O(max(n,m))  Biểu diễn đồ thị bằng ma trận kề thì độ phức tạp tính toán là O(n+n 2)= O(n2).  Biểu diễn đồ thị bằng danh sách cạnh, nó có độ phức tạp tính toán là O(n.m) III.5.2 Nhận xét  Về đề tài: Đây là một đề tài khá quen thuộc, gần gũi, nhìn chung không có điểm gì mới.  Ưu điểm  Trình bày rõ ràng, mạch lạc , khoa học, logic, dễ tóm lược thông tin.  Nội dung chính xác, cơ bản, phân tích vấn đề logic.  Nhược điểm:  Chưa nêu cụ thể được ứng dụng của thuât toán tìm kiếm đồ thị trong thực tế chứ không phải qua một sô bài tập.  Chưa nêu được ưu nhược điểm, va sự tương quan giứa hai cách tìm kiếm trên đồ thị  Bổ sung:  Đưa thêm ứng dung thuật toán tìm kiếm đô thị: du lịch, lĩnh vực trí tuê nhân tạo  Nêu ra ưu nhược điểm, sự tương quan giữa BFS và DFS III.6. Bài báo cáo: Quy hoạch đông 16 NTH: Nguyễn Văn Chiến- Nguyễn Hữu Hoàng-Nguyễn Thị Kim Anh III.6.1. Tóm tắt:  Giới thiệu chung: một phương pháp chia nhỏ bài toán, tổ hợp kết quả, tương tư như chia để trị, áp dụng hữu hiệu cho bài toán tối ưu  Kĩ Thuật quy hoạch động o Nguồn gốc:nhà toán học người Mĩ Richard Bellman phát minh,năm 1953. o Khái niệm: là KTLT chia bài toán lớn-> bài toán nhỏ,lời giải bài toán nhỏ lưu vào bảng phương án để tổ hợp tìm kết quả ban đâu. o Bản chất: Chia cắt bài toán lớn thành nhỏ, ghi nhớ và tổ hợp kết quả o Đặc điểm căn bản (2): cấu trúc con tối ưu và bài toán con gối nhau o Phương pháp tiếp cận: từ dưới lên (Bottom-up), từ trên xuống (Top-down) o Quy trình triển khai(4 bước):  Bước 1 : Xác định cấu trúc con tối ưu  Bước 2 : Xác định hàm hồi quy của nghiệm tối ưu.  Bước 3 : Tính giá trị của nghiệm tối ưu theo Bottom-up hoặc top-down.  Bước 4 : Xây dựng lại nghiệm tối ưu từ thông tin đã tính toán ở bước 3. oƯu điểm :  Giảm thiểu tối đa dung lượng bộ nhớ cần sử dụng.  Giảm thiểu tối đa độ phức tạp thuật toán và thời gian tính toán  Khả năng áp dụng cao, cho nhiều bài toán phức tạp.  Là phương pháp tuyệt vời cho nhiều bài toán tối ưu. III.6.2 Nhận xét  Về đề tài: Đây là đề tài khá quen thuộc nhưng khó tiếp cận vói một số người học  Ưu điểm  Là một bài báo cáo khá hoàn chỉnh, đầy đủ và chi tiêt, nổi bật được vấn đề. Giúp người đọc dễ dàng nắm bắt nội dung  Trình bày rõ ràng, mạch lạc, tính khoa học cao  Biết lựa chọn và phân tích ví dụ khá rõ ràng, chi tiết góp phần cung cố nội dung  Nhược điểm  Chưa làm nổi bật được sức manh của phương pháp trên các vấn đề lớn và các bài toán thực tế  Chưa nêu được nhược điểm của kỹ thuật  Bổ sung  Nên đưa thêm việc triển khai kỹ thuật trong các bài toán thực tế , vấn đề lớn  Nêu ra nhược điểm của kỹ thuật  Các thuật toán sử dụng quy hoạch động: o Thuật toán xử lý xâu ký tự o Thuật toán CYK xác định xem một xâu cho trước có thể được sinh từ một ngữ pháp phi ngữ cảnh (context-free grammar) o Thuật toán Viterbi 17 o Thuật toán Earley o Thuật toán Needleman-Wunsch và các thuật toán sắp chuỗi o Các thuật toán dung trong đồ thị như: thuật toán Bellman-Ford, thuật toán Dijkstra, thuật toán Floyd: o Tối ưu hóa thứ tự của phép nhân ma trận theo chuỗi (chain matrix multiplication) o Thuật toán tổng tập con (subset sum) (Theo wikipedia) III.7. Bài báo cáo: Chia để trị (dịch sách) NTH: Lê thành Long-Lưu Hoàng Hiệp III.7.1. Tóm tắt Một giải pháp hữu hiệu nhất cho các kỹ thuật giải quyết vấn đề là chia chúng thành những vấn đề nhỏ hơn, dễ giải quyết hơn  Chương trình Quy hoạch động oHàm fibonaci: oNhững Vấn Đề Về Phân Vùng: một bài toán đặt ra là phân vùng S vào phạm vi K sao cho cân bằng công việc và giảm thiểu thời gian xử lý oKhoảng Ăn Khớp Các Ký Tự: Chương trình, dựa vào thuật toán quy hoạch động, chia để trị, tim ra lỗi chính tả oDãy Tăng Lớn Nhất oPhép Đạc Tam Giác:của một đa giac là một tập các tam giác không giao nhau mà tổng không gian các tam giác này bằng đa giác ban đầu oHạn chế của chương trình Quy hoạch động  Chia để trị oSự Mũ Hoá Nhanh oTìm Kiếm Nhị Phân III.7.2 Nhận xét  Ưu điểm  Về cơ bản, bản dịch tương đối sát nghĩa  Nội dung phần dịch nói chung là phản ánh được  Nhược điểm  Còn rất nhiều chỗ dịch chưa được chuẩn, dịch theo kiểu word by word, tối nghĩa, câu cú lủng củng, ngang tai (mang văn phong nói, sử dụng từ thừa thãi ) Lấy một ví dụ đơn giản: Phần nhóm dịch: Để có được công việc thực hiện công bằng và hiệu quả, các sách sẽ được chia đều trong ba công nhân. Để tránh phải sắp xếp lại những cuốn sách hay chia chúng thành phần nhỏ , sẽ là đơn giản nhất để chia giá sách thành ba khu vực và phân công mỗi khu vực vào một trong những công nhân. 18 Theo ý cá nhân tôi: Để công việc được thực hiện công băng và hiệu quả…hay chia chúng ra, đơn giản nhất là chia giá sách thành ba khu và phân môi khu một công nhân Nên cố găng dịch nhiều hơn để có văn phong chính xác, hợp lý III.8. Bài báo cáo: Chia để trị NTH: Nguyên Thị Hiên-Trần Kim Liên- Đỗ Ngọc Hà III.8.1. Tóm tắt  Ý tưởng và nội dung của thuật toán chia để trị oChia bài toán lớn thành bài toán nhỏ cùng dạng dễ giải để tìm KQ bài toán đầu oNội dung:  Phân tích bài toán đã cho thành các bài toán cơ sở  Tổng hợp kết quả từ bài toán cơ sở để có lời giải của bài toán ban đầu.  Các bài toán minh hoạ và các ví dụ  Thuật toán tìm kiếm nhị phân  Bài toán Min & Max  Thuật toán Quick Sort ….  Đánh giá thuật toán:  Ưu điểm: là phương pháp tối ưu giải một số bài toán lớn, đồ sộ  Nhược điểm: Sử dụng đệ quy lên tốn bộ nhớ III.8.2 Nhận xét Về đề tài: là một đề tài quen thuộc gần gũi, được nhiều người biết đến và sử dụng  Ưu điểm:  Trình bày khá thoáng, dễ đọc  Nhược điểm  Nội dung báo cáo còn sơ sài  Nêu quá nhiều bài toán chỉ để thể hiện việc áp dụng thuật toán chia để trị  Bổ sung  Nên bổ sung thêm  nguồn gốc: Ý tương thuật toan có tư Babylonia I, trước công nguyê, nhưngJohn Mauchly đưa ra sự miêu tả thuật toán năm 1946  bản chất  đặc điểm căn bản,  quy trình triển khai thuật toán  Thay vì chỉ nêu các bài toán mà không phản ánh được gì, ta có thể sửa bổ sung như sau:Các nguyên tắc có thể dung chia nhỏ bài toán:  Nguyên tắc chia đôi: bài toán Min Max, tìm kiếm nhị phân…  Nguyên tắc phân hoạch: Thuật giải quicksoft …  Bổ sung thêm phần ưu điểm:  19  Là thuật toán tích hợp một cách tự nhiên cho các thi hành trong máy đa xử lý, đăc biệt là hê thống chia sẻ bộ nhớ  Thuật toán làm tăng hiệu quả sử dụng bộ nhớ  Có sự kiểm soát toàn diện chương trình cho ra kết quả chính xác (Theo wikipedia) III.9. Bài báo cáo: Bảng băm NTH: Hoàng Thị Tình- Trần Thị Thay- Nguyễn Thị Thể III.9.1. Tóm tắt  Nguồn gốc: xuất hiện những năm 50 của thế kỷ 20, dựa trên ý tưởng: biến đổi giá trị khóa thành một số,sử dụng số này đánh chỉ mục cho bảng dữ liệu  Hàm băm: là ánh xạ giá trị từ khóa vào một dãy các địa chỉ của bảng băm  Bảng băm: là kĩ thuật chia nhỏ khóa, bằng cách khác nhau rồi trộn phối hợp lại,trích ra 1 mã đại diện Mô tả cấu trúc bảng băm tổng quát: hàm băm, tập khóa, tập địa chỉ Các phép toán trên bảng băm: thêm phần tử (insert), loại bỏ (remove), tìm kiếm  Các phương pháp, thuật toán giải quyết xung đột trên bảng băm  Phương pháp kết nối trực tiếp  Phương pháp kết nối hợp nhất  Phương pháp dò tuần tự(tuyến tính)  Phương pháp dò bậc hai  Phương pháp băm kép Nêu lên nội dung, các hàm thực hiện và đánh giá về phương pháp  Đánh giá về bảng băm: phụ thuộc vào dung lương bộ nhớ o Ưu điểm :  Cấu trúc dung hòa giữa thời gian truy xuất và dung lượng bộ nhớ:  Bảng băm thích hợp tổ chức dữ liệu có kích thước lớn, lưu trữ ở bộ nhớ ngoài. o Nhược điểm: Gây xung đột địa chỉ o Ứng dung: bài toán kinh điển và trong lĩnh vực mật mã III.9.2 Nhận xét Về đề tài: đây là một đề tài khá  mới mẻ, hay, lôi cuốn Ưu điểm: o Bài trình bày khoa học, dễ đọc, dễ hiểu, nêu bật được vấn đề o Nội dung khá đầy đủ, cơ bản, chính xác  Nhược điểm o Chưa phân tích được việc sử dụng kỹ thuật trong bài toán cụ thể để làm rõ vấn đê o Chưa đưa ra lý do tại sao có xung đột trong bảng băm.  Bổ sung o Nêu nguyên nhân xảy ra xung đột trên bảng băm: trong thực tế bảng băm có thể ánh xạ nhiều giá trị từ khóa tới cùng một chỉ số nào đó, tức lưu các dữ liệu đó  20