Giáo Trình Kỹ Thuật Lập Trình Nâng Cao Tại Trường Đại Học Công Nghiệp Thực Phẩm TP.HCM

Giáo trình kỹ thuật lập trình nâng cao tại trường ĐH Công nghiệp Thực phẩm TP HCM cung cấp kiến thức chuyên sâu và ứng dụng thực tiễn.

• Trường học: Trường Đại Học Công Nghiệp Thực Phẩm TP.HCM
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Giáo Trình Kỹ Thuật Lập Trình Nâng Cao
• Loại tài liệu: Giáo Trình
• Năm xuất bản: 2013
• Địa điểm: TP.HCM

Mục lục chi tiết

• 1. CHƯƠNG 1: TỔNG QUAN KỸ THUẬT LẬP TRÌNH
• 1.1. Tổng quan về kỹ thuật lập trình
• 1.2. Phong cách lập trình
• 1.3. Một số kỹ thuật và phong cách lập trình căn bản
• 1.4. Phân tích đánh giá giải thuật
• 1.4.1. Sự cần thiết phân tích thuật giải
• 1.4.2. Thời gian thực hiện của chương trình
• 1.4.3. Tỷ suất tăng và độ phức tạp của thuật toán
• 1.4.4. Cách tính độ phức tạp
• 2. CHƯƠNG 2: KỸ THUẬT XỬ LÝ MẢNG
• 2.1. Kỹ thuật xử lý mảng một chiều
• 2.1.1. Thuật toán lặp tổng quát
• 2.1.2. Thuật toán tính tổng và tích
• 2.1.3. Thuật toán đếm
• 2.1.4. Thuật toán tìm phần tử đầu tiên
• 2.1.5. Thuật toán tìm tất cả các phần tử
• 2.1.6. Thuật toán tìm min, max
• 2.1.7. Thuật toán sắp xếp
• 2.2. Kỹ thuật xử lý mảng hai chiều
• 2.2.1. Mảng hai chiều (ma trận)
• 2.2.2. Thuật toán cơ bản trên mảng hai chiều
• 2.2.3. Ma trận vuông
• 2.2.4. Một số bài toán đặc biệt
• 3. CHƯƠNG 3: KỸ THUẬT ĐỆ QUY
• 3.1. Đệ quy tuyến tính (Linear Recursion)
• 3.2. Đệ quy nhị phân (Binary Recursion)
• 3.3. Đệ quy phi tuyến (NonLinear Recursion)
• 3.4. Đệ quy tương hỗ (Mutual Recursion)
• 3.5. Những ưu nhược điểm của kỹ thuật đệ quy
• 3.6. Các bước tìm giải thuật đệ quy cho một bài toán
• 3.6.1. Thông số hóa bài toán
• 3.6.2. Tìm các trường hợp cơ bản (phần cơ sở) cùng giải thuật tương ứng cho các trường hợp này
• 3.6.3. Phân rã bài toán tổng quát theo phương thức đệ quy
• 3.6.4. Một số bài toán đệ quy thông dụng
• 3.6.4.1. Bài toán tìm tất cả hoán vị của một dãy phần tử
• 3.6.4.2. Bài toán sắp xếp mảng bằng phương pháp trộn (Merge Sort)
• 3.6.4.3. Bài toán chia thưởng
• 3.6.4.4. Bài toán tháp Hà Nội
• 3.7. Khử đệ quy
• 3.7.1. Khử đệ quy đơn giản bằng vòng lặp
• 3.7.2. Khử đệ quy dùng stack
• 4. CHƯƠNG 4: KỸ THUẬT XỬ LÝ CHUỖI
• 4.1. Một số khái niệm
• 4.2. Nhập/ xuất chuỗi kí tự
• 4.3. Các thuật toán tìm kiếm chuỗi
• 4.3.1. Thuật toán Brute Force
• 4.3.2. Thuật tóan Knuth – Morris – Pratt
• 4.3.3. Thuật tóan Boyer Moore
• 5. CHƯƠNG 5: THIẾT KẾ THUẬT TOÁN
• 5.1. Kỹ thuật chia để trị - Divide to Conquer
• 5.2. Một số bài toán minh họa
• 5.3. Kỹ thuật tham ăn – Greedy Technique
• 5.3.1. Giới thiệu bài toán tối ưu tổ hợp
• 5.3.2. Nội dung kỹ thuật tham ăn
• 5.3.3. Một số bài toán minh họa
• 5.4. Kỹ thuật nhánh cận - Branch and Bound
• 5.4.1. Bài toán tìm đường đi của người giao hàng
• 5.5. Kỹ thuật quy hoạch động - Dynamic programming
• 5.5.1. Một số bài toán minh họa
• 5.5.2. Bài toán ba lô
• TÀI LIỆU THAM KHẢO
• LỜI NÓI ĐẦU

Tóm tắt

I. Tổng quan về Giáo Trình Kỹ Thuật Lập Trình Nâng Cao

Giáo trình Kỹ thuật lập trình nâng cao tại Trường ĐH Công Nghiệp Thực Phẩm TP.HCM cung cấp kiến thức nền tảng và nâng cao cho sinh viên ngành công nghệ thông tin. Nội dung giáo trình được thiết kế để giúp sinh viên nắm vững các kỹ thuật lập trình, từ cơ bản đến nâng cao, nhằm đáp ứng nhu cầu thực tiễn trong ngành công nghiệp phần mềm.

1.1. Mục tiêu của giáo trình Kỹ thuật lập trình

Giáo trình nhằm trang bị cho sinh viên những kiến thức cần thiết về kỹ thuật lập trình và giải thuật. Sinh viên sẽ học cách phân tích và xây dựng các giải thuật hiệu quả, từ đó áp dụng vào thực tiễn.

1.2. Đối tượng sử dụng giáo trình

Giáo trình được thiết kế cho sinh viên hệ đại học chuyên ngành Công nghệ thông tin. Nó cũng có thể hữu ích cho những người muốn nâng cao kỹ năng lập trình của mình.

II. Những Thách Thức Trong Kỹ Thuật Lập Trình Nâng Cao

Kỹ thuật lập trình nâng cao đối mặt với nhiều thách thức, từ việc hiểu rõ các thuật toán đến việc áp dụng chúng vào các bài toán thực tế. Những thách thức này đòi hỏi sinh viên phải có tư duy logic và khả năng phân tích tốt.

2.1. Khó khăn trong việc phân tích giải thuật

Phân tích giải thuật là một trong những thách thức lớn nhất. Sinh viên cần phải hiểu rõ cách thức hoạt động của từng giải thuật để có thể áp dụng một cách hiệu quả.

2.2. Độ phức tạp của thuật toán

Độ phức tạp của thuật toán ảnh hưởng lớn đến hiệu suất của chương trình. Sinh viên cần nắm vững cách tính độ phức tạp để lựa chọn giải thuật phù hợp cho từng bài toán.

III. Phương Pháp Giảng Dạy Kỹ Thuật Lập Trình Nâng Cao

Phương pháp giảng dạy trong giáo trình Kỹ thuật lập trình nâng cao bao gồm lý thuyết kết hợp với thực hành. Điều này giúp sinh viên có thể áp dụng kiến thức vào thực tế một cách hiệu quả.

3.1. Lý thuyết và thực hành

Giáo trình kết hợp giữa lý thuyết và thực hành, giúp sinh viên hiểu rõ hơn về kỹ thuật lập trình và cách áp dụng chúng vào các bài toán thực tế.

3.2. Các bài tập thực hành

Cuối mỗi chương có phần bài tập từ cơ bản đến nâng cao, giúp sinh viên kiểm tra và củng cố kiến thức đã học.

IV. Ứng Dụng Thực Tiễn Của Kỹ Thuật Lập Trình Nâng Cao

Kỹ thuật lập trình nâng cao có nhiều ứng dụng trong thực tiễn, từ phát triển phần mềm đến giải quyết các bài toán phức tạp trong ngành công nghiệp.

4.1. Phát triển phần mềm

Kỹ thuật lập trình nâng cao giúp sinh viên phát triển các ứng dụng phần mềm hiệu quả, đáp ứng nhu cầu của thị trường.

4.2. Giải quyết bài toán phức tạp

Sinh viên có thể áp dụng các kỹ thuật lập trình để giải quyết các bài toán phức tạp trong lĩnh vực công nghệ thông tin.

V. Kết Luận Về Giáo Trình Kỹ Thuật Lập Trình Nâng Cao

Giáo trình Kỹ thuật lập trình nâng cao tại Trường ĐH Công Nghiệp Thực Phẩm TP.HCM là một tài liệu quý giá cho sinh viên. Nó không chỉ cung cấp kiến thức lý thuyết mà còn giúp sinh viên phát triển kỹ năng thực hành cần thiết.

5.1. Tương lai của kỹ thuật lập trình

Kỹ thuật lập trình sẽ tiếp tục phát triển và đóng vai trò quan trọng trong ngành công nghiệp phần mềm. Sinh viên cần cập nhật kiến thức thường xuyên để theo kịp xu hướng mới.

5.2. Khuyến nghị cho sinh viên

Sinh viên nên chủ động tìm hiểu và thực hành các kỹ thuật lập trình để nâng cao kỹ năng của mình, từ đó đáp ứng tốt hơn yêu cầu của thị trường lao động.

Trích đoạn nội dung tài liệu

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THỰC PHẨM TP.HCM KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM  Giáo trình KỸ THUẬT LẬP TRÌNH NÂNG CAO (Dành cho hệ Đại học) TP.HCM, tháng 9 năm 2013 1 MỤC LỤC CHƯƠNG 1. TỔNG QUAN KỸ THUẬT LẬP TRÌNH.1 Tổng quan về kỹ thuật lập trình .1 Phong cách lập trình .2 Một số kỹ thuật và phong cách lập trình căn bản.2 Phân tích đánh giá giải thuật .1 Sự cần thiết phân tích thuật giải .2 Thời gian thực hiện của chương trình .3 Tỷ suất tăng và độ phức tạp của thuật toán .4 Cách tính độ phức tạp . KỸ THUẬT XỬ LÝ MẢNG .1 Kỹ thuật xử lý mảng một chiều .1 Thuật toán lặp tổng quát.2 Thuật toán tính tổng và tích.3 Thuật toán đếm .4 Thuật toán tìm phần tử đầu tiên .5 Thuật toán tìm tất cả các phần tử.6 Thuật toán tìm min, max .7 Thuật toán sắp xếp .2 Kỹ thuât xử lý mảng hai chiều .1 Mảng hai chiều (ma trận) .2 Thuật toán cơ bản trên mảng hai chiều .3 Ma trận vuông.4 Một số bài toán đặc biệt . KỸ THUẬT ĐỆ QUY .1 Đệ quy tuyến tính (Linear Recursion) .2 Đệ quy nhị phân (Binary Recursion) .3 Đệ quy phi tuyến (NonLinear Recursion).5 Đệ quy tương hỗ (Mutual Recursion) .6 Những ưu nhược điểm của kỹ thuật đệ quy .3 Các bước tìm giải thuật đệ quy cho một bài toán .1 Thông số hóa bài toán .2 Tìm các trường hợp cơ bản (phần cơ sở) cùng giải thuật tương ứng cho các trường hợp này.3 Phân rã bài toán tổng quát theo phương thức đệ quy .4 Một số bài toán đệ quy thông dụng .1 Bài toán tìm tất cả hoán vị của một dãy phần tử.2 Bài toán sắp xếp mảng bằng phương pháp trộn (Merge Sort) .3 Bài toán chia thưởng .4 Bài toán tháp Hà Nội.1 Khử đệ quy đơn giản bằng vòng lặp.2 Khử đệ quy dùng stack. KỸ THUẬT XỬ LÝ CHUỖI .1 Một số khái niệm .2 Nhập/ xuất chuỗi kí tự.2 Các thuật toán tìm kiếm chuỗi .1 Thuật toán Brute Force .2 Thuật tóan Knuth – Morris – Pratt.3 Thuật tóan Boyer Moore . THIẾT KẾ THUẬT TOÁN .1 Kỹ thuật chia để trị - Divide to Conquer .2 Một số bài toán minh họa.2 Kỹ thuật tham ăn – Greedy Technique .1 Giới thiệu bài toán tối ưu tổ hợp .2 Nội dung kỹ thuật tham ăn.3 Một số bài toán minh họa.3 Kỹ thuật nhánh cận - Branch and Bound .2 Bài toán tìm đường đi của người giao hàng .4 Kỹ thuật quy hoạch động - Dynamic programming .2 Một số bài toán minh họa.3 Bài toán ba lô. 107 TÀI LIỆU THAM KHẢO. 118 3 LỜI NÓI ĐẦU “Algorithm + Data structure = Program” (“Giải thuật + Cấu trúc dữ liệu = Chương trình”) Câu nói nổi tiếng của Niklaus Wirth, một nhà khoa học máy tính nổi tiếng, tác giả của ngôn ngữ lập trình Pascal, đã đặt tên cho một cuốn sách của ông. Đây là một trong những quyển sách nổi tiếng, được làm giáo trình giảng dạy ở các trường đại học lớn. Qua đó chúng ta thấy vai trò quan trọng của giải thuật và kỹ thuật lập trình để xây dựng các giải thuật nhằm tìm đáp án tối ưu nhất cho các bài toán lập trình. Môn học Kỹ thuật lập trình nâng cao được bố trí sau 2 môn học Kỹ thuật lập trình và Cấu trúc dữ liệu trong chương trình đào tạo cho sinh viên chuyên ngành Công nghệ thông tin. Môn học nhằm giới thiệu cho sinh viên những kiến thức cơ bản, những kỹ thuật chủ yếu của việc phân tích và xây dựng các giải thuật, để tìm ra các cách giải tối ưu nhất có thể cho bài toán. Các kỹ thuật được trình bày ở đây là những kỹ thuật cơ bản, phổ biến và được các nhà khoa học tin học tổng kết và vận dụng trong cài đặt các chương trình. Việc nắm vững các kỹ thuật đó sẽ rất bổ ích cho sinh viên khi phải giải quyết một vấn đề thực tế. Nội dung giáo trình gồm các phần như sau: - Chương 1: Tổng quan kỹ thuật lập trình - Chương 2: Xử lý cấu trúc mảng - Chương 3: Kỹ thuật đệ qui - Chương 4: Xử lý chuỗi - Chương 5: Thiết kế thuật toán Các vấn đề được trình bày chi tiết với những ví dụ rõ ràng. Cuối mỗi chương có phần bài tập được sắp xếp từ cơ bản đến nâng cao giúp sinh viên nắm vững và kiểm tra kiến thức bằng việc giải các bài tập. Chúng tôi mong rằng các sinh viên tự tìm hiểu trước mỗi vấn đề, kết hợp với bài giảng trên lớp của giảng viên và làm bài tập để việc học môn này đạt hiệu quả. Trong quá trình giảng dạy và biên soạn giáo trình này, chúng tôi đã nhận được nhiều đóng góp quý báu của các đồng nghiệp ở Bộ môn Công nghệ Phần mềm cũng như các đồng nghiệp trong và ngoài Khoa Công nghệ Thông tin. Chúng tôi xin cảm ơn và hy vọng rằng giáo trình này sẽ giúp cho việc giảng dạy và học môn “Kỹ thuật lập trình nâng cao” đạt hiệu quả tốt hơn. Chúng tôi hy vọng nhận được nhiều ý kiến đóng góp để giáo trình ngày càng hoàn thiện. Nhóm tác giả 4 CHƯƠNG 1. TỔNG QUAN KỸ THUẬT LẬP TRÌNH 1.1 Tổng quan về kỹ thuật lập trình 1.1 Phong cách lập trình Một chương trình nguồn được xem là tốt không chỉ được đánh giá thông qua thuật giải đúng và cấu trúc dữ liệu thích hợp, mà còn phụ thuộc vào phong cách và kỹ thuật mã hoá (coding) của người viết chương trình. Nếu một người lập trình viết một chương trình dù thực hiện đúng yêu cầu đặt ra nhưng mã nguồn quá lộn xộn và phong cách lập trình cẩu thả, thì mã nguồn này sẽ gây khó khăn không chỉ cho những người khác muốn đọc hiểu nó, mà còn cho chính người lập trình khi muốn chỉnh sửa hoặc cải tiến. Đôi khi người mới lập trình không quan tâm đến vấn đề này do ban đầu chỉ làm việc với chương trình nhỏ. Tuy nhiên, vấn đề phát sinh khi họ phải làm việc với dự án lớn và chương trình lúc này không còn đơn giản vài chục dòng lệnh nữa. Nếu không rèn luyện một phong cách và trang bị một số kỹ thuật lập trình tốt thì người lập trình đối mặt với nhiều khó khăn… Trong chương đầu tiên xin giới thiệu một số kỹ thuật và phong cách lập trình cơ bản, ít nhiều giúp cho người học viết chương trình được tốt hơn.2 Một số kỹ thuật và phong cách lập trình căn bản. Cách đặt tên biến Thông thường tùy theo ngôn ngữ và môi trường lập trình, người viết chương trình thường chọn cho mình một phong cách nhất quán trong việc đặt tên các định danh. Một số quy tắc cần quan tâm khi đặt tên như sau: – Tên của định danh phải thể hiện được ý nghĩa: thông thường các biến nguyên như i, j, k dùng làm biến chạy trong vòng lặp; x, y dùng làm biến lưu tọa độ, hoặc dùng làm biến đại diện cho các số bất kỳ… Còn những biến lưu trữ dữ liệu khác thì nên đặt gợi nhớ, nhưng tránh dài dòng: biến đếm số lần dùng "count, dem, so_luong…", biến lưu trọng lượng “weight, trong_luong”, chiều cao “height” ; … Nếu đặt quá ngắn gọn như c cho biến đếm, hay w cho khối lượng thì sau này khi nhìn vào chương trình sẽ rất khó hiểu ý nghĩa của chúng. Ngược lại đặt tên quá dài như "the_first_number, the_second_number,…" để chỉ các số bất kỳ, sẽ làm dư thừa, rườm rà trong chương trình. – Tên phải xác định được kiểu dữ liệu lưu trữ: phong cách lập trình tốt là khi người đọc nhìn vào một biến nào đó thì xác định ngay được kiểu dữ liệu và tên đối tượng mà biến đó lưu trữ. Cho nên tên biến thường là danh từ (tên đối tượng) kèm theo tiền tố mang ý nghĩa kiểu dữ liệu. Giả sử có biến đếm số lần thì ta có thể đặt iNumber, trong đó i là kiểu của dữ liệu, strContent là kiểu chuỗi, CPoint là lớp Point…Có nhiều cú pháp quy ước đặt tên biến, người lập trình có thể chọn cho mình một quy ước thích hợp. Có thể tham khảo một số quy ước trong phần bên dưới. – Theo một quy ước cụ thể: + Cú pháp Hungary: hình thức chung của cú pháp này là thêm tiền tố chứa kiểu dữ liệu vào tên biến.1 bên dưới là một số tiền tố quy ước được nhiều lập trình viên sử dụng. Các công ty phần mềm thường có các quy ước về cách đặt tên biến cho 5 đội ngũ lập trình viên. Tuy nhiên đa số các quy ước này đều dựa trên cú pháp Hungary. Tiền tố Kiểu dữ liệu Ví dụ minh họa b bool bool bEmpty, bChecked ; c char char cInChar, cOutChar ; str/s String string strFirstName, strIn, strOut ; i/n integer int iCount, nNumElement ; li long integer long liPerson, liStars ; f float float fPercent ; d double double dMiles, dFraction ; if Input file stream ifstream ifInFile ; of Output file stream ofstream ofOutFile ; S Struct struct sPoint{…} ; C Class class CStudent,CPerson + Đối với những hằng thì tất cả các ký tự đều viết HOA.1: #define MAXSIZE 100 const float PI = 3.14 ; + Cách đặt tên cho hàm : hàm bắt đầu với ký tự đầu tiên là ký tự viết thường và các ký tự đầu từ phía sau viết hoa, hoặc các từ cách nhau bằng dấu _ (underscore) và không có tiền tố. Tuy nhiên điều này cũng không bắt buộc tùy theo ngôn ngữ lập trình. Ngoài ra hàm có chức năng thực hiện một nhiệm vụ nào đó, cho nên tên chúng là động từ hoặc cụm động từ, thường bắt đầu bằng các động từ chính: get, set, do, is, make… Ví dụ 1. Phong cách viết mã nguồn – Sử dụng tab để canh lề chương trình : khi soạn thảo mã nguồn nên dùng tab với kích thước là 4 hay 8 khoảng cách để canh lề. Thói quen này giúp cho chương trình được rõ ràng và dễ đọc, dễ quản lý. 6 Không nên Nên void docFile (SV a[], int &n) void docFile (SV a[], int &n) { { ifstream in; ifstream in; char* filename="filein.txt"; char* filename = in.txt"; in>>n; in.diem; } } } – Sử dụng khoảng trắng : chương trình sẽ dễ nhìn hơn Không nên Nên int iCount =0 ; int iCount = 0 ; for(int i=0;i<n;i++) for (int i = 0 ; i < n ; i++) { { iCount++; iCount ++; } } cout<<"Ket qua la:"<<iCount; cout << "Ket qua la:" << iCount; – Tránh viết nhiều lệnh trên một dòng. Không nên Nên if(a>5){b=a; a++} if ( a > 5) { b = a; a ++; } – Định nghĩa các hằng số. 7 Một số lập trình có thói quen không định nghĩa những hằng số thường xuyên sử dụng.