Bài giảng Kỹ thuật lập trình - Giới thiệu môn học - Trịnh Tấn Đạt

Kỹ Thuật Lập Trình Trịnh Tấn Đạt Khoa CNTT - Đại Học Sài Gòn Email: trinhtandat@sgu.edu.vn Website: https://sites.google.com/site/ttdat88/ Nội dung ▪ Giới thiệu môn học ▪ Các nội dung ▪ Đánh giá ▪ Tài liệu tham khảo ▪ Đề tài cho đồ án môn học (option) ▪ Trao đổi và thảo luận Giới Thiệu ▪ Tên học phần: Kỹ thuật lập trình ▪ Số tín chỉ: 3 (2,1) ▪ Số tiết (lí thuyết, thực hành): 60 (30; 30) ▪ Mô tả học phần o Học phần Kỹ thuật lập trình trình bày các kiến thức tiếp nối của học phần Cơ sở lập trình, bao gồm các chương: Kỹ thuật lập trình đệ qui, Kỹ thuật lập trình con trỏ, Kỹ thuật lập trình ký tự và chuỗi ký tự, Kỹ thuật lập trình với tập tin văn bản, một số kỹ thuật lập trình nâng cao. o Học phần này giúp người học hoàn thiện và nâng cao kiến thức về ngôn ngữ lập trình. Giúp người học rèn luyện nhằm nâng cao tư duy về kỹ thuật lập trình. ▪ Mục tiêu: hoàn thiện các kỹ năng về lập trình như: Phân tích vấn đề bài toán, thiết kế chương trình, soạn thảo chương trình, hình thành phong cách lập trình hiệu quả, xử lý lỗi chương trình, ... Nội dung môn học ▪ Giới thiệu và Ôn Tập ▪ Thiết kế chương trình ▪ Con trỏ (Pointer) ▪ Tập tin (FILE) ▪ Chuỗi ký tự (String) ▪ Đệ quy (Recursion) ▪ Các kỹ thuật lập trình tối ưu o Qui hoạch động o Chia để trị o Tìm kiếm và Quay lui (option) o Tham lam (option) ▪ Đồ án môn học (option – không bắt buộc. Sinh viên đăng ký làm sẽ được điểm cộng) Giới Thiệu ❖ Tài liệu tham khảo: ▪ Tài liệu chính [1] Huỳnh Minh Trí, Phan Tấn Quốc, Nguyễn Nhựt Đông, Giáo trình kỹ thuật lập trình, NXB Đại học Quốc Gia TPHCM, 2016. ▪ Tài liệu khác (khuyến khích đọc thêm tài liệu bằng Tiếng Anh) [2] Phạm Văn Ất, “Kỹ thuật lập trình C - cơ sở và nâng cao”, NXB Giáo Dục, 2006. [3] K.N.King, C Programming: A Modern Approach, 2nd Edition [4] Brian W. Kernighan and Dennis M. Ritchie ,The C Programming Language (2nd Edition) [5] Wikibooks.org, “C Programming”, 2012. ▪ Nguồn tham khảo khác (tử internet, tìm kiếm bằng tiếng Anh) o https://www.cprogramming.com/tutorial/c-tutorial.html o o Stackoverflow: https://stackoverflow.com/ o GeeksforGeeks : https://www.geeksforgeeks.org/ o Google, Bing, Baidu, Đánh giá môn học ▪ Điểm quá trình: 50% o Điểm lý thuyết: ✓ Chuyên cần, thảo luận : được thêm điểm thưởng ✓ Kiểm tra giữa kỳ: 1 bài ✓ Điểm đồ án môn học (không bắt buộc): • Sinh viên đăng ký và hoàn thành được thưởng tối đa +2đ. • Nếu đã đăng ký mà không làm sẽ bị trừ -1đ. o Điểm thực hành : ✓ Chuyên cần, thảo luận : được thêm điểm thưởng ✓ Kiểm tra thực hành: cho bài tập về nhà làm trong vòng 2 hoặc 3 tuần. Sau đó sẽ thảo luận và vấn đáp trong phòng thực hành để chấm điểm. ▪ Thi kết thúc học phần: 50% ✓ Tự luận, đề đóng, thời gian làm bài: 90 phút Project môn học (không bắt buộc) ▪ Yêu cầu: thời gian đăng ký (đến hết tuần thứ 3 của học kỳ) • Lý thuyết: đọc hiểu, viết theo hiểu (không dịch word-by-word) • Cài đặt: code và run chương trình. (dựa vào các ví dụ) • Trình bày (powerpoint): ❑ Sơ lược ý chính lý thuyết ❑ Ý tưởng giải quyết(thuật toán, thuật giải) bài toán ❑ Kết quả ❖ Số lượng thành viên 2 hoặc 3 sinh viên Danh sách các đề tài: (sẽ cập nhật thêm trên website) 1. Thuật toán quay lui (Backtracking) và bài toán 8 hậu, mã đi tuần 2. Thuật toán nhánh cận và ứng dụng (ít nhất 3 ví dụ) 3. Thuật toán tham lam và ứng dụng (ít nhất 3 ví dụ) 4. Thuật toán leo đồi (Hill Climbing) và ứng dụng 5. Thuật toán luyện kim (Simulated Annealing) và ứng dụng 6. Tabu Search và ứng dụng 7. Tối ưu bầy đàn (Particle Swarm Optimization) và ứng dụng 8. Giải thuật đàn kiến (Ant colony optimization) và ứng dụng 9. Giải thuật di truyền (Genetic Algorithm) và ứng dụng 10. Thuật toán Dynamic Time Warping (dựa trên quy hoạch động) 11. Thuật toán gradient descent và ứng dụng 12. Ma trận thưa và Thuật toán nhân (nhanh) hai ma trận thưa 13. Sum-area Table (Integral Image) và ứng dụng 14. Tìm hiểu về Standard Template Library (containers, iterators, algorithms) trong C++ và các ví dụ Nghề lập trình và những sự thật ít người biết tới https://techmaster.vn/posts/1862/nghe-lap-trinh-va-nhung-su-that-it-nguoi-biet-toi Trích một phần bài viết ▪ Lập trình là một công việc như thế nào? Có phải lập trình viên là những người tối ngày ngồi trước màn hình máy tính? Cứ code giỏi thì sản phẩm sẽ tốt? Lập trình là một lĩnh vực mà nếu không phải trong nghề thì thật khó thấu hiểu những nỗi “trần ai” trong đó. Sau đây, kĩ sư công nghệ thông tin David Veksler – chủ trang blog The Rational Mind – sẽ chia sẻ cho chúng ta những sự thật ít ai biết về nghề IT – nghề lập trình: Chỉ 10-20% thời gian của toàn bộ dự án được các lập trình viên sử dụng để viết code, và bất kể trình độ, mỗi ngày 1 lập trình viên chỉ viết trung bình từ 10-20 dòng code. Sự khác biệt giữa tay chuyên và gà mờ đó là tay chuyên thì dành 90% thời gian để suy luận, tìm tòi và thử nghiệm các phương án tối ưu nhất cho mình; còn những gà mờ thì dành 90% thời gian để debug, thay đổi vài chỗ trong code, lại debug và mong đến một lúc nào đó chương trình sẽ hoạt động. Coder, Programmer, Developer và Engineer https://www.topitworks.com/blogs/cung-lam-viec-trong-nganh-phan-mem-programmer-coder- developer-va-engineer-khac-nhau-the-nao/ Các loại lỗi trong lập trình ❖ Code xong và cho thực thi thì hiện lỗi 1. Lỗi cú pháp (Syntax Error): Hay còn gọi là lỗi biên dịch (Compiler error) Đây là loại lỗi sơ đẳng nhất trong lập trình. Thường là do bạn gõ sai cấu trúc của ngôn ngữ (ví dụ như thiếu dấu kết thúc một câu lệnh, một số ngôn ngữ từ khoá phân biệt chữ hoa, chữ thường thì lại gõ chữ hoa, v.v. gọi nôm na là lỗi chính tả). Chương trình sẽ không thể biên địch được khi gặp lỗi này. Các trình biên dịch sẽ khi biên dịch code, khi gặp lỗi ở dòng code nào thì sẽ báo lỗi. 2. Lỗi thực thi (Runtime error): Xảy ra bất ngờ khi chương trình đang chạy Loại lỗi này thường xảy ra do người lập trình viết code ẩu, không lường hết các trường hợp xảy ra, khiến chương trình đang chạy thì bị lỗi treo màn hình, thoát khỏi chương trình hoặc thoát luôn chương trình, v.v. Lỗi này có thể dễ dàng phát hiện bằng cách Debug. 3. Lỗi logic (khó phát hiện nhất) : Đây là lỗi do tư duy sai, thuật toán sai dẫn đến sai kết quả ❖ Code xong, chạy tốt nhưng không hiểu tại sao??? - Copy code từ các nguồn có sẵn nhưng ko đọc hiểu code. - Nghĩ tới đâu, code và debug đến đó. - Thiếu comment giải thích - Phân chia module/ hàm hợp lý. Thiếu giải thích mục tiêu, input, ouput của hàm. Từ bài toán đến chương trình Bài toán thực tế Giải thuật tốt/tối ưu Giải thuật - Dùng Mã giả (Pseudocode) - Dùng flowchart Thiết kế Đánh giá Coding - Mô hình toán - Chọn kiểu dữ liệu, cấu trúc dữ liệu - Thiết kế giải thuật Phân tích, đánh giá thuật toán -Độ phức tạp - Cải tiến thuật toán Ngôn ngữ lập trình C/C++ Java Python Các ví dụ thực tế ▪ Bài toán document scanner tham khảo: https://blogs.dropbox.com/tech/2016/08/fast-and-accurate-document-detection-for-scanning/ Goal: to find the corners and edges of a document in the image, so that it can be cropped out from the background. input output Các ví dụ thực tế Compute the intersections between the lines ( tìm giao điểm giữa các đường thẳng) Bài Tập (option) Bài toán: Nhập vào N đường thẳng (mỗi đường thẳng được biễu diễn bằng 2 điểm trong Oxy) a) Liệt kê tất cả giao điểm của các đường thẳng. b) Tìm góc tại giao điểm của các đường thẳng Các ví dụ thực tế ▪ Phân tích thừa số nguyên tố và ứng dụng trong mật mã. ▪ Thuật toán RSA được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT) ▪ Độ an toàn của hệ thống RSA dựa trên 1 trong những vấn đề của toán học: bài toán phân tích ra thừa số nguyên tố các số nguyên lớn. Ví dụ: 15 = 3 * 5 ▪ Năm 2009, để phân tích thành thừa số một số có 232 chữ số (RSA-768) sử dụng hàng trăm máy tính đã mất hai năm. https://www.calculatorsoup.com/calculators/math/prime-factors.php The limit on the input number to factor is less than 10,000,000,000,000 (less than 10 trillion or a maximum of 13 digits) Các ví dụ thực tế ▪ Search Algorithm (thuật toán tìm kiếm) ▪ Goal: Nhanh, hiệu quả, ít tốn bộ nhớ. Ví dụ: Tìm trong từ điển để tra ý nghĩa một từ ( English to Vietnamese) Tìm nội dung “thuật toán sắp xếp trên mảng” trong một quyển sách Tìm đường đi ngắn nhất từ nhà tới trường trong một thành phố