Bài giảng Thuật toán - Algorithms

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Module #5:Thuật toánAlgorithms Rosen 5th ed., §2.1 ~31 slides, ~1 lecture Abu al-Khowarizmi(ca. 780-850) Chapter 2: More Fundamentals §2.1: Algorithms Formal procedures §2.2: Orders of Growth §2.3: Complexity of algorithms Analysis using order-of-growth notation. §2.4: The Integers & Division Some basic number theory. §2.5: Integers & Algorithms Alternate bases, algorithms for basic arithmetic §2.6: Number theory applications Public-Key Cryptography §2.7: Matrices Some basic linear algebra. §2.1: Thuật toán - Algorithms Là cơ sở của lập trình trên máy tính. Tổng quát nhất, thuật toán là thủ tục xác định để thực hiện một nhiệm vụ nào đó. Chương trình máy tính là sử thể hiện thuật toán bằng ngôn ngữ chính xác để máy tính hiểu được, chỉ được dùng một số thao tác mà máy tính biết cách tính. Ta nói rằng chương trình cài đặt (implements) thuật toán của nó. Các thuật toán mà bạn đã biết Các thuật toán số học ở phổ thông: How to add any two natural numbers written in decimal on paper, using carries. Similar: Subtraction using borrowing. Multiplication & long division. Your favorite cooking recipe. How to register for classes at UF. Programming Languages Một số ngôn ngữ lập trình: Newer: Java, C, C++, C#, Visual Basic, JavaScript, Perl, Tcl, Pascal, many others… Older: Fortran, Cobol, Lisp, Basic Assembly languages, for low-level coding. Đôi khi người ta dùng ngôn ngữ mô tả, giả code tựa Pascal (“pseudo-code” language). Bạn cần phải biết tốt ít nhất một ngôn ngữ lập trình! Ví dụ thuật toán Task: Given a sequence {ai}=a1,…,an, aiN, say what its largest element is. Một thuật toán giải nó là: Đặt giá trị cho biến tạm thời v (phần tử lớn nhất đang có) là giá trị của a1. Xét phần tử tiếp theo ai trong dãy. Nếu ai>v, thì gán lại v bằng ai. Lặp lại hai bước trên cho đến khi không còn phần tử nào trong dãy và trả về v. Nếu thêm yêu cầu cho biết thứ tự của phần tử lớn nhất đó? Thực hiện thuật toánExecuting an Algorithm Khi bạn khởi động một phần mềm, bạn nói chương trình hoặc thuật toán của nó bắt đầu chạy hoặc thực hiện bởi máy tính. Cho mô tả bạn có thể tính bằng tay thuật toán bằng cách làm từng bước với bút và giấy. Trước ~1940, “computer” là người mà công việc là thực hiện thuật toán. Executing the Max algorithm Let {ai}=7,12,3,15,8. Find its maximum… Set v = a1 = 7. Look at next element: a2 = 12. Is a2>v? Yes, so change v to 12. Look at next element: a2 = 3. Is 3>12? No, leave v alone…. Is 15>12? Yes, v=15… Các đặc trưng của thuật toán Algorithm Characteristics Một số tính chất chung quan trọng của thuật toán: Input. Thông tin và dữ liệu nhập vào. Output. Thông tin và dữ liệu lấy ra. Definiteness. Thuật toán được xác định chính xác Correctness. Outputs phản ánh đúng inputs. Finiteness. Không chạy mãi mãi. Effectiveness. Các bước nhỏ để khả thi. Generality. Làm việc với nhiều đầu vào có thể. Efficiency. Thời gian và bộ nhớ để chạy. Our Pseudocode Language: §A2 procedurename(argument: type) variable := expression informal statement begin statements end {comment} if condition then statement [else statement] for variable := initial value to final value statement while condition statement procname(arguments) Not defined in book: return expression procedure procname(arg: type) Thông báo rằng đoạn sau xác định thủ tục tên là procname lấy đầu vào (arguments) tên là arg mà là đối tượng dữ liệu kiểu type. Example:procedure maximum(L: list of integers) [statements defining maximum…] variable := expression Là lệnh gán, trước hết tính giá trị của biểu thức expression, sau đó gán lại giá trị kết quả tính được cho biến vế trái variable . Example assignment statement:v := 3x+7 (If x is 2, changes v to 13.) Trong giả code, biểu thức expression có thể được mô tả không hình thức: x := the largest integer in the list L Lệnh không hình thứcInformal statement Đôi khi ta có thể viết lệnh dưới dạng câu nói không hình thức, nhưng phải rõ ràng và chính xác: e.g.,“swap x and y” Nên nhớ rằng ngôn ngữ lập trình thực tế không cho phép như vậy. Sau này ta sẽ triển khai chi tiết thêm cho thuật toán bằng các bước cụ thể cho đến các thao tác mà máy tính hiểu được. begin statements end Groups a sequence of statements together:begin statement 1 statement 2 … statement n end Cho phép dùng một dãy các câu lệnh như một lệnh đơn. Có thể dùng: Sau khai báo thủ tục. Trong lệnh if …sau then hoặc else. Trong thân của vòng for hoặc while. Curly braces {} are used insteadin many languages. Chú giải {comment} Không thực hiện (không làm gì). Văn bản ngôn ngữ tự nhiên giải thích một khía cạnh nào đó của thủ tục cho người đọc. Còn gọi là remark trong một số ngôn ngữ lập trình, như BASIC. VD, có thể xuất hiện trong max program: {Nhan thay v la so nguyen lon nhat hien tai} if condition then statement Tính giá trị của biểu thức mệnh đề condition. Nếu kết quả đúng True, thì thực hiện lệnh statement; Ngược lại bỏ qua đến lệnh tiếp theo sau lệnh if statement . Biến thể: if cond then stmt1 else stmt2 Giống trước, nhưng nếu cond là sai False, thì thực hiện stmt2. while condition statement Tính toán giá trị Bool của mệnh đề condition. Nếu giá trị trả về là True, thì thực hiện statement. Tiếp tục lặp hai hành động trên cho đến khi condition nhận giá trị False; thì thoát ra khỏi vòng while đến lệnh tiếp theo. while condition statement Nó cũng tương đuơng với lồng vô hạn if, như sau: if condition begin  statement  if condition  begin  statement  …(continue infinite nested if’s) end end for var := initial to final stmt Initial là biểu thức số nguyên. Final là biểu thức số nguyên khác. Ngữ nghĩa - Semantics: thực hiện lặp stmt, trước tiên với biến var := initial, sau đó với biến var := initial+1, tiếp theo với var := initial+2, …, sau cùng với var := final. Câu hỏi: Điều gì xảy ra nếu stmt thay đổi giá trị của biến var, hoặc giá trị của initial hoặc final cũng thay đổi? for var := initial to final stmt For can be exactly defined in terms of while, like so: begin var := initial while var  final begin stmt var := var + 1 endend Thủ tục procedure(argument) Lệnh gọi thủ tục (procedure call) bằng cách viết tên thủ tục procedure, cho nó đầu vào là giá trị của biểu thức argument. Nhiều ngôn ngữ lập trình khác nhau coi thủ tục như hàm functions (vì khái niệm thủ tục làm việc giống như với sử dụng hàm f(x)), hoặc như chương trình con hay phương thức. Max procedure in pseudocode procedure max(a1, a2, …, an: integers) v := a1 {largest element so far} for i := 2 to n {go thru rest of elems} if ai > v then v := ai {found bigger?} {at this point v’s value is the same as the largest integer in the list} return v Nghĩ ra thuật toánInventing an Algorithm Đòi hỏi nhiều sự sáng tạo và cảm giác Giống như viết chứng minh. Tuy nhiên, ta không thể đưa ra thuật toán để sáng tạo ra thuật toán. Xem nhiều ví dụ… Thực hành trên máy tính (preferably, on a computer) Xem thêm ví dụ nữa… Va thực hành tiếp Học môn phân tích và thiết kế thuật toán,.... Ví dụ nghĩ ra thuật toán G/s ta phải viết thuật toán để tính vị từ: IsPrime:N→{T,F} Tính xem số tự nhiên cho trước có phải là số nguyên tố không. Trước hết, bắt đầu bằng định nghĩa của logic vị từ về hàm định nghĩa số nguyên tố: n: IsPrime(n)  ¬11 & 1 is a, and let b :≡ n/a. Then n = ab, but if a > n1/2 then b > n1/2 (since a is n’s smallest divisor) and so n = ab > (n1/2)2 = n, an absurdity. Further optimizations are possible: - E.g., only try divisors that  are primes less than n1/2. Note smaller range of search. Another example task Bài toán tìm kiếm trong danh sách được sắp xếp - Problem of searching an ordered list. Given a list L of n elements that are sorted into a definite order (e.g., numeric, alphabetical), And given a particular element x, Determine whether x appears in the list, and if so, return its index (position) in the list. Problem occurs often in many contexts. Let’s find an efficient algorithm! Search alg. #1: Linear Search procedure linear search(x: integer, a1, a2, …, an: distinct integers)i := 1 {start at beginning of list}while (i  n  x  ai) {not done, not found} i := i + 1 {go to the next position}if i  n then location := i {it was found}else location := 0 {it wasn’t found}return location {index or 0 if not found} Search alg. #2: Tìm kiếm nhị phân Binary Search Basic idea: On each step, look at the middle element of the remaining list to eliminate half of it, and quickly zero in on the desired element. x 1 item} m := (i+j)/2 {midpoint} if x>am then i := m+1 else j := mendif x = ai then location := i else location := 0return location Practice exercises 2.1.3: Devise an algorithm that finds the sum of all the integers in a list. [2 min] procedure sum(a1, a2, …, an: integers) s := 0 {sum of elems so far} for i := 1 to n {go thru all elems} s := s + ai {add current item} {at this point s is the sum of all items} return s Các thuật toán sắp xếp Sorting Algorithms Sorting is a common operation in many applications. E.g. spreadsheets and databases It is also widely used as a subroutine in other data-processing algorithms. Two sorting algorithms shown in textbook: Bubble sort Insertion sort However, these are notvery efficient, and you shouldnot use them on large data sets! We’ll see some more efficient algorithms later in the course. Các phần tử nhỏ hơn sẽ “nổi” lên trên trong danh sách như bọt nổi lên trong bình đựng chất lỏng. Sắp xếp nổi bọt - Bubble Sort Thuật toán chènInsertion Sort Algorithm Mô tả thuật toán: Với mỗi đồ vật trong danh sách đầu vào, “Chèn” nó vào đúng chỗ trong danh sách đầu ra đã được sắp xếp. Giống như: Sử dụng tìm kiếm tuyến tính hoặc nhị phân để tìm chỗ cho đồ vật mới cần phải chèn Sau đó đẩy các vật ra xa thêm một vị trí. Chèn vật mới vào chỗ vừa tạo ra. Tóm tắt §2.1: Algorithms Đặc trưng của thuật toán. Giả code - Pseudocode. VD: Max algorithm, primality-testing, linear search & binary search algorithms. Sorting. Use methods of Cảm giác binary search nhanh hơn nhiều linear search, nhưng lập luận phân tích tính hiệu quả như thế nào? Độ phức tạp thuật toán - algorithmic complexity, mà sử dụng khái niệm cấp độ tăng trong §1.8.