Bài toán và thuật toán

- Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH CHƯƠNG II BÀI TOÁN VÀ THUẬT TOÁN 2.1.
- 20 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH Ví dụ, trong một bài toán Tin học khi đề cập đến một số nguyên dương N ta phải biết rõ phạm vi giá trị của nó, để lựa chọn cách thể hiện N bằng kiểu dữ liệu thích hợp.
- Bước 2: Lựa chọn hoặc thiết kế thuật toán Bước lựa chọn và thiết kế thuật toán là bước quan trọng nhất để giải một bài toán.
- Mỗi thuật toán chỉ giải một bài toán nào đó, nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toán.
- Cần chọn một thuật toán phù hợp để giải bài toán đã cho.
- Khi lựa chọn thuật toán người ta thường quan tâm đến các tài nguyên như giờ CPU, số lượng ô nhớ.
- Trong thực tế, khi lựa chọn thuật toán người ta còn quan tâm tới việc viết chương trình cho thuật toán đó được dễ dàng.
- Việc thiết kế và lựa chọn thuật toán để giải một bài toán cụ thể cần căn cứ vào lượng tài nguyên mà thuật toán đòi hỏi và lượng tài nguyên thực tế cho phép.
- Bước 3: Viết chương trình Việc viết chương trình là một tổng hợp hữu cơ giữa việc lựa chọn cấu trúc dữ liệu và ngôn ngữ lập trình để diễn đạt đúng thuật toán.
- Khi viết chương trình ta cần lựa chọn một ngôn ngữ bậc cao, hoặc hợp ngữ, hoặc ngôn ngữ máy, hoặc một phần mềm chuyên dụng thích hợp cho thuật toán đã lựa chọn.
- Nếu 21 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH có sai sót, ta phải sửa chương trình rồi thử lại.
- KHÁI NIỆM THUẬT TOÁN 2.2.1.
- Định nghĩa Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán, ta nhận được Output cần tìm.
- Có nhiều cách trình bày thuật toán: dùng ngôn ngữ tự nhiên.
- Một số ví dụ Ví dụ 1: Mô tả thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số bất kì (nguyên hoặc thực).
- Các đặc trưng của thuật toán Tính hữu hạn: Sau một số hữu hạn lần thực hiện các thao tác thuật toán phải kết thúc.
- Tính xác định: Sau khi thực hiện một thao tác, hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo.
- Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.
- Tính chi tiết: Các thao tác trong thuật toán phải được xác định một cách chặt chẽ theo nghĩa đủ chi tiết để đối tượng thực hiện thuật toán có thể làm được.
- Tính phổ dụng: Thuật toán không chỉ cho phép giải một bài toán đơn lẻ mà áp dụng cho cả một lớp bài toán có cùng cấu trúc.
- 23 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH 2.3.
- THUẬT TOÁN TÌM KIẾM 2.3.1.
- Thuật toán tìm kiếm tuyến tính: Tìm kiếm tuyến tính hay tìm kiếm tuần tự.
- Tư tưởng thuật toán là bắt đầu bằng việc so sánh x với a1.
- Thuật toán tìm kiếm nhị phân: Thuật toán này có thể được dùng khi dãy số được sắp xếp đơn điệu theo thứ tự tăng hoặc giảm dần.Tư tưởng thuật toán là chọn phần tử ở vị trí giữa làm chốt, chia dãy thành 2 phần có kích thước nhỏ hơn.
- 24 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH Ví dụ: Cho dãy số: A .
- Dùng ngôn ngữ tựa Pascal: {Thuật toán áp dụng với dãy tăng dần} Procedure tìm kiếm nhị phân (x: Item, a1,a2,...,an: Item).
- ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 2.4.1 Khái niệm về độ phức tạp của một thuật toán Thước đo hiệu quả của một thuật toán là thời gian mà máy tính sử dụng để giải bài toán theo thuật toán đang xét, khi các giá trị đầu vào có một kích thước xác định.
- Một thước đo thứ hai là dung lượng bộ nhớ đòi hỏi để thực hiện thuật toán khi các giá trị đầu vào có kích thước xác định.
- Các vấn đề như thế liên quan đến độ phức tạp tính toán của một thuật toán.
- Sự phân tích thời gian cần thiết để giải một bài toán có kích thước đặc biệt nào đó liên quan đến độ phức tạp thời gian của thuật toán.
- Sự phân tích bộ nhớ cần thiết của máy 25 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH tính liên quan đến độ phức tạp không gian của thuật toán.
- Vệc xem xét độ phức tạp thời gian và không gian của một thuật toán là một vấn đề rất thiết yếu khi các thuật toán được thực hiện.
- Biết một thuật toán sẽ đưa ra đáp số trong một micro giây, trong một phút hoặc trong một tỉ năm, hiển nhiên là hết sức quan trọng.
- Độ phức tạp thời gian của một thuật toán có thể được biểu diễn qua số các phép toán được dùng bởi thuật toán đó khi các giá trị đầu vào có một kích thước xác định.
- Ví dụ: Xét thuật toán tìm số lớn nhất trong dãy n số a1, a2.
- Nếu coi mỗi lần so sánh hai số của thuật toán đòi hỏi một đơn vị thời gian (giây chẳng hạn) thì thời gian thực hiện thuật toán trong trường hợp xấu nhất là n-1 giây.
- Với dãy 64 số, thời gian thực hiện thuật toán nhiều lắm là 63 giây.
- Ta nói độ phức tạp là n-1 Ví dụ: Thuật toán về bài toán “Tháp Hà Nội” Bài toán “Tháp Hà Nội” như sau: Có ba cọc A, B, C bằng kim cương và 64 cái đĩa bằng vàng các đĩa có đường kính đôi một khác nhau.
- 26 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH Nếu n=1 thì rõ ràng là S1=1.
- Thuật toán về bài toán “Tháp Hà Nội” đòi hỏi 264−1 lần chuyển đĩa (xấp xỉ 18,4 tỉ tỉ lần).
- Nếu mỗi lần chuyển đĩa mất 1 giây thì thời gian thực hiện thuật toán xấp xỉ 585 tỉ năm!.
- Ta nói độ phức tạp là 2n−1 Hai thí dụ trên cho thấy rằng: một thuật toán phải kết thúc sau một số hữu hạn bước, nhưng nếu số hữu hạn này quá lớn thì thuật toán không thể thực hiện được trong thực tế.
- So sánh độ phức tạp của các thuật toán Một bài toán thường có nhiều cách giải, có nhiều thuật toán để giải, các thuật toán đó có độ phức tạp khác nhau.
- Thuật toán 1: Procedure tính giá trị của đa thức (a0, a1.
- Ta có thể tính P(x) theo thuật toán sau: 27 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH Thuật toán 2: Procedure tính giá trị của đa thức (a0, a1.
- {P là giá trị của đa thức P(x) tại x0} Ta hãy xét độ phức tạp của hai thuật toán trên.
- Đối với thuật toán 1: ở bước 2, phải thực hiện 1 phép nhân và 1 phép cộng với i=1.
- 2 2 Đối với thuật toán 2, bước 2 phải thực hiện n lần, mỗi lần đòi hỏi 2 phép tính (nhân rồi cộng), do đó số phép tính (nhân và cộng) mà thuật toán 2 đòi hỏi là 2n.
- Rõ ràng là thời gian thực hiện thuật toán 2 ít hơn so với thời gian thực hiện thuật toán 1.
- Ta nói rằng thuật toán 2 (có độ phức tạp là 2n) là thuật toán hữu hiệu hơn (hay nhanh hơn) so với thuật toán 1 (có độ phức tạp là n(n+3)/2).
- Để so sánh độ phức tạp của các thuật toán, điều tiện lợi là coi độ phức tạp của mỗi thuật toán như là cấp của hàm biểu hiện thời gian thực hiện thuật toán ấy.
- Định nghĩa 1: Ta nói hàm f(n) có cấp thấp hơn hay bằng hàm g(n) nếu tồn tại hằng số C>0 và một số tự nhiên n0 sao cho 28 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH |f(n.
- Trong tin học, nó được sử dụng rộng rãi để phân tích các thuật toán.
- 29 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH Định nghĩa 2: Nếu một thuật toán có độ phức tạp là f(n) với f(n)=O(g(n)) thì ta cũng nói thuật toán có độ phức tạp O(g(n.
- Nếu có hai thuật toán giải cùng một bài toán, thuật toán 1 có độ phức tạp O(g1(n.
- thuật toán 2 có độ phức tạp O(g2(n.
- mà g1(n) có cấp thấp hơn g2(n), thì ta nói rằng thuật toán 1 hữu hiệu hơn (hay nhanh hơn) thuật toán 2.
- Đánh giá độ phức tạp của một thuật toán 2.4.3.1.
- Thuật toán tìm kiếm tuyến tính Số các phép so sánh được dùng trong thuật toán này cũng sẽ được xem như thước đo độ phức tạp thời gian của nó.
- Từ đó, thuật toán tìm kiếm tuyến tính có độ phức tạp là O(n).
- Thuật toán tìm kiếm nhị phân Để đơn giản, ta giả sử rằng có n=2k phần tử trong bảng liệt kê a1,a2,...,an, với k là số nguyên không âm (nếu n không phải là lũy thừa của 2, ta có thể xem bảng là một phần của bảng gồm 2k+1 phần tử, trong đó k là số nguyên nhỏ nhất sao cho n < 2k+1).
- Ở mỗi giai đoạn của thuật toán vị trí của số hạng đầu tiên i và số hạng cuối cùng j của bảng con hạn chế tìm kiếm ở giai đoạn đó được so sánh để xem bảng con này còn nhiều hơn một phần tử hay không.
- Do đó thuật toán tìm kiếm nhị phân có độ phức tạp là O(log2n).
- Từ sự phân tích ở trên suy ra rằng thuật toán tìm kiếm nhị phân, ngay cả trong trường hợp xấu nhất, cũng hiệu quả hơn thuật toán tìm kiếm tuyến tính.
- SỐ NGUYÊN VÀ THUẬT TOÁN 2.5.1.
- Thuật toán Euclide Phương pháp tính ước chung lớn nhất của hai số bằng cách dùng phân tích các số nguyên đó ra thừa số nguyên tố là không hiệu quả.
- Dưới đây là phương pháp hiệu quả hơn để tìm ước số chung lớn nhất, gọi là thuật toán Euclide.
- Thuật toán này đã biết từ thời cổ đại.
- Nó mang tên nhà toán học cổ Hy lạp Euclide, người đã 31 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH mô tả thuật toán này trong cuốn sách “Những yếu tố” nổi tiếng của ông.
- Thuật toán Euclide dựa vào 2 mệnh đề sau đây.
- Bằng cách áp dụng liên tiếp thuật toán chia, ta tìm được: r0 = r1q1 + r2 0 ≤ r2 < r1 r1 = r2q2 + r3 0 ≤ r3 < r2.
- Ví dụ: Dùng thuật toán Euclide tìm UCLN(414, 662).
- 32 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH 2.5.2.
- Ta viết N duới dạng đa thức: 33 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH N = dn bn + dn-1 bn-1.
- Vì 16 là luỹ thừa của nên việc biến đổi biểu diễn số giữa hai hệ đếm 34 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH đó được thực hiện rất dễ dàng.
- THUẬT TOÁN ĐỆ QUY 2.6.1.
- Ta sẽ thấy rằng các thuật toán rút gọn liên tiếp bài toán ban đầu tới bài toán có dữ liệu đầu vào nhỏ hơn, được áp dụng trong một lớp rất rộng các bài toán.
- Định nghĩa: Một thuật toán được gọi là đệ quy nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn.
- Một số ví dụ Ví dụ 1: Tìm thuật toán đệ quy tính giá trị an với a là số thực khác không và n là số nguyên không âm.
- 35 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH Ta xây dựng thuật toán đệ quy nhờ định nghĩa đệ quy của an, đó là an+1=a.an với n>0 và khi n=0 thì a0=1.
- Ví dụ 2: Tìm thuật toán đệ quy để tính UCLN của hai số nguyên a,b không âm.
- Ví dụ 3: Hãy biểu diễn thuật toán tìm kiếm tuyến tính như một thủ tục đệ quy.
- Để tìm x trong dãy tìm kiếm a1,a2,...,an trong bước thứ i của thuật toán ta so sánh x với ai.
- Thuật toán tìm kiếm có dạng thủ tục đệ quy như sau.
- i 36 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH else if i = j then loacation.
- Ví dụ 4: Hãy xây dựng phiên bản đệ quy của thuật toán tìm kiếm nhị phân.
- Nếu chúng bằng nhau thì thuật toán kết thúc, nếu không ta chuyển sang tìm kiếm trong dãy ngắn hơn, nửa đầu của dãy nếu x nhỏ hơn giá trị giữa của của dãy xuất phát, nửa sau nếu ngược lại.
- 37 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH Có cách khác tính hàm giai thừa của một số nguyên từ định nghĩa đệ quy của nó.
- Thông thường để tính một dãy các giá trị được định nghĩa bằng đệ quy, nếu dùng phương pháp lặp thì số các phép tính sẽ ít hơn là dùng thuật toán đệ quy (trừ khi dùng các máy đệ quy chuyên dụng).
- Theo thuật toán này, để tìm fn ta biểu diễn fn = fn-1 + fn-2.
- 38 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH Thủ tục lặp Procedure Iterative fibonacci (n).
- Ta đã chỉ ra rằng số các phép toán dùng trong thuật toán đệ quy nhiều hơn khi dùng phương pháp lặp.
- 39 Bài toán và thuật toán Nguyễn Thế Vinh - ĐHKH BÀI TẬP CHƯƠNG II Bài tập tính toán 2.1.1.
- Lập thuật toán ít nhất 2 thuật toán tính xn với x là một số thực và n là một số nguyên.
- Đánh giá độ phức tạp của từng thuật toán.
- Mô tả thuật toán chèn một số nguyên x vào vị trí thích hợp trong dãy các số nguyên a1, a2.
- Tìm thuật toán xác định vị trí gặp đầu tiên của phần tử lớn nhất trong bảng liệt kê các số nguyên, trong đó các số này không nhất thiết phải khác nhau.
- Tìm thuật toán đảo ngược một dãy số nguyên gồm n số.
- Đánh giá độ phức tạp của thuật toán đó