Bao Cao Cuoi Ky Ii

ĐẠ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. 2. 3. 4. 5. 6. 7.

Nguyễn Văn Đức Bách-Phượng-Mai Nghĩa-Hưng-Học Nguyệt-Sính-T.T.Trang Thơm-T.T.Hiền-Dung Nhung-Thủy Đạt-Hiếu-Đ.Q-Hưng

8. 9. 10 . 11 . 12 . 13 . 14 . 15 . 16 . 17 . 18 . 19 . 20 . 21 . 22 . 23 .

P.T.Hiền-Thư-Vân Chiến-Hoàng-N.K.Anh Lê.T.Long-Hiệp

Phong cách lập trình Phân tích bài toán theo modul Đặc tả hình thức trong phân tich hệ thống Cấu trúc dữ liệu và cách sắp xếp(Dịch ) Cây nhị phân Thuật toán đồ thị (Dịch sách) 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ị Quy hoach động Kỹ thuật chia để trị (dịch sách)

Liên-Hiên-Hà

Chia để trị

Tình-Thay-Thể

Bảng băm

N.T.Linh-N.Đ.Giang-T.K.Anh Tổng quan kỹ thuật đệ quy Quyền-Phú-Thành

Kỹ thuật sắp xếp trong lập trình

Cường-L.T.Trang-B.K.Linh

Bài toán liệt kê

K.Dương-N.TrungLâm-Thắng Thủ thuật sử dụng thư viện đồ họa Hạnh-Đỗ.T.T.Hiền-Lâm

Các phương pháp lập trình

Nhân-Hoa-Sơn

Lập trình hướng đối tượng

Tuấn-Thiện-Xuất

Kiểm chứng chương trình

Lê.N.Duy-T.V.Tài

Kiểm chứng chương trình

L.V.Hùng-Đ.Long-N.V.Hùng

Quan máy học

Phạm Thanh Hòa

Lập trình điều khiển trên máy CNC

Ngọc-N.P.Long-L.Đ.Long

Ứng dụng ngắt trong lập trình nhúng

2

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:

6

 Đề 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ó 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: o Trì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 o Quy 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 o Phong 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 I. 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 II. 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 III. 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 Ứng dụng trong tính toán o Ứ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: o Khái niệm thuật giải Heuritic: một sự mở rộng khái niệm thuật toán o Xâ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ể 15

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. • 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 o Phâ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ị o Biể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ị: o Thuậ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) o Thuậ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+n2)= 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

16

III.6. Bài báo cáo: Quy hoạch đông 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ự 17

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 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 o Hàm fibonaci: o Nhữ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ý o Khoả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ả o Dãy Tăng Lớn Nhất o Phé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 o Hạn chế của chương trình Quy hoạch động  Chia để trị o Sự Mũ Hoá Nhanh o Tì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 18

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. 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ị o Chia 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 o Nộ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 … 19

• Bổ sung thêm phần ưu điểm:  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

20

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 đó trong cùng một thành phần mảng, mà mỗi thành phần mảng chỉ cho phép lưu một dữ liệu=> xung đột o Bổ sung một bảng băm tốt để ta cố gắng tạo được: • Tính được dễ dàng và nhanh các địa chỉ ứng với từ khóa • Đảm bảo ít xảy ra xung đột o Đưa ra một số bảng băm và cách cài đặt • Cài đặt bảng băm địa chỉ mở • Cài đặt bảng băm dây chuyền

III.10. Bài báo cáo: Tổng quan kỹ thuật đệ quy NTH: Nguyễn Đức Giang- Trần Thị Kim Anh- Nguyễn Thị Linh III.10.1. Tóm tắt  Kỹ thuật đệ quy 1. Khái niệm kỹ thuật đệ quy:Là kỹ thuật có hàm có lệnh gọi lại hàm đó.

phân loại đệ quy: dựa vào tiêu chí có 2 kiểu( trực tiêp, gián tiếp) hoặc 4 kiểu đệ quy( tuyến tính, phi tuyến, nhị phân, hỗ tương ) 2. Cơ chế thực hiện giải thuật đệ quy:Đưa bài toán lớn về bài toán nhỏ nhất để tính rồi lấy kết quả tính ngược trở lại 3. Phương pháp sử dụng kỹ thuật đệ quy trong một bài toán  Thông số hóa bài toán.  Phát hiện trương hợp suy biến.  Phân tích bài toán theo phương thức đệ quy 4. Ưu và nhược điểm Ưu điểm : làm chương trình,mã nguồn trở lên ngắn gọn Nhược điểm: Tốn bộ nhớ, mất nhiều thời gian và giảm tốc đô xử lý,  Khử đệ quy 1. Tổng quan về vấn đề giải thuật đệ quy 2. Các trường hợp khử đệ quy đơn giản.  Trường hợp khử đệ quy bằng vòng lặp.  Khử đệ quy hàm đệ quy arsac.  Khử đệ quy một số dạng thủ tục đệ quy thường gặp

III.10.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 và sử dụng khá nhiều  Ưu điểm o Bài trình bày tương đối khoa học, 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 Hơi quá ôm đồm khi trình bày cả đệ quy và khử đệ quy o Cơ chế thực hiện giải thuật đệ quy chưa được phân tích sâu  Bổ sung 21

o Nên trinh bày một trong hai vân đề đệ quy và khử đệ quy o Trong phần cơ chế thực hiện giải thuật đệ quy có thể bổ sung: • Cớ cấu ngăn xếp cho lần gọi hàm : Khi một hàm gọi một hàm khác, tất cả các trạng thái hàm gọi đang có cần được khôi phục sau khi hàm được gọi kết thúc. Trạng thái đó gồm có:điểm quay về, các giá trị trong thanh ghi, các trị trong biến cục bộ và các tham trị của nó. Như vậy môi hàm cần có một vùng nhớ dành riêng cho nó. Vùng nhớ này tồn tại suốt thời gian hàm thực hiện cho đến khi kết thúc công việc. Nhiệm vụ của máy tính là đưa vung nhớ tạm này vào một danh sách có cung • Cách lưu giá trị hàm trong bộ nhớ, trên các thanh ghi o Các cách thực hiên của đệ quy • Thực hiện đa xử lý: thực hiện đồng thời • Thực hiện đơn xử lý: o Nên đưa ra trường hợp để phân tích nên hay không nên sử dụng đệ quy o So sánh giữa đệ quy và không đệ quy

III.11. Bài báo cáo: Kỹ thuật sắp xếp trong lập trình NTH: Ngô Thế Quyền-Nguyên Việt Phú-Nguyên Trung Thành III.11.1. Tóm tắt  Đặt Bài Toán Sắp xếp là quá trình bố trí lại vị trí các phần tử của 1 tập đối tượng nào đó theo thứ tự nhât định. Bài toán sắp xếp xuất hiện trong nhiều lĩnh vực Tập đối tượng cần sắp xếp có nhiều dạng khác nhau=> Có nhiều thuật toán sắp xếp khác nhau  Các Thuật Toán Sắp Xếp:Nêu ý tưởng, cài đặt và độ phức tạp của TT o Sắp xếp chọn(sellectionsort):chọn phẩn tử thỏa yêu cầu nhất đưa lên vị trí đầu o Sắp xếp nổi bọt (Bubblesort):duyệt từ cuối lên đầu, gặp hai khóa kế cận bị ngược thứ tự thì đổi chỗ o Sắp xếpChèn:từng phần tử so sánh với các PT trong dãy, sẽ sắp đúng vào dãy o Thuật toán SHELLSORT:chia nhỏ dãy ra sắp xếp rồi ghép lại= dãy săp xếp o Thuật toán sắp xếp kiểu phân đoạn ( QUICKSORT): một phương pháp sắp xếp tôt nhất, dựa vào việc chọn khóa để sắp xếp dãy theo khóa chốt đó o Vài cải tiến của QuickSort o Thuật toán kiểu vun đóng (HEAPERT)  Tính ổn định của thuật toán sắp xếp: bảo toàn thứ tự ban đầu của các bản ghi mang khóa bằng nhau trong danh sách. Nói chung các thuật toán ko đảm bảo tính ổn định nhưng có thể biến đổi để trở thành ổn định  Đánh giá thuật toán: các thuật toán có ưu,nhược khác nhau, no ưu điểm chung là nhanh

III.11.2 Nhận xét  Về đề tài: là một đề tài khá gần gũi  Ưu điểm: 22

o Từ trước, các thuật toán sắp xếp được người lập trình biết khá rời rạc, vi thế có thể thấy bài báo cáo viết khá chi tiết, có tính tổng quát và khái quát cao. o Trình bày báo cáo rõ ràng mạch lạc, có tính khoa học cao  Nhược điểm  Bổ sung Nói chung, bài báo cáo không cần bô sung gi nhiều o Có thể bổ sung về bài toán sắp xếp: bài toán săp xếp chia làm hai loại • Sắp xếp trong: săp xếp các phần tử có trong bộ nhớ • Sắp xếp ngoài: săp xếp các phần tử được lưu ở các thiết bị lưu trữ ngoài o Thao tác cơ bản của thuật toán sắp xếp là so sánh và đổi chỗ

III.12. Bài báo cáo: Bài toán liệt kê NTH: Nguyên Mạnh Cường –Lê Thu trang-Bùi Khánh Linh III.12.1. Tóm tắt Trong thực tế, có một số bài toán muốn biết có bao nhiêu đối tượng và tìm ra đối tượng thỏa mãn điều kiện nào đó -> đếm cấu hình tổ hợp,bài toán liệt kê tổ hợp Phương pháp liệt kê là phương kế cuối cùng để giải bài toán tổ hợp hiện nay  Nhắc lại một số kiến thức tổ hợp  Phương pháp sinh: có thể áp dụng để giải bài toán liệt kê tổ hợp nếu: • Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê • Xây dựng được thuật toán từ cấu hình chưa phải cấu hình cuối, Liệt kê theo thứ tự từ điển:áp dụng liệt kê tập con k phần tử và một số bt #  Thuật toán quay lui: dùng để giải bài toán liệt kê các cấu hình;là Phương pháp giải quyết vấn đề là thử và sửa. Áp dụng cho bài toán hoán vị.v.v  Kỹ thuật nhánh cận:là kỹ thuật giúp tận dụng những thông tin đã tìm được để loại bỏ sớm những phương án chắc chắn không phải tối ưu->kết quả nhanh

III.12.2 Nhận xét  Về đề tài: đây là đề tài nghe đến khá nhiều, nhưng nói chung đối với sinh

viên ít người biết đến một cách đây đủ.  Ưu điểm: o Trình bày khá sáng sủa, rõ ràng mạch lạc, nổi bật được vấn đề->dễ nắm bắt thông tin o Nội dung bài báo cáo khá đầy đủ, phân tích tốt các ví dụ làm nổi bật các phương pháp.  Nhược điểm o Chỉ để ý nhiều vào việc phân tích các bài toán áp dụng , không nói nhiều về kỹ thuât.  Bổ sung Nên miêu tả kỹ thuật kỹ hơn, đưa thêm độ phức tạp của kỹ thuật,một vài đánh giá nhận xét về kỹ thuật.

23

•

Để diễn tả giải thuật quay lui, ta sử dụng cấu trúc cây ghi lựa chọn đã thực hiện,gọi là cây không gian trạng thái • Nếu nút cây không gian trạng thái có trung binh a nút con thì độ phức tạp của giải thuật quay lui là an

III.13. Bài báo cáo: Sử dụng thư viện đồ họa NTH: NguyênTrung Lâm–Kiều Văn Dương-Nguyễn Xuân Thắng III.13.1. Tóm tắt  Đồ thị cơ bản:Một tệp ảnh là một tập hợp của nhiều pixel hay điểm bởi một

màu sắc nhất định nào đó. Mọi hình ảnh đều có dạng hình chữ nhật và có cạnh dài và ngắn nhất định, được tạo bởi một matrix của pixels.  Image – formate:có 3 dịnh dạng hình ảnh thường dung là gif , jpeg , png Dùng hàm imagecreate (int x_size,int y_size) tạo ảnh có kích thươc x và y  Sử dụng ảnh đã có:tạo một ảnh trống. có thể lấy ảnh từ đĩa qua các hàm sau:  Ressource imagecreatefromjpeg (string filename)// ảnh dạng jpeg.  Ressource imagecreatefrompng (string filename)// ảnh dạng png.  Truy tim kích thước của tệp ảnh: bằng việc sử dụng các hàm sau cho ta thông tin kích thước ảnh: getimagesize ( ) hoặc imagesx( ) và imagey( )  Copy và bóp ảnh  Để phối màu cho ảnh ta có thể: Pha màu, Hoà màu, Thay đổi màu, Tô màu và Làm màu vô sắc.  Tạo hình căn bản  Đường thẳng: imageline(resounrce image,int x1,int y1,int x2,int y2,int col)  Hình chữ nhật: dùng hàm này làm ảnh có hình chữ nhật imagerectangle(resource image,int x1,int y1,int x2,int y2,int col)  Hình góc:hàm imagepoligon(resource image, array points,int num_points  Tạo hình võng:hàm image(int cx,int cy,iny w,int h,int s,int e,int col)

III.13.2 Nhận xét  Về đề tài: là một đề tài không rõ ràng cụ thể, không hiểu sử dụng thư viện đồ

họa cho cái gì, thuộc lĩnh vực nào  Ưu điểm Đề cập được các tác vụ với ảnh và các hàm cần dùng  Nhược điểm o Trình bày thiếu khoa học, phân chia ý không rõ ràng, tiếng anh xen tiếng việc không cần thiết, gây phản cảm. o Không nêu được ứng dụng của việc sử dụng thư viên đô họa  Bổ sung o Nhìn từ mục lục ta có thể chỉnh sưa như sau: 1. Đồ họa cơ bản (thay vì cơ bản graphics) 2. Định dạng hình ảnh (thay vì Image-formate.) 3. Sử dụng ảnh đã có. 4. Truy tim kích thước của tệp ảnh. 5. Copy và chỉnh sửa ảnh (thay vì Copy và bóp ảnh.) 6. Tô màu  pha màu. 24

 Hoà màu.  Thay đổi màu.  Làm màu vô sắc. 7. Tạo hình căn bản.  Đường thẳng.  Hình chữ nhật.  Hình góc.  Tạo hình võng.. 8. Vẽ chữ. o Nêu lên ứng dụng của việc sử dụng thư viên đô họa: trong thiết kế web, lĩnh vực liên quan đến ảnh:

III.14. Bài báo cáo: Các phương pháp lập trình NTH: Phạm Hồng Hạnh-Đỗ Thị Thu Hiền-Nguyễn Thị Lâm III.14.1. Tóm tắt  Trừu tượng hóa trong lập trình: một phương pháp giúp người lập trình biết

cách tập trung vào những vấn đề.Có hai kiểu trừu tượng hoá quá trình , trừu tượng hóa dữ liệu  Lập trình logic:  Ngôn ngữ Prolog: ngôn ngữ cấp cao, ngôn ngữ miêu tả và không có tính thủ tục  Cú pháp Prolog( 7 phần): Vị từ ; mệnh đề ; vị từ nhát cắt và fail;khai báo kiểu dữ liệu do người dùng định nghĩa(bằng từ khóa domains); danh sách(gồm hai phần:đầu và đuôi);cấu trúc tổng quát của chương trình prolog ; những đặc điểm cơ bản( so trùng và đệ quy)  Lập trình hàm:NNLT hàm thiết kế dựa trên các hàm toán học Hàm toán học: là khái niệm cơ bản trong các ngôn ngữ hàm Bản chất của ngôn ngữ lập trình hàm:mô phỏng các hàm toán học nhiều nhất cóthể  Lập trình thủ tục(LTTT):là kiểu lâp trình mà một thủ tục chính được viết để khởi động tiến trình và các luồng con gọi thực hiện các thủ tục con Lập trình cấu truc: tập con của LTTT, có 3 cấu trúc: trình tự, quyết định, vòng lặp  Lập trình hướng đối tượng(OOP): là phương pháp lập trình lấy hướng đối tượng làm nền tảng để xây dựng thuật giải và chương trình Các đặc trưng cơ bản: Sự đóng gói/che dấu thông tin, tính kế thừa, tính đa hình Các nguyên lý trong OOP: open- close, nghich đảo phụ thuộc,.thay thế Lisko v.v.

III.14.2 Nhận xét  Về đề tài:là một đề tài khá đồ sồ, đề cập đến nhiều phương pháp lập trình nên

vừa mới lại vừa gần gũi và rất hấp dẫn  Ưu điểm o Là bài báo đầy đủ, chi tiết, nội dung lớn,và đề cập khá toàn diện về các vấn đề của các phương pháp lập trình o Trình bày khá tốt, rõ ràng mạch lạc, chuẩn xác  Nhược điểm 25

o Vì là một đề tài khá đồ sồ, nên thiếu phần mục lục là một vấn đề đáng quan

tâm, gây khó khăn trong việc nhìn tổng quát về bài báo cáo gồm nhưng nội dung gì  Bổ sung o Cần bổ sung phần mục lục vào bài báo cáo o Nên có sự so sánh giưa các phương pháp lập trình o Bổ sung thêm ứng dụng cho các phương pháp lập trình

III.15. Bài báo cáo: Lập trình hướng đối tượng NTH: Nguyễn Văn Nhân- Phạm Thị Mai Hoa-Nguyên Đức Sơn III.15.1. Tóm tắt  Đặt vấn đề: Lập trình tuyến tính có nhiều hạn chế: Không sử dụng lại được các đoạn mã Không có khả năng kiểm soát phạm vi truy xuất dữ liệu; Mọi dữ liệu là toàn cục dễ bị ảnh hưởng=> Lập trinh hướng đối tượng là một phương pháp khắc phục nhược điểm trên  Nội Dung: o Lập trinh HĐT:là phương pháp thiết kế & pháy triển phần mềm dựa trên lớp và đối tượng. o Đối tượng:Thực thể phần mềm bao bọc thuộc tính và phương thức o Class:là thiết kế định nghĩa thuộc tính, phương thức cho đối tượng cùng loại Thành viên lớp t h u ộ c một trong ba loại quyền Public, protected, private • Hàm khởi tạo: Khai báo,cấp phát bộ nhớ cho đối tượng • Hàm hủy: Hủy bỏ đối tượng, giải phóng bộ nhớ • Phạm vi lớp: • Lớp con:Kế thừa thuộc tính,phương thức của lớp khác • Lớp cha:Lớp chia sẻ sự kế thừa o Thuộc tính:Biến, dữ liệu. o Phương thức: Các hàm của đối tượng o Thông điêp: là một lời yêu cầu một hoạt động o Đặc trưng: • Bao đóng:tiến trinh che dấu việc thực thi chi tiết của mọt đối tượng • Kế thừa:Cho phép các lớp đối tượng này kế thừa từ các lớp đối tượng khác • Đa hình:nhiều hành động được thực hiện khác nhau với đối tương khác nhau o Sự trừu tượng hoá : Là khả năng bỏ qua hay không để ý tới các thành phần không quan trọng

III.15.2 Nhận xét  Về đề tài:đây là đề tài tương đối mới mẻ, nhưng đang dần được nhiều người biết

đến ,tìm hiểu và học  Ưu điểm • Bài báo cao khá đầy đủ và chi tiết, nổi bật đươc kiến thức cơ bản 26

• Nội dung trình bày khá rõ ràng  Nhược điểm • Khối lương nội dung khá lơn nhưng không có mục lục để có cái nhìn khái quát •

Trình bày một só chỗ không đưuoc rõ ràng gây loạn cho người đọc

 Bổ sung:

   

Khái niêm lớp cơ sở ảo: Khái niệm toán tử điều khiển Hàm thành viên nội tuyến Phương thức ảo

IV: Giai đoạn kiểm chứng IV.1. Bài báo cáo: Kiểm chứng chương trình NTH: Lê Ngọc Duy Trần-Trần Văn Tài IV.1.1. Tóm tắt  Các giai đoạn trong cuộc sống phàn mêm: o Đặc tả bài toán: phân tích yêu cầu và diễn đạt lại chính xác bằng ngôn ngữ thích

hợp o Xây dựng hệ thống: thiết kế, triển khai từng module và thử nghiệm trên các dữ

liệu và các mức độ hệ thống o Sử dụng và bảo trì hệ thống  Đặc tả: Khi có một vấn đề cần giải quyết, ta phát biểu bài toán bằng một văn bản o Tác dụng của đặc tả bài toán • Là cơ sở để đặt vấn đề, thông tin giũa người đặt bài toán và người giải bài toán . • Là cơ sở để những người giải bài toán triển khai các giải pháp của mình . • Là cơ sở để người giải bài toán kiểm chứng tính đúng của phần mềm tạo ra . • Là phương tiện để nhiều người hiểu tính năng của hệ thống tin học mà không cần đi vào chi tiết của hệ thống o Đặc tả chương trình: gồm dữ liệu nhập và điều kiện ràng buộc trên dữ liệu nhập  Ngôn ngữ lập trình:Để kiểm chứng tính đúng của một đoạn chương trình cần trình bày đoạn chương trình đó trong một dạng NNLT ở dạng cốt lõi.  Kiểm chứng có tính đúng: qua hệ luật Hoare, đoạn chương trình không có vòng lặp, có vong lặp  Kiểm chứng có tính đúng đầy đủ  Lược đồ kiểm chứng hợp lý và các điều kiện càn kiểm chứng

III.16.2 Nhận xét  Về đề tài: đây là đề tài khá mới vẻ, ít được biết đến nhưng cũng đang dần được

nhiều người tìm hiểu  Ưu điểm: o Nội dung nêu khá đây đủ, toàn diện và chính xác  Nhược điểm 27

o Trình bày không tốt, các đề mục không được làm nổi bật, gây khó đọc và nắm bắt nội dung o Nội dung khá trừu tượng, khó tiếp cận

IV.2. Bài báo cáo: Kiểm chứng chương trình NTH: Nguyễn Anh Tuấn- Dương Đức Thiện-Đỗ Đác Xuất IV.21. Tóm tắt: Nội dung giống với nhóm trên nên tôi không tóm tắt lại ở đây

IV.2.2 Nhận xét  Về đề tài: đây là đề tài khá mới vẻ.

 Ưu điểm: o Nội dung nêu khá đây đủ, toàn diện và chính xác o Trình bày khá tốt, làm nổi bật được vấn đề, giúp người đọc nắm bắt được nội dung  Nhược điểm o Nội dung khá trừu tượng, khó tiếp cận

V: Ứng dụng V.1. Bài báo cáo: Lập trình điều khiển trên máy CNC NTH: Phạm Thanh Hòa V.1.1. Tóm tắt  Khái niệm và ngôn ngữ lập trình trên máy CNC Chương trình CNC là tập những chỉ dẫn cần thiết cho quá trình gia công 1 chi tiết cơ khí trên máy công cụ điều khiển CNC hoặc NC một cách tự động Ngôn ngữ lập trình NC chia làm 2 cấp: thấp và cao  Cách điều khiển máy CNC và tiện ích của máy o Điều khiển số trực tiếp CNC: từ bên ngoài bởi máy thực hiện chức năng lập trình o Điều khiển số bằng máy tính: o Điều khiển số bằng máy tính CNC Cấu truc hệ thông gồm 6 thành phần : chương trình gia công, thiết bị đọc, hệ điều khiển máy,hệ truyền chuyển động, hệ phản động và máy công cụ o Khả năng của CNC:CNC có nhiêu chức năng xử lý và điều khiển linh hoạt o Phương thức lập trình CNC: trực tiếp và tự động  Kỹ thuật lập trình: Chương trình CNC bao gồm chuỗi chỉ thị chuyển dao, đóng ngắt và ngắt và phụ chợ cần thiết đẻ điều khiển máy gia công Chương trình CNC:gồm đầu, than và kết thúc chương trình  Bài toán minh họa và hình ảnh các loại máy công cụ và sản phẩm

V.1.2 Nhận xét  Về đề tài: đây là đề tài khá mới vẻ. 28

 Ưu điểm Nội dung nêu khá đây đủ, toàn diện và chính xác

V.2. Bài báo cáo: Quan máy học NTH: Lê Văn Hùng- Lê Viết Hùng-Đặng Trần Long V.2.1. Tóm tắt  Thế nào là máy học o Định nghĩa:là một lĩnh vực của trí tuệ nhân tạo, liên quan đén việc cho phép máy học o Ứng dụng:trong ngành KH-SX,đặc biệt nghành phân tích khối luong dữ liệu khổng lồ: xử lý ngôn ngữ tự nhiên, nhận dạng, chuẩn đoán trong y học.v.v.v o Tương tác với con người:tùy thuộc vào mục đích mà khả năng tương tác khác nhau o Các giải thuật:học có giám sát, học không giám sát, học nửa giám sát, học tăng cường, chuyển đổi, học cách học. o Các chủ đề về máy học:hai chủ đè chính:mô hinh hóa các hàm mật dộ xác suất điều kiện hồi quy và mô hinh hóa các hàm mật dộ xác suất qua mô hình phát sinh  Học bằng cách xây dựng cây định danh o Đâm chồi: là quá trình qua mỗi lầm phân hoạch, cây phn hoạch ngày càng rộng ra o Phương án chọn thuộc tính phân hoạch: hai phương án • Quinlan:quyết định thuộc tính phân hoạch bắng xây dựng vecto đặc trưng • Độ đo hỗn loạn: o Phát sinh tập luật:ứng mỗi lá, ta đi từ đỉnh cho đến nút lá và phát sinh ra luật TƯ. o Tối ưu tập luật • Loại bỏ mệnh đề thừa • Xây dựng mệnh đề mặc định

V.2.2 Nhận xét  Về đề tài:đây là đề tài tương đối mới mẻ, hấp dẫn

 Ưu điểm • Bài báo cáo khá đầy đủ và chi tiết, nổi bật đươc kiến thức cơ bản, nội dung trình bày khá rõ ràng • Trình bày rõ ràng mạch lạc  Nhược điểm  Bổ sung: o Trong các chủ đề về máy học Cần bổ sung thêm:Mô hình tối ưu hóa: hầu hết các phương pháp trên đều sử dụng tối ưu hóa hoặc là các thể hiện của các thuật toán tối ưu hóa o Một số phần mềm hỗ trợ: • SPIDER - một hộp công cụ học máy hoàn chỉnh cho Matlab • Orange, bộ chương trình học máy với các script viết bằng Python và giao diện lập trình đồ họa 29

• •

YALE là một công cụ mạnh miễn phí cho Học máy và Khai phá dữ liệu Matlab

V.3. Bài báo cáo: Ứng dụng ngắt trong lập trình nhúng NTH: Nguyễn Trọng Ngọc- Nguyễn Phi Long-Lê Đức Long V.3.1. Tóm tắt  Nhu cầu thực tế của các hệ thống nhúng trong đời sống hiện nay  Hệ thống nhúng là gì:một thuật ngữ để chỉ một hệ thống có khả năng tự trị được nhúng vào trong một môi trường hay một hệ thống mẹ.  Sự cần thiết của ngắt trong lập trình nhúng: trong quá trình hoạt động có



 



thể xảy ra rắc rối khi điều chỉnh tuần tự, CPU chậm ,tốn -> LT nhúng Mô tả kỹ thuật về thuật toán ngắt  Ngắt trong Dos  Thuật toán  Phân tích thuật toán Ngắt trong vi điều khiển PIC16F887 của Microchip Một vài ứng dụng thực tế  Ngắt giúp tiết kiệm đáng kể CPU  Ngắt và nút bấm Đánh giá ưu nhược điểm và phương hướng phát triển  Ưu điểm của ngắt:tíết kiệm CPU, nâng cao hiệu suấtvà giảm nhiệt độ chíp> kéo dài tuổi thọ  Nhược điểm của ngắt:chương trình ngắt phức tạp và hạn chế ngắt trong 1 chíp  Phương hướng phát triển • Tiếp tục thực hiện ngắt với các timer1, timer2. • Ngắt đối với thiết bị ngoại vi. • Tạo ngắt với nút bấm

V.3.2 Nhận xét  Về đề tài:đây là đề tài khá mới mẻ, hấp dẫn

 Ưu điểm • Bài báo cáo khá đầy đủ và chi tiết, nổi bật đươc kiến thức cơ bản, nội dung trình bày khá rõ ràng • Trình bày rõ ràng mạch lạc, hình ảnh minh họa cụ thể

30