Bài giảng Công nghệ thông tin 1 - Xây dựng, phát triển và đánh giá thuật toán

Nội dung text: Bài giảng Công nghệ thông tin 1 - Xây dựng, phát triển và đánh giá thuật toán

1. Nhập môn Công nghệ thông tin 1
2.  Nghiên cứu khoa học  Nghiên cứu thuật toán  Vai trò và chức danh trong nghiên cứu khoa học 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 2
3. • Nghiên cứu khoa học thường được mô tả là một quy trình tìm hiểu tích cực, cần cù và có hệ thống nhằm khám phá, lý giải tri thức hay thậm chí tạo ra những tri thức mới. 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 4
4. • Nghiên cứu thường được chia làm hai loại: – Nghiên cứu cơ bản: phát triển các lý thuyết hiện có nhằm làm cho nó càng gần giống với thế giới tự nhiên. – Nghiên cứu ứng dụng: cách thức đưa các lý thuyết vào sản xuất các sản phẩm phục vụ đời sống. “Điện đã có thể không bao giờ được phát minh nếu người ta chỉ lo việc cải tiến những ngọn nến” 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 5
5. • Mức độ tổng quát: – Giúp tri thức nhân loại ngày càng mở rộng và phát triển. – Đáp ứng được nhu cầu và thỏa mãn của con người nhiều hơn. – • Mức độ cá nhân: – Để kiếm sống. – Để thỏa đam mê khám phá. – (Thảo luận) 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 6
6. Tính toán Khai thác mềm dữ liệu Nhận dạng Thị giác máy tính 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 7
7. Search engine Chẩn đoán y khoa Bài toán Trí tuệ nhân tạo Bioinformatics 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 8
8. Thị trường chứng khoán Hệ thống siêu thị Tài chính, ngân hàng Tổng hợp, phân loại, gom cụm văn bản 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 9
9. Nhận dạng mặt người Phân loại cá trong công nghiệp Nhận dạng chữ viết 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 10
10. • Thuật toán hay giải thuật nói chung là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa cho việc hoàn tất một số việc từ một trạng thái ban đầu cho trước dẫn đến kết quả mong muốn. • Một bài toán có thể được giải quyết bởi các thuật toán khác nhau. 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 12
11. • Thuật toán để giải phương trình bậc nhất P(x): ax + b = c (với a, b, c là các số thực) có thể thực hiện qua một số bước sau: Nếu a = 0 b = c thì P(x) có nghiệm bất kì b ≠ c thì P(c) vô nghiệm Nếu a ≠ 0 P(x) có duy nhất một nghiệm x = (c - b)/a 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 13
12. • Boolos & Jeffrey (1974, 1999) đã đưa ra nhận xét sau: – Không có con người nào có thể viết đủ nhanh, đủ dài, đủ nhỏ để liệt kê tất cả các thành phần của một tập rất lớn gần như vô hạn mà chỉ bằng cách lần lượt viết ra tên của chúng theo một số quy ước. – Tuy nhiên, con người có thể đưa ra cách thức để xác định phần tử thứ n bất kì. Từ đó, cách thức này sẽ được thực hiện bởi các máy điện toán. 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 14
13. • Các nhà phát triển thuật toán thường tự đặt 4 câu hỏi phản biện (critical) khi họ đánh giá các thuật toán: – Có phải thuật toán giải quyết bài toán đã được nêu ra? – Có phải thuật toán rõ ràng, rành mạch? – Thuật toán có đưa ra một kết xuất? – Thuật toán có kết thúc trong một khoảng thời gian hợp lý? 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 15
14. • Xác định đầu vào • Xác định tiến trình thực hiện • Xác định đầu ra • Phát triển lược đồ HIPO • Xác định các module liên quan 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 16
15. • Thuật toán cần dữ liệu gì? • Như thế nào để có dữ liệu đó? • Định dạng dữ liệu thế nào? 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 17
16. • Làm cách nào để thao tác với dữ liệu để sinh ra những kết quả có ý nghĩa? 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 18
17. • Dữ liệu nào cần được trả ra? • Định dạng dữ liệu trả ra? 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 19
18. • HIPO (Hierarchy of Input-Processes- Outputs) là một kĩ thuật phục vụ cho việc lên kế hoạch và ghi tài liệu cho thuật toán. • HIPO là một biểu đồ phân tầng thể hiện cấu trúc điều khiển và một bộ nhập-xử lý- xuất để mô tả dữ liệu đến, dữ liệu xuất từ đâu và những xử lý được thực thi bởi các module trên lược đồ phân tầng này. 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 20
19. BÀI TOÁN NHẬP XỬ LÝ XUẤT MODULE MODULE MODULE MODULE MODULE MODULE 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 21
20. • Như thế nào để tách những bài toán lớn thành những mảnh nhỏ hơn và có thể quản lý được? • Các module cần dữ liệu đầu vào nào? • Những xử lý cần được thực hiện trong mỗi module? • Dữ liệu kết xuất của từng module? 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 22
21. • Thuật toán có thể được thể hiện trong: – Ngôn ngữ tự nhiên – Mã giả – Lược đồ flowchart – Ngôn ngữ lập trình – Bảng điều khiển 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 23
22. • Thuật toán được đánh giá dựa trên khối lượng tài nguyên (thời gian và bộ nhớ) cần để thực thi nó. – Độ phức tạp về mặt không gian. – Độ phức tạp về mặt thời gian. 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 24
23. • Đánh giá thuật toán quan trọng vì: – Việc sử dụng vô ý một thuật toán không hiệu quả có thể ảnh hưởng đến hiệu năng hệ thống. – Trong các ứng dụng thời gian thực, một thuật toán chạy quá lâu có thể làm cho kết quả của nó đã lỗi thời hoặc vô dụng. – Một thuật toán không hiệu quả cũng có thể tiêu tốn một khối lượng tính toán hay vùng nhớ một cách không kinh tế để chạy. 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 25
24. • Có nhiều cách để phân loại thuật toán: – Theo cách thực thi: tuần tự, song song, – Theo phương pháp thiết kế: vét cạn, chia để trị, – Theo lĩnh vực nghiên cứu: tìm kiếm, sắp xếp, – Theo độ phức tạp: khối lượng thời gian cần để hoàn thành so với kích thước dữ liệu nhập. 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 26
25. • Các chức danh trong nghiên cứu khoa học ở Việt Nam: – Học vị: • Cử nhân: người hoàn thành một chương trình đào tạo các môn khoa học ở cấp đại học. • Thạc sĩ: người nắm vững một lĩnh vực trong nghiên cứu khoa học. • Tiến Sĩ: người có thể đưa ra các phát kiến mới. – Học hàm: • Phó Giáo Sư • Giáo Sư 14/12/2015 Khoa CNTT - ĐH Khoa học Tự nhiên 28