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! | BÀI 2 CÁC KIẾN THỨC CƠ BẢN Vũ Thương Huyền huyenvt@ 1 NỘ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@ 2 HÀM Toán rời rạc huyenvt@ 3 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@ 4 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@ 5 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@ 6 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@ 9 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 - 1 Ví 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@ 10 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@ 11 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@ 12 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 .
