Nguyên lý và phương pháp lập trình

Nguyên Lý Và Phương Pháp Lập Trình MỘT SỐ BÀI TẬP TRONG CÁC CHƯƠNG Bài 1. Cho biết các phẩm chất của chương trình và giải thích các phẩm chất đó? Có 10 phẩm chát của chương trình: - Tính đúng đắn, tính chính xác (correctness): chương trình phải thực hiện được và đáp ứng đúng chức năng theo yêu cầu lập trình ban đầu. - Tính chắc chắn (robustness): phân tích chương trình thành các chương trình con, tính độc lập giữa các chương trình con của chương trình càng cao càng tốt. - Tính thân thiện (user friendliness): chương trình phải dễ nhìn, trực quan và dễ sử dụng. - Khả năng thích nghi (adapability): chương trình có khả năng phát triển, tiến hóa theo yêu cầu. - Tính tái sử dụng (reuseabitilty): chương trình có thể dùng làm một phần trong chương trình khác. - Tính tương liên (interoperability): khả năng tương tác với người dùng và với phần mềm khác. - Tính hiệu quả (efficiency): chương trình phải thực hiện được chức năng của nó trong giới hạn tài nguyên sao cho là thấp nhất. - Tính khả chuyển (porability): khả năng chuyển đổi dễ dàng giữa các môi trường. - Tính an toàn (security): chương trình phải đảm bảo an toàn thông tin cho hệ thống máy tính vận hành, không phát sinh hay lây lan virus làm tổn hại đến hệ thống. - Tính dừng (halt): chương trình không được chạy vô hạn mà phải được dừng sau một khoảng thời gian xác định. Bài 2. Giải thích tính dừng của chương trình? Chương trình không được chạy vô hạn mà phải được dừng sau một khoảng thời gian xác định. Có nghĩa là: - Chương trình phải tồn tại một điều kiện dừng (điều kiện kết thúc) để có thể xuất ra kết quả cho người dùng. - Nếu không xuất ra được kết quả mong muốn thì chương trình cũng phải thông báo lỗi cho người dùng biết đồng thời kết thúc chương trình khi giới hạn tài nguyên vượt mức cho phép. Bài 3. Giải thích tính đúng đắn của chương trình, nguồn gốc các sai sót. Cho biết các cách kiểm tra tính đúng đắn của chương trình? Tính đúng đắn, tính chính xác (correctness): chương trình phải thực hiện được và đáp ứng đúng chức năng theo yêu cầu lập trình ban đầu. Có 3 nguồn gốc các sai sót: - Dữ liệu. - Cú pháp. - Ngữ nghĩa. Các cách kiểm tra tính đúng đắn của chương trình: - Sai sót dữ liệu: dùng bộ kiểm tra dữ liệu. - Sai sót cú pháp: dùng trình biên dịch. - Sai sót ngữ nghĩa: khó phát hiện, ta có thể sử dụng:  Test nội bộ.  Test người dùng. - Phương pháp kiểm sửa ngẫu nhiên:  Đảm bảo mọi trường hợp đều được kiểm tra.  Thường bị lỗi ở những gã rẽ, phải duyệt qua ít nhất một lần.  Thêm vào m lỗi giả trong chương trình N lỗi. Bài 4. Cho biết các kỹ thuật tối ưu hóa chương trình và đưa ra ví dụ minh họa? Bài 5. Các kỹ thuật tối ưu hóa thời gian? Có 3 cách tối ưu hoá chương trình: - Tối ưu hoá thời gian (tăng không gian). - Tối ưu hoá không gian (tăng thời gian). - Tối ưu hoá thời gian và không gian (thuật toán thay đổi). Tối ưu hoá thời gian và tối ưu hoá không gian: thuật toán không thay đổi mà thay đổi cấu trúc dữ liệu và cấu trúc chương trình. Tối ưu hoá thời gian và không gian thuật toán sẽ thay đổi ( ở các vòng lặp, việc rẻ nhánh, cấu trúc điều khiển,) Tối ưu hoá thời gian: - Kỹ thuật tối ưu hoá việc rẽ nhánh. + Không thế để các điều kiện Ai theo thứ tự ngẫu nhiên. + Phải sắp các Ai theo xác suất sai của Ai giảm dần. - Kỹ thuật tối ưu các vòng lặp. + Tách các lệnh không phụ thuộc vào chỉ số lặp ra khỏi vòng lặp. + Giảm số toán tử phức tạp trong vòng lặp nhờ các biến phụ. VD: Đoạn chương trình gốc Đoạn chương trình tối ưu vòng lặp sin(x) + sx=sin(x) vòng lặp sx + + Giảm số vòng lặp trong chương trình. Thực hiện nhiều công việc hơn trong mỗi vòng lặp. Đoạn chương trình gốc Đoạn chương trình tối ưu for(i=1,i<=1000,i++) a[i]=0; for(i=1,i<=500,i++) { a[i]=0; a[i+500]=0; } + Vòng lăp nào có số lần lặp ít sẽ nằm ngoài vòng lặp có số lần lặp nhiều hơn. + Thực hiện hợp nhất các vòng lặp có thể. - Tránh gọi lặp một thủ tục: giảm tối đa việc gọi các thủ tục, hàm. - Thay đổi, bố trí cấu trúc dữ liệu. - + Dùng biến phụ thay cho các biểu thức phải tính toán nhiều. - + Dùng bảng truy cập để tính toán. - Một số nguyên lý trong tối ưu hoá chương trình. + Nguyên lý Vanwik: là nguyên lý phân cấp bộ nhớ, dữ liệu thường được truy cập nhiều phải được truy cập nhanh nhất. + Nguyên lý đôi xứng: là nguyên lý đối ngẫu hay nguyên lý tính phần bù. Tính một phần rồi lấy đối xứng, không cần tính toàn bộ. Tối ưu hoá không gian: - Nguyên lý nén dữ liệu: + Giảm khoảng trống. + Mã lặp. + Mã hoá dựa vào tần suất. + Mã nền. + Ánh xạ co dữ liệu. + Nén ảnh. - Nguyên lý phân cấp bộ nhớ. VD: Từ điển có 1 000 000 từ.  3 000 từ thông dụng sẽ được đặt ở bộ nhớ trong.  997 000 từ còn lại sẽ được đặt ở bộ nhớ ngoài. - Nguyên lý dùng công thức thay bộ nhớ. Bài 6. Tìm giải pháp tối ưu cho chương trình đếm số ký tự theo loại: loại ký số, loại ký tự hoa, loại ký tự thường và các ký tự loại khác. - Dùng mảng mọt chiều. - Xem mọt ký tự nhu là mọt chỉ số trong mảng mà giá trị của thành phần sẽ xác định kiểu của ký tự. - Mỗi ký tự là mọt số nguyên có trị trong khoảng từ [0 đến 255] - Tạo mảng mọt chiều TypeTable[0..255] nhu sau: TypeTable[‘a’]=. . . TypeTable[‘z’]=’thuong’
 TypeTable[‘A’]=. . . TypeTable[‘Z’]=’hoa’
 TypeTable[‘0’]=. . . TypeTable[‘9’]=’so’
 Các truờng hợp khác của chỉ số sẽ có trị là “khác”
 Phân tích lợi điểm:
 • Xử lý chuỗi qua chỉ số mảng, tang tốc đọ. • Tốn bọ nhớ. Bài 7. Tìm giải pháp tối ưu cho chương trình đếm số bit 1 của mỗi từ (kiểu số word – 32 bit) trong danh sách các từ cho trước (số lượng từ rất lớn). Dùng mảng một chiều • Tách một từ (word - W) thành 4 bytes. • Trong mỗi byte thay vì đếm số bit 1 ( mất thời gian) ta truy cập mảng một chiều Ctable[0]:=0; { không có bit nào mang trị 1)// số bit 1 của 256 kí tự trong mã ASSCI . . . . . Ctable[255] := 8 ; { 8 bit mang trị 1) Tạo bảng Ctable dùng hàm tự viết hoặc dùng hàm count() trong bitset. Vòng lặp cho một từ : Cword = Ctable [ W and 11111111] + Lấy ra byte thứ 1 Ctable [ W rshift 8 and 11111111] + //rshift : dịch phải k bit Lấy ra byte thứ 2 Ctable [ W rshift 16 and 11111111] + Lấy ra byte thứ 3 Ctable [ W rshift 24 and 11111111] + Lấy ra byte thứ 4 Phân tích: Thay vì dùng thuật toán cổ điển cần: 1 triệu lần lặp * 32 lần dịch chuyển cho mỗi từ là 32.10 ^ 6 lần dịch chuyển Máy tính không đủ chỗ cho một mảng có 2 ^ 23 phần tử, Hơn thế việc khởi tạo mảng sẽ rất mất thời gian. Bài 8. Bằng tinh chế cách viết, tối ưu thuật toán sắp xếp mảng Bubble Sort Shin Boc Mui: public static void m_BubbleSort(int[] a,int n) { int i =0; int j =n-1; while(i<=j) { for (int x = j; x > i;x--) { if (a[x] < a[x - 1]) DoiCho(x, (x - 1)); } for (int y = i; y < j - 1; y++) { if (a[y] > a[y + 1]) { DoiCho(y, y + 1); } } i++; j--; } } Phạm My:  Ý tưởng Bubble sort:  Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i.  Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.  Cải tiến:  Thay vì ta duyệt từ cuối mảng ta duyệt 2 lược từ 2 phía :  Lượt đi: đẩy phần tử nhỏ về đầu mảng.  Lượt về: đẩy phần tử lớn về cuối mảng.  Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.  Thuật giải:  Bước 1: l=0; r=n-1; //Đoạn l->r là đoạn cần được sắp xếp k=n; //ghi nhận vị trí k xảy ra hoán vị sau cùng // để làm cơ sơ thu hẹp đoạn l->r  Bước 2: Bước 2a: j=r; //đẩy phần tử nhỏ về đầu mảng Trong khi j>l nếu a[j]<a[j-1] thì {Doicho(a[j],a[j-1]): k=j;} j--; l=k; //loại phần tử đã có thứ tự ở đầu dãy Bước 2b: j=l Trong khi j<r nếu a[j]>a[j+1] thì {Doicho(a[j],a[j+1]); k=j;} j++; r=k; //loại phần tử đã có thứ tự ở cuối dãy  Bước 3: Nếu l<r lặp lại bước 2 Ngược lại: dừng Bài 9. Tối ưu bài toán nhân hai ma trận vuông. Bài 10. Sử dụng tinh chế thuật toán tối ưu chương trình tính giá trị của đa thức: Y = an .x n + a n-1 . x n-1 + + a 1 .x + a 0 Bài 11. Sắp xếp một dãy số nguyên 20000 số phân biệt khác nhau (các số nguyên đó có trị từ 1..30000) mà bộ nhớ trong chỉ có 1200 từ (4 bytes/từ). Bộ nhớ có 1200 từ, 1 từ có 4 bytes. Vậy ta có tất cả: 1200*4=4800 (byte). Mà, 1 byte có 8 bit => có tất cả: 4800*8=38400 (bit). Để lưu được 20000 số phân biệt. Xét mảng gồm 38400 bit, để lưu 20000 số phân biệt khác nhau có giá trị từ 1 đến 30000 ta sẽ đánh số tương ứng với giá trị của nó trên mảng. VD: để lưu số 100 ta sẽ đánh số 1 vào vị trí thứ 99 của mảng (vì mảng bắt đầu từ vị trí số 0). Khi duyệt mảng, cứ đến vị trí thứ i có giá trị 1 thì tương ứng với số có giá trị i-1. Và random cho tới vị trí số 29999 và đủ 20000 số. Những số j không được lưu trữ thì vị trí tại j-1 đó có giá trị là 0. Bài 12. Hãy đặc tả ngôn ngữ được biểu thị bởi biểu thức chính qui: a) a. 0(0|1)*0 b) b. (0|1)*0(0|1)(0|1) c) c. 0*10*10*10* Biểu thức chính quy Giá trị 0(0|1)*0 L(0(0|1)*0) = L(0(0|1)*)∩L(0) = (L(0) ∩ L(0|1)*)∩L(0) = ({0} ∩ {0;1}*)∩{0} = {0}∩{0} = {0} (0|1)*0(0|1)(0|1) L((0|1)*0(0|1)(0|1)) = L((0|1)*) ∩ L(0) ∩ L(0|1) ∩ L(0|1) = L((0|1)*) ∩ L(0) ∩ (L(0) ∪ L(1)) ∩ (L(0) ∪ L(1)) = {0;1}* ∩ {0} ∩ ({0} ∪ {1}) ∩ ({0} ∪ {1}) = {0;1}* ∩ {0} ∩ {0;1} ∩ {0;1} = {0} 0*10*10*10* L(0*10*10*10*) = L(0*) ∩ L(10*) ∩ L(10*) ∩ L(10*) = {0}* ∩ {10}* ∩ {10}* ∩ {10}* = ∅ Bài 13. Giả sử ∑ = {, }. Hãy viết biểu thức chính qui cho ngôn ngữ trên ∑ chứa: a) Tất cả các chuỗi bắt đầu với ab. a+b* b) Tất cả các chuỗi trong đó có chính xác hai ký tự a. aa+b* c) Tất cả các chuỗi trong đó sau ký tự a là ký tự b. a+b Bài 14. Số thập phân chấm phẩy động gồm phần nguyên, phần thập phân và phần số mũ. Phần nguyên là chuỗi 1 hoặc nhiều ký số. Phần thập phân là phần sau dấu chấm sau đó là chuỗi 1 hoặc nhiều ký số. Phần số mũ bắt đầu với ký tự e hoặc E sau đó có thể là dấu + hoặc – và cuối cùng là chuỗi 1 hoặc nhiều ký số. Phần thập phân và phần số mũ có thể bỏ qua nhưng không bỏ cả hai. Hãy viết biểu thức chính qui đặc trưng cho số chấm động nêu trên. (1|2|...|9)*'.'((0|1|2|...|9)*|(e|E)('+'|'-')(0|1|2|...|9)*) Bài 15. Cho văn phạm sau: S → ( L ) | a L → L , S | S a) Cho biết các ký hiệu kết thúc, không kết thúc và bắt đầu “Van phạm phi ngữ cảnh bao gồm bốn thành phần:
 1. Mọt tạp hợp các token - các ký hiẹu kết thúc (terminal symbols). 
 Ví dụ: Các từ khóa, các chuỗi, dấu ngoạc đon, ... 2. Mọt tạp hợp các ký hiẹu chua kết thúc (nonterminal symbols), còn gọi là các biến (variables). 
Ví dụ: Câu lẹnh, biểu thức, ... 3. Mọt tạp hợp các luạt sinh (productions) trong đó mỗi luạt sinh bao gồm mọt ký hiẹu chua kết thúc - gọi là vế trái, mọt mũi tên và mọt chuỗi các token và / hoạc các ký hiẹu chua kết thúc gọi là vế phải. 4. Mọt trong các ký hiẹu chua kết thúc đuợc dùng làm ký hiẹu bắt đầu của van phạm. VD: list →list+digit|list-digit|digit digit → 0 | 1 | 2 ...| 9
 
Nhu vạy van phạm phi ngữ cảnh ở đây là:
 - Tạp hợp các ký hiẹu kết thúc: 0, 1, 2, ..., 9, +, - - Tạp hợp các ký hiẹu chua kết thúc: list, digit.
 - Các luạt sinh đã nêu trên.
 - Ký hiẹu chua kết thúc bắt đầu: list. ” S → ( L ) | a L → L,S | S - Ký hiệu kết thúc: “(”, “)”, “,”,a - Ký hiệu không kết thúc: S,L - Ký hiệu bắt đầu: S b) Tìm cây phân tích cho các câu sau: i. (a,a) ii. (a, (a,a)) iii. (a, (a,(a,a))) Bài 16. Dùng EBNF đặc tả: a) Định nghĩa đầu đề của class (khai báo class) trong ngôn ngữ Java class = phamvi, white space, 'class', white space, name class, '{', {assignment, ' ; ', white space, } '}'; phamvi = public, private, protected, static; identifier = alphabetic character, { alphabetic character | degit }; alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" ; digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; assignment = phamvi, white space, data type, white space, identifier { ';' | '(' , data type, white space, identifier ')',';'}; white space = ? white space characters ? ; b) Lệnh switch trong C Le Thinh: EBNF switch-statement ::= 'switch' '(' ')' '{' * * * '}' case ::= * * case-label ::= 'case' ':' ::= 'default' ':' dynamic-expression ::= static-expression ::= Cao Nguyen Ho: switch = 'switch', '(', variable , ')', '{', 'case', white space, value , ':' { assignment| 'break;'}, 'default:' { assignment| 'break;'}, '}' variable = alphabetic character, { alphabetic character | degit }; value = alphabetic character, { alphabetic character | degit }; alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" ; digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; assignment = { funtion | command }, ';' funtion = ... command = c) Định nghĩa union trong C class = 'union', white space, identifier, '{', {assignment, ' ; ', white space, } '}', name union, ';' ; identifier = alphabetic character, { alphabetic character | degit }; alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" ; digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; assignment = data type, white space, identifier {{'=' , identifier }|{ '[', digit, ']'}}, ';' ; white space = ? white space characters ? ; Bài 17. Dùng BNF đặc tả văn phạm cho biểu thức gán: A = B * C + A Le Thinh: The grammar is the following: → = → A | B | C → + | * | ( ) | The sentence: A = B * C + A Cao Nguyen Ho: → = → | + → | * → A|B|C Bài 18. Dùng BNF đặc tả cho phép toán ++ và -- trong C ::= | ::= '++'|'++'; ::= '--'|'--'; Bài 19. Chứng minh văn phạm sau nhập nhằng: + | a | b | c Bài 20. Chỉnh sửa văn phạm trong bài 9 để thêm vào phép toán -- sao cho phép toán này có độ ưu tiên cao nhất Note: có 2 bài 21, do đó bài ở trên là bài 21A, bài dưới là 21B. Bài 21. (Bài 21A). Hãy đặc tả ngôn ngữ định nghĩa bởi văn phạm sau: a | a b | b c | c Luật sinh gồm có -> -> a -> a . ->b ->b . ->c ->c. Bài 22. Viết văn phạm cho ngôn ngữ chứa chuỗi ký tự sao cho ký tự đi sau là b sẽ lập lại đúng số lần của ký tự đứng trước. Ví du ab, aaaabbbb là trong ngôn ngữ, nhưng a, abb, ba, aaabb không phải trong ngôn ngữ cách viết 1: ::= | ::= | ::= a ::= b cách viết 2: G({S,A,B,G},{a,b},P,S) các luật P: S -> AGB | G G -> AB | G A -> a B -> b Bài 23. Chứng minh rằng chương trình sau đúng: {true} if x > 0 then x := x else x := 0 – x {x ≥ 0} Bài 21. (Bài 21B). Chứng minh tính đúng của chương trình: {n > 0} while n > 0 do n := n – 1 {n = 0} Bài 24. Chứng minh tính đúng bộ phận của chương trình sau: {true} i := 1; while a[i] ≠ x do i := i + 1 { a[i] = x ( ∃j: j ≥ 1 a[j] = x i j ) } Bài 25. Thực hiện kiểm tra văn phạm hồi qui không trái (pairwise disjoint test): a) a. A → aB | b | cBB A -> aB | b | CBB first (aB) = a first (b) = b first (cBB) = c b) b. B → aB | bA | aBb B -> aB | ba | aBb first (aB) = a first (ba) = b first (aBb) = a c) c. C → aaA | b | caB C -> aaA | b | caB first (aaA) = a first (b) = b first (caB) = c Bài 26. Xác định trị từ vựng có thể hình thành các token trong các chương trình sau: a. Pascal: Function max(I, j : integer) : integer; begin if i>j then max :=i else max := j; end; b. C: int i, j; int max(i, j) { return i>j ? i:j; } Bài 27. Xây dựng NFA cho các biểu thức chính qui sau đây: a) (a|b)* b) (a* | b*)* c) (a|b)* abb (a|b)* Bài 28. Xây dựng DFA cho các biểu thức chính qui sau: a. (a|b)*a(a|b) b. (a|b)*a(a|b)(a|b) c. (a|b)*a(a|b)(a|b)(a|b)