Bài giảng Toán rời rạc: Bài 2 - Vũ Thương Huyền

Bài giảng Toán rời rạc: Bài 2 - Vũ Thương Huyền cung cấp cho học viên các kiến thức cơ bản về hàm; đồ thị của hàm; độ tăng của hàm; độ tăng của tổ hợp các hàm; thuật toán, độ phức tạp của thuật toán; khái niệm Big-Omega và Big-Theta; thuật toán tìm kiếm tuyến tính; thuật toán sắp xếp;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Bài 2 - Vũ Thương Huyền BÀI 2CÁC KIẾN THỨC CƠ BẢN Vũ Thương Huyền huyenvt@tlu.edu.vn 1NỘI DUNG • Hàm • Độ tăng của hàm • Thuật toán • Độ phức tạp của thuật toán Toán rời rạc huyenvt@tlu.edu.vn 2 2.1 HÀMToán rời rạc huyenvt@tlu.edu.vn 31.8 HÀM • Dùng để định nghĩa các cấu trúc rời rạc như dãy, xâu • Dùng để biểu diễn thời gian một máy tính phải mất để giải một bài toán Toán rời rạc huyenvt@tlu.edu.vn 41.8 HÀM Định nghĩa 1: Cho A và B là hai tập hợp. Một hàm f từ A đến B là sự gán chính xác một phần tử của B cho mỗi phần tử của A. Ta viết ? ? = ? nếu b là phần tử duy nhất của B được gán bởi hàm f cho phần tử a của A. Nếu f là hàm từ A đến B ta viết: ?: ? → ?. Toán rời rạc huyenvt@tlu.edu.vn 51.8 HÀM Định nghĩa 2: Nếu f là một hàm từ A đến B. • A được gọi là miền xác định của f và B là miền giá trị của f. • Nếu f(a) = b, b gọi là ảnh của a và a là một nghịch ảnh của b. • Tập ánh xạ qua hàm f là tập các ảnh của các phần tử thuộc A • f ánh xạ A đến B Ví dụ: Cho A= {1, 2, 3}, B ={a, b, c} • Hàm f được định nghĩa: 1 → ?, 2 → ?, 3 → ? • 1 → ?, c là ảnh của 1 • 2 → ?, 2 là nghịch ảnh của a • Miền xác định của f {1, 2, 3}, miền giá trị của f {a, b, c} • Tập ánh xạ f {a, c} Toán rời rạc huyenvt@tlu.edu.vn 61.8 HÀM - HÀM ĐƠN ÁNH Định nghĩa 5: Một hàm f được gọi là đơn ánh hay ánh xạ một-một nếu và chỉ nếu ? ? = ?(?) kéo theo x = y với mọi x và y trong miền xác định của f. Không đơn ánh Đơn ánh Toán rời rạc huyenvt@tlu.edu.vn 91.8 HÀM - HÀM ĐƠN ÁNH Các hàm sau có là hàm đơn ánh không?Ví dụ 1: • Cho A = {1, 2, 3} và B = {a, b, c}, hàm f được cho như sau: • 1 → ?, 2 → ?, 3 → ?Ví dụ 2:• Cho g: ? → ? , với g(x) = 2x - 1Ví dụ 3: • Hàm f(x) = x2 , x thuộc tập các số nguyên, miền giá trị của f cũng là tập các số nguyên. Toán rời rạc huyenvt@tlu.edu.vn 101.8 HÀM - HÀM TOÀN ÁNH Định nghĩa 7: Một hàm f từ A đến B được gọi là toàn ánh nếu và chỉ nếu với mọi phần tử ? ∈ ? tồn tại một phần tử ? ∈ ?, với ? ? = ?. Toán rời rạc huyenvt@tlu.edu.vn 111.8 HÀM - HÀM TOÀN ÁNHĐịnh nghĩa 8:Một hàm f là một song ánh nếu nó vừa là đơn ánh vừa là toàn ánh. (1)? (2)? (3)? (4)? (5)? Toán rời rạc huyenvt@tlu.edu.vn 121.8 HÀM – ĐỒ THỊ CỦA HÀM Định nghĩa 11: Cho f là hàm từ tập A đến tập B. Đồ thị của hàm f là tập các cặp sắp thứ tự ?, ? | ? ∈ ? ?à ? ? = ? . ? ? = 2? + 1 ? ? = ?2 Một số hàm quan trọng: • Hàm sàn • Hàm trần Toán rời rạc huyenvt@tlu.edu.vn 131.8 HÀM - HÀM TOÀN ÁNH Định nghĩa 12: Hàm sàn gán cho số thực x số nguyên lớn nhất có giá trị nhỏ hơn hoặc bằng x. Giá trị của hàm sàn được kí hiệu x. Hàm trần gán cho số thực x số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x. Giá trị của hàm trần được kí hiệu là x.Ví dụ: • 2,1 = ? • 2,1 = ? • -2,1 = ? • -2,1 = ? Toán rời rạc huyenvt@tlu.edu.vn 14BÀI TẬP Bài 1: Hãy xác định xem hàm f: ? × ? → ? có toàn ánh không? a) ? ?, ? = 2? − ? b) ? ?, ? = ? − |?| Bài 2: Hãy xác định xem hàm f: ? → ? có song ánh không? (?+1) a) ? ? = −3? + 4 b) ? ? = (?+2) 15 Toán rời rạc huyenvt@tlu.edu.vn 2.2 ĐỘ TĂNG CỦA HÀMToán rời rạc huyenvt@tlu.edu.vn 162.2 ĐỘ TĂNG CỦA HÀM Đánh giá thuật toán như thế nào? • Thời gian đòi hỏi để giải một bài toán phụ thuộc vào số phép toán được sử dụng • Ước lượng thời gian bằng cách nhân thời gian đòi hỏi với một hằng số. • Sử dụng khái niệm big-O: đánh giá số phép toán được dùng trong một thuật toán khi đầu vào của nó tăngĐịnh nghĩa 1:Cho hàm f và g là hai hàm từ tập các số nguyên hoặc số thực đếntập các số thực. Ta nói f(x) là O(g(x)) (đọc là f(x) là big-O của g(x)nếu tồn tại hai hằng số C và k sao cho: ? ? ≤? ? ? ,với mọi x>k Toán rời rạc huyenvt@tlu.edu.vn 172.2 ĐỘ TĂNG CỦA HÀMVí dụ : Chứng minh rằng f(x) = x2 +2x+1 là O(x2) Toán rời rạc huyenvt@tlu.edu.vn 18MỘT SỐ KẾT QUẢ QUAN TRỌNGĐịnh lí 1: Cho f(x) = anxn + an-1xn-1 + ... + a1x + a0 , ở đây a0, a1, ..., an là các số thực. Khi đó f(x) là O(xn). • 1+ 2 + ... + n là O(n2) • n! là O(nn) • logn! là O(nlogn) ...