Bài giảng Đặc tả hình thức - Chương 4: Số và kiểu mảng - Vũ Thanh Nguyên

Chương 4: Số và Kiểu mảng Giảng viên: PGS.TS. Vũ Thanh Nguyên Trường Đại học Công Nghệ Thông Tin, ĐHQG-HCM Khoa Công Nghệ Phần Mềm 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 2Nội Dung Số và mảng là khái niệm quan trọng của Đặc tả hình thức Ngôn ngữ Z mô tả các dạng số - đặc biệt là số tự nhiên dùng tương ứng với mảng 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 3Kiểu Số Tập số nguyên Z = {, -2,-1,0,1,2,} Tập số tự nhiên N = {n:Z|n 0} = {0,1,2,} Tập số nguyên dương N1 = {n:Z|n>0} = {1,2,} 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 4Kiểu Số Tập số hữu tỉ Q = {x|x=m/n, m Z, n Z\{0}} Tập số vô tỉ I = {x|x m/n, m Z, n Z\{0}} Tập số thực R=Q I 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 5Kiểu Số  Các phép toán trên tập số nguyên 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 6Kiểu Số  Các phép toán trên số 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt Kiểu Số  Ví dụ về hàm trả lại giá trị tuyệt đối của một số nguyên sử dụng sự miêu tả rỏ ràng như sau:  abs Z Z n:Z n 0 abs n = -n n 0 abs n = n  Hàm successor (succ) trả lại giá trị của số tiếp theo của số tự nhiên  Succ = { 0 ↦ 1, 1 ↦ 2, 2 ↦ 3,}  Hàm predecessor (pred) trả lại giá trị của số phía trước  pred == succ∼ 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 8Kiểu Số Miền xác định của số  Miền xác định giữa 2 số a, b: Z được xác định như sau: a..b = {a, a+1, a+2,, b-2, b-1, b} Hoặc a..b = {n:Z| a n b} Nếu a > b khi đó a..b = ∅ và a..a = {a} 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 9Kiểu Số  Cardinality  Số phần tử của tập (số nguyên)  Xác định là card hay # (ngôn ngữ z)  Ví dụ: #∅ (hay #{}) = 0, #{a} = 1 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 Kiểu Số  Cardinality  Đối với miền xác định a..b #a..b = 1+b-a nếu a b = 0 nếu a > b #a..b = max {0, 1+b-a} Vậy nó tương ứng là 1 2 3 b-a 1+b-a ↧ ↧ ↧ ↧ ↧ a a+1 a+2 b-1 b 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 Kiểu mảng  Trong 1 số trường hợp, để ghi lại thứ tự nhất định của các đối tượng đã được sắp xếp thì ta sẽ sử dụng mảng. Mảng (sequence):  Gồm hữu hạn phần tử (0 hay nhiều phần tử)  Có thứ tự  Một phần tử có thể xuất hiện nhiều lần trong mảng  Các phần tử trong mảng có cùng kiểu dữ liệu 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 Kiểu mảng Mảng:  Mảng chỉ chứa một phần tử s = {1 ↦ x} có #s=1 và được viết là [x] còn gọi là mảng đơn  Tổng quát một mảng {1 ↦ x1, 2 ↦ x2, ,n ↦ xn} được viết ngắn gọn [x1, x2,,xn] 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 Kiểu mảng  Ví dụ: [4, 2, 7, 1, 5, 6, 3] [7, 2, 1, 4, 3, 6, 5] [„C‟, „O‟, „N‟] [42.0, 343.0, 42.0] [] (không giống tập mảng rổng xác định một kiểu dữ liệu) 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 14 Kiểu mảng 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 15 Kiểu mảng 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt Mảng  Cho trước kiểu T  Định nghĩa kiểu mảng mà mỗi phần tử thuộc kiểu T T*  Ví dụ: Word = Char* Smallstring = {„a‟, „b‟, „c‟}* Smallstring = { [], [„a‟], [„b‟], [„c‟], [„a‟, „a‟], [„a‟, „b‟], [„a‟,‟a‟, „c‟] } Paragraph = Word* Chapter = Paragraph* 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt Chuỗi  Chuỗi có thể xem là 1 mảng các ký tự  Ví dụ: [„D‟, „i‟, „s‟, „k‟, „ „, „f‟, „u‟, „l‟, „l‟] “Disk full”  Lưu ý: „a‟ Char “hello” Char* “a” Char* 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt Các hàm và thao tác trên mảng/chuỗi  Hàm len len [] = 0 len [1, 2, 3, 4, 1] = 5 Tổng quan len s = card dom s Một số ví dụ về mảng  [a,b] [b,a]  [a,b] [a,b,b]  Giả sử s1= [b,b,c] s2= [a] Khi đó len s1= 3, len s2= 1 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 Các hàm và thao tác trên mảng/chuỗi  Truy xuất phần tử trong mảng theo chỉ số (tính từ 1) sq = [2, 19, 13, 5, 17] sq(1) = 2 sq(4) = 5 Tổng quát s X* 1 i len s s(i) X  s1(1) = s1(2) = b 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 Các hàm và thao tác trên mảng/chuỗi Mảng/chuỗi con [„a‟, „a‟, „d‟, „c‟, „a‟, „b‟] (2, , 4) = [„a‟, „d‟, „c‟] “Hello” (2, , 2) = “e” s(1,, len s) = s 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt Các hàm và thao tác trên mảng/chuỗi  Phép nối ⃕  s ⃕ t  Ví dụ: “Hello” ⃕ “ ” ⃕ “World” = “Hello World” Một số quy tắc  []⃕s=s⃕[]=s  r⃕(s⃕t) = (r⃕s)⃕t  (r⃕s = r⃕t) s = t  Lưu ý  Nếu s,t T*, s t r:T* s⃕r = t 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt Các hàm và thao tác trên mảng/chuỗi 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt Các hàm và thao tác trên mảng/chuỗi 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt Các hàm và thao tác trên mảng/chuỗi  Cập nhật phần tử trong mảng †  Ví dụ: [1, 2, 3, 4] (3) †11 = [1, 2, 11, 4] 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 25 Các hàm và thao tác trên mảng/chuỗi  Lưu ý (ứng dụng cho tiếp đầu ngữ (prefix) của mảng):  (s t t s) s = t  (r s s t) r t  (r t s t) (r s s r) 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 26 Các hàm và thao tác trên mảng/chuỗi  Phép toán phân bố (ngôn ngữ Z)  ⃕/[] = []  ⃕/[a,b,,n] = a⃕b⃕ ⃕n  ⃕/([a]⃕s) = [a]⃕(⃕/s)  ⃕/(s⃕[a]) = (⃕/s)⃕[a] 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 27 Các hàm và thao tác trên mảng/chuỗi  Hàm Head (hd) và Tail (tl)  Ví dụ: hd [„p‟, „q‟, „r‟] = „p‟  Hàm head của một mảng không rổng có thể định nghĩa như sau: hd (s: X*) r:X pre s [] post r = s(1) 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 28 Các hàm và thao tác trên mảng/chuỗi  Hàm tail của một mảng không rổng có thể định nghĩa như sau: tl (s: X*) rs:X pre s [] post s = [hd s]⃕rs  Ví dụ tl [„p‟, „q‟, „r‟] = [„q‟, „r‟] tl [42] = []  Ví dụ: hd s1 = b hd s2 = a tl s1 = [b,c] tl s2 = [] 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 29 Các hàm và thao tác trên mảng/chuỗi  Chèn 1 phần tử vào đầu mảng (cons)  Ví dụ: cons (6, [2, 3]) = [6, 2, 3] 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt Các hàm và thao tác trên mảng/chuỗi  Hàm inds: trả về tập chỉ số của các phần tử trong mảng inds s = {i | 1 i len s}  Ví dụ: inds [12, 4, 6, 38, 12] = {1, 2, 3, 4, 5}  inds s = {1,,len s}  inds s1 = {1,2,3}  inds s2 = {1}  inds [] = {} 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 31 Các hàm và thao tác trên mảng/chuỗi  Hàm elems: trả về tập hợp các giá trị của các phần tử trong mảng elems s = {s(i) | i inds s}  Ví dụ: elems [12, 4, 6, 12, 4, 6, 38, 12] = {4, 6, 12, 38}  elems s2 = {a}  elems s1 = {b,c}  elems [] = {} 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 32 Các hàm và thao tác trên mảng/chuỗi  Hai mảng bằng nhau  sa = sb len sa = len sb i inds sa sa (i) = sb (i)  Các mảng có thể liên kết bởi hàm concat(sa:X * , sb:X *) rs:X* post len rs = len sa + len sb ( i inds sa rs(i) = sa(i)) ( i inds sb rs(i+len sa) = sb(i))  Hoặc dùng phép nối ⃕ (người ta thường dùng phép nối sa⃕sb hơn là hàm concat(sa,sb). 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 33 Các hàm và thao tác trên mảng/chuỗi  Các mảng có thể liên kết nhờ phép liên kết phân bố tất cả các mảng trong một mảng bởi hàm đệ quy sau: dconc : (X*)* → X* Dconc(ss) ≜ if ss = [] then [] else (hd ss)⃕dconc(tl ss)  Ví dụ: dconc[s1, [],s2,s2] = [b,b,c,a,a] 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 34 Các hàm và thao tác trên mảng/chuỗi  Xác định độ dài của mảng con của mảng đả cho có kích thước từ i tới j  subseq(s:X*, i:N1, j:N) rs:X * pre i j+1 i len s + 1 j len s post s1,s2 X * len s1 = i-1 len s2 = len s – j s= s1⃕rs⃕s2 Có thể thấy được rằng: len rs = len s – (i-1 + (len s -j)) = (j – i) + 1 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 35 Các hàm và thao tác trên mảng/chuỗi  Thường hàm subseq(i,j,q) được viết là s(i,,j)  Ví dụ:  s1(2,,2)=[b]  s1(1,,3)=[b,b,c]  s1(1,,0)=[]  s1(4,,3)=[] 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt 36 Các hàm và thao tác trên mảng/chuỗi  Sơ đồ của các phép toán trên mảng 4/5/2019 Prof.Dr.Vu Thanh Nguyen CuuDuongThanCong.com https://fb.com/tailieudientucntt