Trường Đại học Công Nghệ Thông Tin, ĐHQG-HCM Khoa Công Nghệ Phần Mềm

Chương 7 Kiểu ánh xạ

23-02-2023

TS. Vu Thanh Nguyen

1

TS. Vũ Thanh Nguyên

Nội dung

23-02-2023

TS. Vu Thanh Nguyen

2

 Ánh xạ  Các hàm và thao tác trên ánh xạ  Đặc tả sử dụng ánh xạ

Kiểu ánh xạ

 Ví dụ: { “TH301” ↦ “Đặc tả hình thức”,

23-02-2023

TS. Vu Thanh Nguyen

3

“TH402” ↦ “Công cụ và Môi trường phát triển phần mềm”, “TH403” ↦ “Xây dựng phần mềm hướng đối tượng”, …}

Kiểu ánh xạ

 Tích Descarte:

 Nhắc lại:

A  B = {(a, b) | (a  A)  (b B)}

 Ánh xạ và tích Descarte:

 Cho A = {a1, a2, a3, a4, …}, B = {b1, b2, b3, …} {(a1, b1), (a2, b2), (a3, b1), (a4, b3)}  A  B

 Khi đó, ta có ánh xạ từ A vào B sau:

{a1↦ b1, a2 ↦ b2, a3 ↦ b1, a4 ↦ b3}

23-02-2023

TS. Vu Thanh Nguyen

4

Ánh xạ

 Đơn ánh: Mỗi phần tử trong tập nguồn tương ứng với tối đa 1

phần tử (ảnh) trong tập đích

 Toàn ánh: Mỗi phần tử trong tập nguồn đều có ảnh trong tập

đích

 Song ánh: Mỗi phần tử trong tập đích có duy nhất một tiền

ảnh trong tập nguồn

Tập nguồn

Tập đích

Ảnh

Tiền ảnh

23-02-2023

TS. Vu Thanh Nguyen

5

Định nghĩa kiểu ánh xạ

m

 Định nghĩa kiểu ánh xạ: A  B  Ví dụ 1: m f : ℤ  ℤ

 Ví dụ 2:

Acc-system::

m

m

custs: Name  Acc-no accs: Acc-no  Account

 Ví dụ 3:

m

thuộc-khoa: SINH-VIÊN  KHOA

 Ví dụ 4:

m

23-02-2023

TS. Vu Thanh Nguyen

6

phân-công: NHÂN-VIÊN  PHÒNG-BAN

Định nghĩa ánh xạ

 Định nghĩa ánh xạ thông qua tính chất:

{x ↦ y | Vị từ liên quan đến x và y}

 Ví dụ:

{p ↦ q | (p = 1  q = TRUE)  (p = 0  q = FALSE)}

23-02-2023

TS. Vu Thanh Nguyen

7

chính là {1 ↦ TRUE, 0 ↦ FALSE}

Hàm và thao tác trên ánh xạ

 Hàm Domain (dom)

m dom: A  B  A-set dom(m) ≝ { a |  b  B  ( (a ↦ b)  m)}

 Ý nghĩa: tập các phần tử trong tập nguồn A có ảnh trong tập

đích B

 Hàm Range (rng)

m

rng: A  B  B-set rng (m) ≝ { b |  a  A  ( (a ↦ b)  m)}

 Ý nghĩa: tập các phần tử trong tập đích B có tiền ảnh trong tập

23-02-2023

TS. Vu Thanh Nguyen

8

nguồn A

Hàm và thao tác trên ánh xạ

 Ví dụ:

23-02-2023

TS. Vu Thanh Nguyen

9

vowel {‘A’ ↦ 65, ‘E’ ↦ 69, ‘I’ ↦ 73, ‘O’ ↦ 79, ‘U’ ↦ 85} dom (vowel) = {‘A’, ‘E’, ‘I’, ‘O’, ‘U’} rng (vowel) = {65, 69, 73, 79, 85} vowel(‘A’) = 65 vowel(‘U’) = 85

Toán tử cập nhật †

m

m

m

 Cho m và n là 2 ánh xạ cùng kiểu _†_ : A  B  A  B  A  B m†n ≝

{ a ↦ b |

(( a  dom n)  (b = n(a)))

 ((a  (dom m – dom n))  (b = m(a))} hoặc { a ↦

(if a  dom n then n(a) else m(a) |

23-02-2023

TS. Vu Thanh Nguyen

10

a  (dom m  dom n) }

Toán tử cập nhật †

 Kết quả của m † n là tập hợp tất cả các bộ trong n và các bộ

trong m không có tiền ảnh/khóa trong dom(n)

23-02-2023

TS. Vu Thanh Nguyen

11

 Ví dụ: { 2 ↦ 4, 1 ↦ 3} † {3 ↦ 5, 1 ↦ 2} = {1 ↦2, 2 ↦ 4, 3 ↦ 5} { 3 ↦ 5, 1 ↦ 2} † {2 ↦ 4, 1 ↦ 3} = {1 ↦3, 2 ↦ 4, 3 ↦ 5}

Giả sử m1 = {a ↦ 1, c ↦ 3, d ↦ 1}, m2 = {b ↦ 4, c ↦ 5} m1†m2 = {a ↦ 1,b ↦ 4, c ↦ 5,d ↦ 1} m2†m1 = {a ↦ 1,b ↦ 4, c ↦ 3,d ↦ 1}

m†{} = m = {}†m

23-02-2023

TS. Vu Thanh Nguyen

12

Toán tử chọn các bộ theo tập khóa ⊲

m

m

_⊲_ : A-set  A  B  A  B s ⊲ m ≝

{ a ↦ m(a) | a  (dom m  s ) }

 Ý nghĩa: chọn lại những bộ trong ánh xạ có giá trị khóa cho

23-02-2023

TS. Vu Thanh Nguyen

13

trước

Toán tử chọn các bộ theo tập khóa ⊲

23-02-2023

TS. Vu Thanh Nguyen

14

 Ví dụ: { 2, 3, 4} ⊲ {1 ↦ 3, 4 ↦ 7, 3 ↦ 3} = {4 ↦ 7, 3 ↦ 3} { a, d, e} ⊲ m1 = {a ↦ 1, d ↦ 1} {} ⊲ m = {} s ⊲ {} = {}

_ Toán tử xóa bộ dựa vào tập khóa ⊲

m

m

_

_

_⊲_ : A-set  A  B  A  B s ⊲ m ≝

{ a ↦ m(a) | a  (dom m – s ) }

 Ý nghĩa: Xóa bỏ các bộ trong ánh xạ có giá trị khóa cho

_

_

23-02-2023

TS. Vu Thanh Nguyen

15

trước

_

_

_

_ Toán tử xóa bộ dựa vào tập khóa ⊲

23-02-2023

TS. Vu Thanh Nguyen

16

Ví dụ: { 2, 3, 4} ⊲ {1 ↦ 3, 4 ↦ 7, 3 ↦ 3} = {1 ↦ 3} { a, d, e} ⊲ m1 = {c ↦ 3} {} ⊲ m = m ma†mb = (dom mb – ma)  mb

Đặc tả với kiểu ánh xạ

m

m

23-02-2023

TS. Vu Thanh Nguyen

17

 Ví dụ: m Mã-HP  Tên-HP m Mã-GV  Mã-HP-set Mã-GV  Giảng-Viên Mã-SV  Sinh-Viên

Đặc tả với kiểu ánh xạ

 Ví dụ: Mã-HP = Char* Mã-SV = Char* HọTên = Char* Sinh-Viên ::

mã-SV: Mã-SV họ-tên: HọTên

Lớp ::

23-02-2023

TS. Vu Thanh Nguyen

18

mã-HP: Mã-HP mã-Lớp: ℕ1 học-kỳ: {1, 2, 3, 4} năm-học: ℕ1

Đặc tả với kiểu ánh xạ

m

= Sinh-Viên  Lớp-set

Đăng-ký Danh-sách-lớp= Lớp

m  Sinh-Viên-set

23-02-2023

TS. Vu Thanh Nguyen

19

Đặc tả với kiểu ánh xạ

 Ví dụ: Đặc tả hàm trả về các lớp mà sinh viên sv đã và đang

đăng ký học

DSĐăngKýHọc : Sinh-Viên  Đăng-ký  Đăng-ký DSĐăngKýHọc (sv, ds-đăng-ký) ≜

{sv} ⊲ ds-đăng-ký

DSLớpĐăngKýHọc : Sinh-Viên  Đăng-ký  Lớp-set DSLớpĐăngKýHọc (sv, ds-đăng-ký) ≜

23-02-2023

TS. Vu Thanh Nguyen

20

if (sv  dom ds-đăng-ký) then else ds-đăng-ký(sv) {}

Đặc tả với kiểu ánh xạ

↼

  Ví dụ: Đăng ký cho 1 sinh viên học 1 lớp ĐĂNG-KÝ-HỌC (sv: Sinh-Viên, lớp: Lớp) wr đk: Đăng-ký ext ↼ ({sv} ⊲ đk = {}) (lớp  ({sv} ⊲ đk)(sv))

pre post

↼

↼

(đk = đk † { sv ↦ ({sv} ⊲ đk )(sv)  {lớp}) }  ({sv} ⊲ đk  {}))

↼ ↼

↼

23-02-2023

TS. Vu Thanh Nguyen

21

 (đk = đk  { sv ↦ {lop})  ({sv} ⊲ đk = {}))

Đặc tả với kiểu ánh xạ

↼

↼

wr (sv  dom(đk))  ((sv  dom(đk))  (lớp  đk(sv)))

 Ví dụ: Đăng ký cho 1 sinh viên học 1 lớp ĐĂNG-KÝ-HỌC (sv: Sinh-Viên, lớp: Lớp) đk: Đăng-ký ext ↼ pre post

↼

↼

((đk = đk † { sv ↦ đk(sv)  {lớp}})  (sv  dom(đk)))

↼

↼ ↼

23-02-2023

TS. Vu Thanh Nguyen

22

 ((đk = đk  { sv ↦ {lop})  (sv  dom(đk)))