CHƯƠNG III: ĐẶC TẢ CÁC THÀNH PHẦN CƠ BẢN
Các nội dung chính của chương:
III.1 ĐẶC TẢ KIỂU DỮ LIỆU.. 2
III.2 ĐẶC TẢ HÀM... 3
III.2.1 Cú pháp chung khi đặc tả hàm (dùng ngôn ngữ toán học) :3
III.2.2 Ví dụ 1:3
III.2.3 Ví dụ 2. 4
III.3 ĐẶC TẢ ĐỆ QUY.. 5
III.4 CÁC QUY TẮC TÍNH TOÁN.. 6
III.5 CÁC SƠ ĐỒ TRẠNG THÁI7
III.6 CÁC ĐỐI TƯỢNG HÌNH HỌC.. 8
III.7 CÁC RÀNG BUỘC.. 10
III.7.1 Ràng buộc trên kiểu dữ liệu. 10
III.7.2 Ràng buộc trên sơ đồ logic. 12
III.8 BÀI TẬP ÁP DỤNG.. 14
III.1 ĐẶC TẢ KIỂU DỮ LIỆU
Một kiểu dữ liệu bao gồm :
o Tập hợp các giá trị
o Hệ thống các phép toán cơ sở
Dựa trên các phép toán này, ta có thể đặc tả các phép toán còn lại.
Một phép toán (có thể được gọi là 1 hàm) là một ánh xạ riêng phần trên tập D Ì X :
Domain : điều kiện x Î D
Where: y là ảnh của x.
D được gọi là miền xác định của f.
Ta có các kiểu dữ liệu cơ bản như sau:
Ký hiệu
Tên kiểu
Các phép toán cơ sở
N
Các số tự nhiên (số nguyên không âm)
+, –, *, /
>, >=, <, <=, =, !=
Z
Các số nguyên
Q
Các số hữu tỉ
R
Các số thực
B
Kiểu logic, gồm 2 giá trị True và False
Ø, Ù, Ú, ®, «, Þ, Û
C
Kiểu các ký tự
>, >=, <, <=, =, !=
S
Các chuỗi ký tự
vXét kiểu dữ liệu chuỗi (S):
o Là tập hợp tất cả các chuỗi ký tự.
o Các hàm (phép toán) cơ sở bao gồm:
1.
Domain:
Where: b=True Û s là chuỗi rỗng
2.
Domain:
Where: s là chuỗi gồm đúng 1 ký tự là c
3.
Domain:
Where: t được tạo lập bằng cách chèn ký tự c vào đầu chuỗi s
4.
Domain: ØRong(s)
Where: t được tạo lập bằng cách xóa đi ký tự đầu của s.
5.
Domain: ØRong(s)
Where: c là ký tự đầu tiên của chuỗi s
III.2 ĐẶC TẢ HÀM
III.2.1 Cú pháp chung khi đặc tả hàm (dùng ngôn ngữ toán học) :
Domain : điều kiện x Î D
Where: y là ảnh của x.
X: tập các giá trị nguồn
Y: tập các giá trị đích
D: Miền xác định của hàm
III.2.2 Ví dụ 1:
Đặc tả các hàm sau:
1. Tìm căn bậc 2 của 1 số thực
2. Tìm phần nguyên của 1 số thực
3. Hàm DIV (2 số không âm)
4. Hàm MOD (2 số không âm)
Giải:
1.
2.
3.
4.
III.2.3 Ví dụ 2
Dựa vào các hàm cơ sở trên kiểu dữ liệu chuỗi, hãy đặc tả các hàm sau:
1. f: xóa 2 ký tự đầu của 1 chuỗi
2. g:Tìm phần tử thứ 2 của 1 chuỗi
3. h:Chèn 1 ký tự vào ví trí thứ 2 của chuỗi
Giải:
1.
2.
3.
Câu này còn có thể được đặc tả bằng 1 cách khác như sau (dựa vào 2 hàm f và g của câu 1 và câu 2):
hay có thể triển khai đầy đủ như sau:
III.3 ĐẶC TẢ ĐỆ QUY
Đặc tả đệ quy thực chất là cách thức đặc tả hàm theo dạng truy hồi. Một đặc tả được gọi là đệ quy nếu trong phần biểu thức Where của hàm có sử dụng đến chính bản thân hàm đang được đặc tả.
Ví dụ 1 : Ta xét hàm tìm kích thước của một chuỗi ký tự bất kỳ :
Ví dụ 2 : Xét hàm tính tổng các phần tử trong mảng a, kích thước n
MANG = Zn
Ví dụ 3 : Xét hàm đếm số lần xuất hiện của 1 số nguyên x trong mảng a, kích thước n
Ví dụ 4 : Hàm kiểm tra mảng tăng dần
III.4 CÁC QUY TẮC TÍNH TOÁN
Trong quá trình xây dựng các hệ thống phần mềm, đặc biệt là các hệ thống quản lý luôn có 1 yêu cầu không thể thiếu là thực hiện việc tính toán theo 1 hoặc 1 số quy tắc nhất định nào đó. Do vậy, việc đặc tả các quy tắc này là cần thiết, để nhằm đảm bảo cho việc tính toán được chính xác và đầy đủ.
Nguyên tắc chung khi đặc tả các quy tắc tính toán :
1. Đặt tên cho các đại lượng có liên quan đến quá trình tính toán
2. Xác định kiểu dữ liệu của các đại lượng này
3. Đặc tả hàm tính toán cho từng quy tắc
Ví dụ : Ta xét phần mềm quản lý thư viện với yêu cầu tính toán tiền phạt cho mỗi quyển sách khi trả sách trễ hạn với các yêu cầu khác nhau có thể có như sau :
a) Mỗi ngày trả trễ phạt 1000đ.
b) Mỗi ngày trả trễ phạt 1000đ, nhưng từ ngày trễ thứ 5 trở đi thì phạt 2000đ/ngày.
c) Có 2 loại sách A và B. Hình thức phạt như câu b), nhưng mức phạt khác nhau cho mỗi loại sách :
Loại A : 1000đ và 2000đ
Loại B : 1500đ và 2500đ
Giải :
Gọi t : số tiền phạt (t Î N)
n: số ngày trả trễ hạn (n Î N)
l: loại sách (l Î {A, B})
a)
b)
c)
III.5 CÁC SƠ ĐỒ TRẠNG THÁI
Một sơ đồ trạng thái thường dùng các hình vẽ để mô tả trạng thái và hoạt động của một đối tượng, 1 quá trình nào đó. Tuy nhiên, việc sử dụng hình vẽ khi xử lý trên máy tính lại tỏ ra hết sức khó khăn, độ chính xác lại không cao.
Ví dụ 1 : Sơ đồ hoạt động của 1 thang máy
Nguyên tắc chung khi đặc tả 1 sơ đồ trạng thái :
1. Gán các giá trị 1, 2, 3, … cho các trạng thái có trong sơ đồ
2. Gọi t1 : trạng thái hiện hành (t1ÎN)
t2 : trạng thái có thể chuyển đến trực tiếp từ t1 (t2ÎN)
3. Xây dựng các ràng buộc trên t1 và t2 dưới dạng một mệnh đề để mô tả các tình trạng có thể có của sơ đồ.
Để đặc tả sơ đồ trong ví dụ trên, ta đặt :
1 : Đi lên
2 : Dừng
3 : Đi xuống
t1 : trạng thái hiện hành t2 : trạng thái có thể chuyển đến từ t1
Ta có đặc tả :
Ví dụ 2: Sơ đồ mô trả trạng thái của 1 quyển sách trong thư viện
Để đặc tả sơ đồ trong ví dụ trên, ta đặt :
1 : Trạng thái chuẩn bị
2 : Sẵn sàng
3 : Tu bổ
4 : Cho mượn
5 : Mất
t1 : trạng thái hiện hành t2 : trạng thái có thể chuyển đến từ t1
Ta có đặc tả :
III.6 CÁC ĐỐI TƯỢNG HÌNH HỌC
Một điểm trên mặt phẳng được biểu diễn dưới dạng (x, y) trong đó x và y là 2 số thực biểu diễn hoành độ và tung độ của điểm đó. Ta định nghĩa kiểu dữ liệu :
DIEM = R ´ R
M Î DIEM
Ký hiệu : M.x hoành độ của M
M.y tung độ của M
Đặc tả 1 đối tượng hình học trên mặt phẳng là đặc tả hàm kiểm tra các điểm có liên quan có thỏa các điều kiện ràng buộc để tạo nên đối tượng hay không.
Dạng thức chung :
Ví dụ : Cho A, B, C, D là các điểm. Đặc tả các phát biểu sau :
a) A, B là 2 điểm trùng nhau
b) A, B, C là 3 điểm thẳng hàng
c) A, B, C là 3 đỉnh của 1 tam giác
d) AB // CD
e) AB ^ CD
f) C là trung điểm của AB
g) Hàm tính độ dài của đoạn thẳng AB
h) Hàm tính khoảng cách từ điểm A đến đường thẳng qua BC
Giải :
a)
b)
c)
d)
e)
f)
g)
h)
III.7 CÁC RÀNG BUỘC
III.7.1 Ràng buộc trên kiểu dữ liệu
Gọi T là tập hợp nền của kiểu dữ liệu T
Ràng buộc trên kiểu dữ liệu T là hàm kiểm tra tính hợp lệ :
Domain:
Where: bÛ t thỏa ràng buộc
Ví dụ : Kiểu dữ liệu NGAY, biểu diễn một (ngày, tháng, năm). Kiểu có thể có các tập hợp nền như sau :
a) NGAY Ì N´N´Z dÎNGAY à d = (ng, t, n)
b) NGAY Ì{1..31}´{1..12}´Z dÎNGAY à d = (ng, t, n)
c) NGAY Ì N´Z dÎNGAY à d = (stt, n)
d) NGAY Ì{1..366}´Z dÎNGAY à d = (stt, n)
Đặc tả hàm kiểm tra ngày hợp lệ dựa trên 4 tập hợp nền ở trên.
Giải :
Trước tiên, ta đặc tả hàm kiểm tra năm nhuận :
Sau đó đặc tả các hàm kiểm tra tính hợp lệ đối với từng tập hợp nền:
a) NGAY Ì N´N´Z
b) NGAY Ì{1..31}´{1..12}´Z
c) NGAY ÌN´Z
d) NGAY Ì{1..366}´Z
III.7.2 Ràng buộc trên sơ đồ logic
Các ràng buộc trên sơ đồ logic chính là các ràng buộc toàn vẹn trong cơ sở dữ liệu. Việc đặc tả các ràng buộc trên sơ đồ logic sử dụng ngôn ngữ đại số quan hệ (các vị từ và lượng từ).
Các ràng buộc toàn vẹn bao gồm :
o Các ràng buộc khóa nội, khóa ngoại
o Ràng buộc thuộc tính
o Ràng buộc thời điểm
o Ràng buộc liên thuộc tính
o v.v...
Ví dụ 1 : Xét phần mềm quản lý thư viện với sơ đồ logic như sau :
Độc giả (MĐG, MLĐG, Họtên, Địachỉ, Điệnthoại)
Loại ĐG (MLĐG, Tên, Ghichú)
Thể loại (MTL, Tên, Ghichú)
Sách (MS, MTL, Tên, NămXB, Tácgiả)
Mượn (MMượn, MĐG, Ngàymượn)
CTMượn (MMượn, MS, Ngàytrả)
Hãy đặc tả các ràng buộc sau :
o Ràng buộc về khóa nội, khóa ngoại
a) MĐG là duy nhất trong Độc giả
b) MTL của Sách phải có trong Thể loại
o Ràng buộc thuộc tính :
c) Ngày mượn phải khác rỗng
o Ràng buộc thời điểm :
d) Tại 1 thời điểm, sách chỉ có thể cho 1 độc giả mượn
o Ràng buộc liên thuộc tính :
e) Ngày trả sau ngày mượn
Giải :
a)
b)
c)
d)
e)
Ví dụ 2 : Xét phần mềm quản lý giải bóng đá với sơ đồ sau :
Đặc tả các ràng buộc :
a) Các trọng tài trong cùng 1 trận đấu phải cùng thuộc 1 quốc gia
b) Trong 1 trận đấu chỉ có 1 trọng tài chính
c) Trọng tài và các đội thi đấu không cùng thuộc 1 quốc gia
d) Mội trận đấu chỉ có 2 đội tham gia
III.8 BÀI TẬP ÁP DỤNG
1. Đặc tả các hàm tính toán sau :
a) Tìm n!
b) Tìm A(k,n) – chỉnh hợp chập k
c) Tìm C(k,n) – Tổ hợp chập k
d) Tìm USCLN của 2 số nguyên dương a, b
e) Tìm phần tử thứ n trong dãy Fibonacci :
F(n) = 1 nếu n£2
F(n) = F(n-1) + F(n-2) nếu n>2
2. Đặc tả các hàm sau trên dữ liệu kiểu chuỗi :
a) Xác định phần tử thứ k của chuỗi
b) Xóa phần tử thứ k của chuỗi
c) Xóa k ký tự đầu của chuỗi
d) Xóa k ký tự, kể từ vị trí thứ p trong chuỗi
e) Chèn 1 ký tự vào vị trí thứ k trong chuỗi
f) Tìm xem ký tự c có hay không có trong chuỗi
g) Đếm số lần xuất hiện của ký tự c trong chuỗi
3. Cho mảng a gồm toàn các số nguyên, kích thước n (n³0). Hãy đặc tả các hàm sau :
a) Tìm giá trị lớn nhất, nhỏ nhất trong mảng
b) Tính tổng các số chẵn có trong mảng
c) Kiểm tra xem mảng có thứ tự tăng dần / giảm dần hay không
d) Đếm số run của mảng
4. Tính tiền thuê phòng cho 1 khách sạn trong phần mềm quản lý khách sạn :
Có 3 loại phòng A, B, C
Loại A : 70.000đ/ngày
Loại B : 100.000đ/ngày
Loại C : 120.000đ/ngày
Mỗi phòng dành cho 2 khách nhưng có thể cho tối đa 3 khách thuê, tính phụ thêm 20% trong trường hợp thuê 3 người.
Nếu thuê lâu hơn 10 ngày sẽ giảm 10% trên tổng số tiền phải trả.
5. Tính tiền lương cho nhân viên trong phần mềm quản lý nhân viên :
Mỗi nhân viên có 1 mức lương tháng với số ngày công quy định là 22.
Mỗi ngày nghỉ trừ 50.000đ, nghỉ quá 5 ngày thì trừ toàn bộ. Mỗi ngày làm thêm thưởng 40.000đ
6. Cho A, B, C, D, G, H, O là các điểm trong mặt phẳng, hãy đặc tả các đối tượng và phát biểu sau :
a) ABC là tam giác cân tại A
b) ABC là tam giác cân
c) ABC là tam giác đều
d) G là trọng tâm của tam giác ABC
e) H là trực tâm của tam giác ABC
f) O là tâm đường tròn ngoại tiếp tam giác ABC
g) O là tâm đường tròn nội tiếp tam giác ABC
h) ABCD là tứ giác
i) ABCD là hình thang
j) ABCD là hình thang vuông
k) ABCD là hình thang cân
l) ABCD là hình bình hành
m) ABCD là hình thoi
n) ABCD là hình chữ nhật
o) ABCD là hình vuông
7. Xét chương trình quản lý thời điểm đến làm việc của các nhân viên. Hãy biểu diễn và đặc tả các ràng buộc trên kiểu dữ liệu THOI_DIEM tương ứng của nhân viên, biết rằng công ty mở cửa với giờ quy định :
Sáng từ 6h30 đến 7h15
Chiều từ 12h45 đến 13h30
ứng với các tập hợp nền như sau:
a) THOI_DIEM Ì N´N´N tdÎTHOI_DIEM à td = (h, m, s)
b) THOI_DIEM Ì {0..59}´{0..59}´N tdÎTHOI_DIEM à td = (h, m, s)
c) THOI_DIEM Ì N tdÎTHOI_DIEM à td = (stt), với stt là số giây tính từ thời điểm 0:00:00 của ngày.
d) THOI_DIEM Ì {0..86399}´N tdÎTHOI_DIEM à td = (stt), ý nghĩa giống câu c)
e) THOI_DIEM Ì {6, 7, 12, 13}´N tdÎTHOI_DIEM à td = (h, m)
8. Xét phần mềm đánh cờ tướng. Người ta biểu diễn kiểu dữ liệu QUAN_CO tương ứng với 1 quân cờ trên bàn cờ theo quy định như sau:
o Bàn cờ có 9 cột được đánh số thứ tự từ 0 đến 8 theo trình tự từ trái sang phải và có 10 dòng được đánh số thứ tự từ 0 đến 9 theo trình tự từ dưới lên trên.
o Tướng chỉ di chuyển thẳng hoặc ngang từng bước một trong cung
o Sĩ chỉ chuyển xiên từng bước một trong cung
o Tượng chỉ di chuyển xiên trong hình vuông cạnh bằng 2 và không thể qua sông.
o Chốt chỉ di chuyển thẳng từng bước một và khi qua sông có thể di chuyển ngang (cũng từng bước một).
Đặt NAME Ì C = {‘T’, ‘S’, ‘V’, ‘X’, ‘P’, ‘M’, ‘C’} là tập các tên quân cờ
Ta quy định tập hợp nền của kiểu dữ liệu QUAN_CO như sau :
QUAN_CO Ì NAME ´ {0..8} ´ {0..9} ´ {0, 1}
Trong đó giá trị 0 tương ứng với quân xanh, 1 tương ứng với quân đỏ.
Hãy đặc tả tất cả các vị trí hợp lệ của từng quân cờ trên bàn cờ.
9. Mô tả và đặc tả các ràng buộc trên kiểu dữ liệu PHONG ứng với các phòng trong khách sạn biết rằng :
a) Khách sạn có 25 tầng
b) Số phòng được đánh số thứ tự theo STT tầng và STT của phòng trong tầng
Ví dụ : Tầng 3 : 301, 302, ..., 314
Tầng 11 : 1101, 1102, ..., 1114
c) Khách sạn không có tầng 13
d) Tầng cuối cùng chỉ gồm có 1 phòng, tầng trệt gồm 2 phòng, các tầng còn lại có đúng 14 phòng
10.Mô tả và đặc tả các ràng buộc trên kiểu dữ liệu THANG_MAY tương ứng với các trạng thái của 1 thang máy, bao gồm :
o Tổng trọng lượng khách
o Tình trạng cửa (đóng / mở)
o Tình trạng di chuyển (lên, xuống, dừng)
Biết rằng :
a) Lúc di chuyển, cửa phải đóng
b) Cửa chỉ đóng khi tổng trọng lượng không quá 360kg
c) Không cho phép đổi hướng đột ngột giữa 2 tầng
Bạn đang đọc truyện trên: Truyen2U.Pro