intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Kỹ thuật lập trình: Các kỹ thuật lập trình nâng cao - Trịnh Tấn Đạt (2024)

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:86

Thêm vào BST
Báo xấu
2
lượt xem 0
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Kỹ thuật lập trình: Các kỹ thuật lập trình nâng cao" cung cấp cho người đọc các nội dung: Giới thiệu khái niệm thuật toán/ thuật giải và độ phức tạp thuật toán, các kỹ thuật lập trình nâng cao, kỹ thuật tham lam (greedy), kỹ thuật quay lui (backtracking). Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình: Các kỹ thuật lập trình nâng cao - Trịnh Tấn Đạt (2024)

  1. Các kỹ thuật lập trình nâng cao 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/
  2. Nội dung  Giới thiệu khái niệm thuật toán/ thuật giải và độ phức tạp thuật toán.  Các kỹ thuật lập trình nâng cao  Kỹ thuật chia để trị (divide and conquer)  Kỹ thuật quy hoạch động (dynamic programming) o Bài toán dãy con tăng dài nhất (không liên tiép) o Bài toán Balô: loại 1 và 2  Kỹ thuật tham lam (greedy)  Kỹ thuật quay lui (backtracking)  …
  3. Giới thiệu  Tổng quan về thuật toán.  Thuật toán là gì? Tập hợp hữu hạn các hướng dẫn rõ ràng để giải quyết một bài toán(vấn đề). Mở rộng(máy tính): một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn.  Tính chất cơ bản của thuật toán: o Xác định = không mập mờ + thực thi được o Hữu hạn o Đúng
  4. Giới thiệu Ví dụ: – Một lớp học cần chọn lớp trưởng theo các bước: 1. Lập danh sách sinh viên 2. Sắp thứ tự 3. Chọn người đứng đầu làm lớp trưởng – Danh sách cần gì? – Sắp theo thứ tự nào? (tăng giảm, tiêu chí nào) – Nếu trùng tiêu chí thì giải quyết ra sao?
  5. Giới thiệu Sửa lại: a) Lập danh sách theo: họ tên, ngày tháng năm sinh, điểm các môn, điểm trung bình cuối năm. b) Sắp xếp theo ĐTB giảm. Nếu ĐTB bằng nhau  cùng hạng. c) Nếu có 01 HS đứng đầu  chọn, ngược lại chọn người có điểm toán cao nhất, nếu không chọn được  bốc thăm.  Phân biệt mập mờ và lựa chọn có quyết định: – Mập mờ là thiếu thông tin hoặc có nhiều lựa chọn nhưng không đủ điều kiện quyết định, ví dụ: bước 1, 2. – Lựa chọn có quyết định là hoàn toàn xác định duy nhất trong điều kiện cụ thể của vấn đề, ví dụ bước c.
  6. Giới thiệu  Tính thực thi được, ví dụ: – Tính  10 ? – Chạy xe thẳng từ ĐHSG đến sân bay TSN?  Tính dừng, ví dụ: – B1 nhập n; – B2 s=0; – B3 i=1; – B4 nếu i=n+1 sang B8, ngược lại sang B5 – B5 cộng i vào s – B6 cộng 2 vào i – B7 quay lại B4 – B8 Tổng cần tính là s
  7. Giới thiệu  Đặc trưng khác của thuật toán: – Xác định đầu vào/ra – Tính hiệu quả: khối lượng tính toán, không gian, thời gian. – Tính tổng quát Ví dụ: – giải ax2 + bx + c = 0 – Cho mảng các số nguyên A, tìm phần tử lớn nhất.  Các phương pháp biểu diễn thuật toán: – Ngôn ngữ tự nhiên – Sơ đồ (lưu đồ) khối – Mã giả (Pseudo-code)
  8. Giới thiệu  Khái niệm thuật giải  Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi là các thuật giải.  Đây là khái niệm mở rộng của thuật toán dựa trên tính xác định và tính đúng đắn. Ví dụ thuật giải Heuristic: – Nguyên lý vét cạn thông minh – Nguyên lý Greedy (tham lam) – Nguyên lý thứ tự
  9. Giới thiệu  Độ phức tạp của thuật toán
  10. Giới thiệu
  11. Giới thiệu  Ước lượng tiệm cận 1. Ý nghĩa: Phân lớp cấp độ lớn của các hàm f(n) khi n đủ lớn. Ký hiệu: O (big O – O lớn)  Thuật toán T có thời gian thực hiện là f(n) và f = O(g). Ta nói thuật tóan T có độ phức tạp g. Ví dụ : Thuật toán T, kích thước n, có thời gian chạy Ta nói “T có độ phức tạp tương đương n3”. Ký hiệu là O(n3)
  12. Giới thiệu  Phân loại
  13. Giới thiệu
  14. Giới thiệu  Cách tính big O:  Quy tắc cộng: Nếu K(n) và H(n) là thời gian thực hiện hai đọan chương trình P và Q liên tiếp, với K(n)=O(f(n)) và H(n)=O(g(n)) thì thời gian thực hiện hai đoạn này là T(n)=O(max(f(n),g(n))).  Quy tắc nhân: Nếu K(n) và H(n) là thời gian thực hiện hai đọan chương trình P và Q lồng vào nhau, với K(n)=O(f(n)) và H(n)=O(g(n)) thì thời gian thực hiện hai đoạn này là T(n) = O(f(n).g(n)). Ví dụ: - Thuật toán tìm kiếm tuyến tính trên mảng 1 chiều n phần tử có độ phức tạp O(n) - Thuật toán sắp xếp đổi chỗ trực tiếp (interchange sort) trên mảng 1 chiều n phần tử có độ phức tạp O(n2).
  15. Chia Để Trị (Divide and Conquer)
  16. Giới thiệu  Kỹ thuật quan trọng, được áp dụng rộng rãi để thiết kế các giải thuật có hiệu quả.  Để giải quyết một bài toán kích thước n, ta chia bài toán này thành một số bài toán con có kích thước nhỏ hơn. Giải các bài toán con này rồi tổng hợp kết quả lại để được lời giải ban đầu.  Những bài toán con này cũng có thể được chia thành các bài toán có kích thước nhỏ hơn nữa để giải quyết. Quá trình này sẽ đưa đến những bài toán mà lời giải là hiển nhiên hay dễ dàng thực hiện. Ta gọi những bài toán này là bài toán cơ sở.
  17. Một số bài toán tiêu biểu  Tính fast power an.  Tháp Hanoi  Tìm kiếm nhị phân  MergeSort và QuickSort  Nhân số nguyên lớn  Xếp lịch thi đấu thể thao  …
  18. Quick sort Quick Sort : dựa vào kỹ thuật chia để trị  Chọn một phần tử trong mảng làm điểm đánh dấu (pivot). Thuật toán sẽ thực hiện chia mảng thành các mảng con dựa vào pivot đã chọn.  Mấu chốt chính của thuật toán quick sort là việc phân đoạn dãy số dựa vào pivot - Mục tiêu của công việc này là: Cho một mảng và một phần tử x là pivot. Đặt x vào đúng vị trí của mảng đã sắp xếp. + Di chuyển tất cả các phần tử của mảng mà nhỏ hơn x sang bên trái vị trí của x + Di chuyển tất cả các phần tử của mảng mà lớn hơn x sang bên phải vị trí của x. - Khi đó ta sẽ có 2 mảng con: mảng bên trai của x và mảng bên phải của x. Tiếp tục công việc với mỗi mảng con(chọn pivot, phân đoạn) cho tới khi mảng được sắp xếp.
  19. Quick sort Một số cách để chọn pivot thường được sử dụng:  Luôn chọn phần tử đầu tiên của mảng.  Luôn chọn phần tử cuối cùng của mảng. (Được sử dụng trong ví dụ này)  Chọn một phần tử random.  Chọn một phần tử có giá trị nằm giữa mảng(median element).
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2