LỜI NÓI ĐẦU ..............................................................................................................................................4 CHƯƠNG 1 LỊCH SỬ HÌNH THÀNH VÀ PHÁT TRIỂN CỦA LẬP TRÌNH.............................5 1.1 Kỹ thuật lập trình giai đoạn thứ nhất của máy tính điện tử...........................................................5 1.2 Cuộc khủng hoảng phần mềm những năm 60...............................................................................5 1.3 Những tư tưởng cách mạng trong lập trình...................................................................................6 1.4 Triển khai chương trình theo sắc thái công nghệ ..........................................................................8 CHƯƠNG 2 CÁC PHƯƠNG PHÁP LUẬN LẬP TRÌNH.............................................................12 2.1 Đặt vấn đề ..................................................................................................................................12 2.2 Phương pháp luận là gì ................................................................................................................14 2.3 Các phương pháp triển khai chương trình....................................................................................14 2.3.1 Triển khai chương trình từ trên xuống dưới và từ dưới lên trên...........................................14 2.3.2 Làm mịn dần (tinh chế dần từng bước).................................................................................27 2.4 Các phương pháp luận lập trình..................................................................................................35 2.4.1 Giới thiệu...............................................................................................................................35 2.4.2 Lập trình hướng thiết bị ......................................................................................................37 2.4.3 Lập trình hướng công tắc....................................................................................................39 2.4.4 Lập trình tuyến tính.............................................................................................................41 2.4.5 Lập trình có cấu trúc...........................................................................................................42 2.4.6 Lập trình hướng đối tượng...................................................................................................53 2.4.7 Lập trình hướng lát cắt ........................................................................................................58 2.4.8 Lập trình hướng cấu phần....................................................................................................66 2.4.9 Lập trình hướng dịch vụ.......................................................................................................75 2.4.10 Điện toán đám mây .............................................................................................................83 2.4.11 Lập trình hàm.....................................................................................................................89 2.4.12 Lập trình logic....................................................................................................................92 2.4.13 Lập trình Cơ sở dữ liệu.......................................................................................................96 2.4.14 Lập trình mã nguồn mở.....................................................................................................100 CHƯƠNG 3 PHONG CÁCH LẬP TRÌNH GỠ RỐI VÀ TỐI ƯU CHƯƠNG TRÌNH............105 3.1 Phong cách lập trình..................................................................................................................105 3.2 Các nguyên tắc lập trình............................................................................................................105 3.3 Các chuẩn trong lập trình..........................................................................................................112 3.4 Các lỗi có thể phát sinh trong quá trình thiết kế và cài đặt một sản phẩm phần mềm..............112 3.4.1 Ý đồ thiết kế sai.................................................................................................................113 3.4.2 Phân tích các yêu cầu không đầy đủ và lệnh lạc ..............................................................113 3.4.3 Hiểu sai về chức năng.......................................................................................................113 3.4.4 Lỗi tại các đối tượng chịu tải............................................................................................114 3.4.5 Lỗi lây lan .........................................................................................................................115 3.4.6 Lỗi cú pháp .......................................................................................................................116 3.4.7 Hiệu ứng phụ (Side Effect)................................................................................................117 3.5 Một số vấn đề trong cải tiến hiệu xuất chương trình ................................................................119 3.5.1 Tốc độ xử lý.......................................................................................................................119 3.5.2 Không gian bộ nhớ............................................................................................................128 3.6 Case Tools hỗ trợ trong cài đặt .................................................................................................130 3.7 Các ngôn ngữ lập trình thế hệ thứ 4..........................................................................................130 CHƯƠNG 4 CHỨNG MINH TÍNH ĐÚNG ĐẮN CỦA CHƯƠNG TRÌNH..............................132 4.1 Tính đúng đắn của sản phẩm.....................................................................................................132 4.2 Khái niệm chung, cách đặt vấn đề chứng minh ........................................................................133 4.3 Hệ tiền đề của Hoare.................................................................................................................135 TÀI LIỆU THAM KHẢO ........................................................................................................................143
LỊCH SỬ HÌNH THÀNH VÀ PHÁT TRIỂN CỦA LẬP TRÌNH
Kỹ thuật lập trình giai đoạn thứ nhất của máy tính điện tử
Lập trình là một công việc đòi hỏi nhiều công sức và có năng suất thấp, thường chỉ đạt khoảng 4-5 lệnh/ngày Việc thiết kế và cài đặt một sản phẩm phần mềm có thể mất từ 6 tháng với 3 nhân viên, nhưng quá trình kiểm tra và sửa lỗi có thể kéo dài thêm 3 năm Để giải quyết vấn đề này, trong ngành công nghệ thông tin, một chiến lược thương mại được áp dụng là công bố các bản sửa lỗi dưới dạng phiên bản mới thay vì chỉ đơn thuần sửa chữa sản phẩm.
Ví dụ: Ta thấy hệ điều hành DOS 4.0, chỉ tồn tại một thời gian ngắn được thay bẳng DOS 5.0, tương tự cho hệ điều hành Window
Trong những năm 50, lập trình chủ yếu được thực hiện bằng các ngôn ngữ bậc thấp, và việc theo dõi hoạt động của chương trình trực tiếp như ngày nay là không khả thi, khiến lập trình viên phải làm việc cẩn trọng hơn Trước thập niên 60, lập trình được xem như một hoạt động nghệ thuật, mang tính cá nhân cao hơn là khoa học, và những người thành thạo một ngôn ngữ lập trình cùng với một số mẹo về cấu hình phần cứng được coi là chuyên gia trong lĩnh vực này.
Cuộc khủng hoảng phần mềm những năm 60
Những năm 60 đã bùng nổ “cuộc khủng hoảng về đảm bảo phần mềm” được đặc trưng bởi hai hiện tượng sau đây:
Chi phí cho tin học ngày càng gia tăng, đặc biệt là chi phí cho phần mềm, chiếm tỷ lệ cao trong tổng chi phí công nghệ thông tin, trong khi chi phí cho phần cứng có phần ổn định Năm 1965, tổng chi phí cho tin học trên toàn cầu đạt 250 tỷ Franc Nhiều dự án lớn ứng dụng tin học đã thất bại liên tiếp, chủ yếu do vấn đề trong việc đảm bảo chất lượng sản phẩm.
Các nhà tin học lý thuyết đã nghiên cứu sâu về bản chất của ngôn ngữ lập trình, thuật toán và các hoạt động lập trình nhằm giải quyết những vướng mắc trong kỹ thuật lập trình, từ đó nâng cao nội dung này thành nguyên lý khoa học.
Các kết quả nghiên cứu điển hình như:
Dijkstra đã chỉ ra rằng động thái của chương trình có thể được đánh giá rõ ràng thông qua các cấu trúc lặp, rẽ nhánh và gọi đệ quy Ông cũng nhấn mạnh rằng tay nghề của lập trình viên tỉ lệ nghịch với số lượng toán tử goto mà họ sử dụng trong chương trình.
Bài báo đã phân tích nguyên nhân khiến việc sử dụng lệnh goto một cách bừa bãi trong lập trình tạo ra sự rối rắm trong mã nguồn, giống như một món mì sợi lộn xộn.
Gries phê phán rằng trong các trường đại học hiện nay, chương trình giảng dạy thường chú trọng vào việc dạy ngôn ngữ lập trình hơn là kỹ thuật lập trình Thay vì tập trung vào các nguyên lý và phương pháp luận lập trình, nhiều khóa học chỉ cung cấp các mẹo lập trình mà không đi sâu vào kiến thức nền tảng cần thiết.
Những tư tưởng cách mạng trong lập trình
Tính cách mạng của các quan điểm khoa học trong giai đoạn này được thể hiện qua việc chương trình máy tính và lập trình viên trở thành đối tượng nghiên cứu chính của lý thuyết lập trình Một vấn đề cốt lõi được đặt ra là làm thế nào để kiểm soát và quản lý sự phức tạp trong hoạt động lập trình.
Trí tuệ của mỗi lập trình viên có giới hạn, trong khi các vấn đề thực tiễn cần giải quyết bằng công nghệ thông tin lại rất đa dạng và phức tạp Do đó, câu hỏi đặt ra là liệu có thể chia nhỏ các bài toán lớn thành những bài toán nhỏ hơn với độ phức tạp thấp hơn để giải quyết từng phần, sau đó tổng hợp kết quả lại hay không?
Các kết quả nghiên cứu đạt được:
Năm 1969, Hoare đã đưa ra các tiên đề quan trọng để chứng minh tính đúng đắn của chương trình và phát hiện tính chất bất biến của vòng lặp Sau đó, Dijkstra và Hoare đã cùng nhau phát triển ngôn ngữ lập trình có cấu trúc.
Để thực hiện các nguyên lý lập trình, Wirth đã thiết kế và cài đặt ngôn ngữ ALGOL W, một biến thể của ALGOL 60 ALGOL W sau đó được hoàn thiện thành ngôn ngữ lập trình Pascal, nổi bật với cú pháp giản dị và trong sáng, dễ dàng minh họa các tư tưởng lập trình hiện đại, rất phù hợp cho việc giảng dạy.
+ Năm 1978, Kernighan và Ritchie đã thiết kế ra ngôn ngữ lập trình C
Cuộc cách mạng lập trình trong những năm 60 – 70 đã mang lại nhận thức rằng lập trình là một trong những lĩnh vực khó khăn nhất của toán học ứng dụng Lập trình được xem như một khoa học, nhằm đề xuất các nguyên lý và phương pháp nâng cao hiệu suất lao động cho lập trình viên, với mục tiêu chính là tăng cường năng suất làm việc.
Tính đúng đắn của chương trình
Tính dễ đọc, dễ hiểu, dễ thực hiện của chương trình
Tính dễ sửa đổi của chương trình
Tận dụng tối đa khả năng của thiết bị mà không phụ thuộc vào nó là mục tiêu của công nghệ phần mềm, nhằm tối ưu hóa sự phối hợp giữa con người và máy móc Để đảm bảo tính đúng đắn của một đối tượng, cần thiết phải kiến trúc nó một cách đơn giản và rõ ràng.
Lập trình viên cần vượt qua những giới hạn của ngữ pháp trong ngôn ngữ lập trình, đồng thời diễn đạt các chỉ thị một cách rõ ràng và chính xác Điều này quan trọng hơn việc chỉ đơn thuần biết nhiều ngôn ngữ lập trình, và đây chính là tiêu chuẩn hàng đầu mà họ cần tuân thủ.
Trong lập trình, nhiều lập trình viên mới thường bị ràng buộc bởi các ngôn ngữ lập trình cụ thể Tuy nhiên, bản chất của lập trình không phải là sử dụng một ngôn ngữ nhất định, mà là hướng tới việc phát triển giải pháp và tư duy lập trình.
Triển khai chương trình theo sắc thái công nghệ
Công nghệ sản xuất một sản phẩm phần mềm nào đó thường bao gồm các giai đoạn sau:
1 Tìm hiểu nhu cầu của khách hàng Đây là bước hình thành nên bài toán
2 Xác định các chức năng cần có của sản phẩm
3 Chia nhỏ các chức năng thành các nhóm độc lập tương đối với nhau Mỗi nhóm sẽ ứng với một bộ phần hợp thành của sản phẩm
Để sản xuất hộp bia, quy trình công nghệ được chia thành các giai đoạn chính: chuẩn bị nguyên liệu, lên men, làm hộp, ướp hương liệu, đóng hộp, đóng thùng và nhập kho.
Chú ý rằng, mỗi công đoạn bao gồm nhiều chức năng khác nhỏ hơn
+ Công đoạn a) chuẩn bị nguyên liệu có thể bao gồm:
Chuẩn bị lúa đại mạch
+ Công đoạn c) làm hộp có thể gồm:
4 Giao việc thiết kế và sản xuất mỗi bộ phận của sản phẩm này cho từng người hoặc nhóm người
5 Các nhóm triển khai công việc: Thực hiện các bước thiết kế, sản xuất, thử nghiệm
Trong quá trình hợp tác, các nhóm thường xuyên liên lạc để giảm thiểu công việc trùng lặp và đảm bảo tính tương thích khi kết nối các bộ phận.
6 Ghép nối các bộ phận/chi tiết thành phẩm
7 Thử nghiệm sản phẩm, sửa nếu cần
8 Bán và giao lô sản phẩm đầu tiên cho khách hàng
9 Thu thập thông tin phản hồi từ phía người sử dụng Quyết định sửa lại sản phẩm, cải tiến hoặc hủy bỏ việc sản xuất sản phẩm này
Quy trình sản xuất sản phẩm bao gồm nhiều giai đoạn, và nhóm phát triển phần mềm cũng thực hiện các nhiệm vụ tương tự Mỗi thành viên trong nhóm đảm nhận những nhiệm vụ chuyên biệt để đảm bảo hiệu quả trong từng giai đoạn.
- Phân tích viên + lãnh đạo nhóm: Đảm nhận các nhiệm vụ từ 1- 4 o Sản phẩm thu được sau giai đoạn 4 là phần đầu của hồ sơ phần mềm gồm:
Các đặc tả yêu cầu
Các đặc tả chức năng của phần mềm cũng như các module tương ứng
Giai đoạn 5 tập trung vào việc các nhóm triển khai công việc, trong đó nhóm trưởng tiếp tục phát triển bộ hồ sơ bằng cách bổ sung các đặc tả chi tiết và tinh chỉnh từng bước Mục tiêu là tạo ra các chương trình con được viết bằng ngôn ngữ lập trình cụ thể Đồng thời, các lập trình viên cũng tham gia tích cực vào quá trình này.
Phân tích các nhiệm vụ con
Đặc tả từng khối chức năng trong nhóm của mình, đặc tả tốt có thể giao nhiệm vụ mã hóa cho máy tính
Chuyển biểu diễn của thuật toán từ dạng đặc tả sang dạng mã nguồn (sử dụng ngôn ngữ lập trình cụ thể)
Khi mã hóa, việc tận dụng quỹ thuật toán và quỹ chương trình là rất quan trọng, đặc biệt trong bối cảnh thời gian giao nộp sản phẩm hạn hẹp Điều này đòi hỏi các thành viên trong tập thể phải có ý thức trách nhiệm cao, áp dụng nguyên tắc "mình vì mọi người, mọi người vì mình" Khi phát triển phần mềm, dù là nhỏ, bạn cần nhận thức rằng sản phẩm của mình phục vụ cho nhiều người dùng, từ đó không chỉ nâng cao chất lượng sản phẩm mà còn đóng góp vào quỹ thuật toán và quỹ chương trình, đồng thời có quyền khai thác các sản phẩm trí tuệ của người khác Thực tế cho thấy, trong lĩnh vực tin học, con người thường phung phí chất xám với năng suất thấp, chỉ khoảng 4-5 lệnh/ngày, dẫn đến việc sản xuất hàng triệu mô-đun và chương trình để thực hiện những công việc tương tự.
Trao đổi với các nhóm khác để:
Nhận được những thủ tục dùng chung
Thông hiểu lẫn nhau: o Muốn hiểu biết tốt nên:
Dùng cùng một thứ ngôn ngữ đặc tả, nhằm mô tả những yếu tố sau của chương trình:
Các kết quả cần đạt được ở mỗi điểm của chương trình
Hành động theo nguyên tắc nhất quán giúp đảm bảo tính minh bạch và dễ hiểu, đồng thời triển khai chương trình theo cấu trúc từ trên xuống dưới và tinh chỉnh dần.
Hướng dẫn cách sử dụng các chi tiết sản phẩm do nhóm mình phát triển
Trong giai đoạn 6, chuyên viên trưởng về lập trình cần tham gia trực tiếp vào các hoạt động từ 1 đến 4, theo dõi tiến độ của hoạt động 5 và bám sát các hoạt động trong giai đoạn 7 để đảm bảo tiến trình dự án diễn ra suôn sẻ.
- Nhiệm vụ 7: Do chuyên viên kiểm thử thực hiện
Nhiệm vụ 8+9 sẽ được thực hiện bởi một chuyên gia Marketing và lãnh đạo nhóm, người này cần tham gia vào các hoạt động từ 1-4 Để đảm bảo hiệu quả, các nhóm cần nhận sự tư vấn từ các chuyên gia về toán học và thuật toán, cùng với các cố vấn kỹ thuật để hỗ trợ trong việc lựa chọn thiết bị phần cứng, thuật toán và phần mềm trợ giúp.
CÁC PHƯƠNG PHÁP LUẬN LẬP TRÌNH
Đặt vấn đề
Mặc dù các nhà khoa học đã nỗ lực để xây dựng nền tảng khoa học cho lập trình, nhưng phương pháp giảng dạy lập trình vẫn chủ yếu mang tính thủ công.
- Nó thường được dạy theo ngữ cảnh của một (hoặc một vài) ngôn ngữ lập trình
- Có sự mập mờ giữa các công cụ, các khái niệm và các cách khác nhau về quan điểm lập trình/phương pháp lập trình
Dạy lập trình giống như dạy xây dựng cầu, nơi một số người chỉ tập trung vào cây cầu gỗ, trong khi những người khác lại chỉ dạy cầu sắt mà không xem xét sự kết hợp giữa hai loại vật liệu Điều này dẫn đến một chương trình học thiếu tính linh hoạt và sáng tạo, bị giới hạn bởi các công cụ và ngôn ngữ lập trình cụ thể.
Khoa học cung cấp cho chúng ta sự hiểu biết sâu sắc về các vấn đề, từ đó giúp chúng ta dự đoán và khái quát hóa Trong lĩnh vực thiết kế khoa học, điều này cho phép các nhà thiết kế sáng tạo ra những cây cầu từ nhiều loại vật liệu khác nhau, như sắt, gỗ, hoặc sự kết hợp của cả hai, dựa trên các khái niệm thiết kế đa dạng.
- và các luật (Laws) mà chúng tuân theo
Trong khoa học lập trình, việc thiết kế chương trình cần dựa trên các khái niệm cơ bản về lập trình Lập trình có thể được xem như một hoạt động kết nối giữa việc đặc tả hệ thống và thực thi chương trình theo bản đặc tả đó Do đó, lập trình bao gồm hai bước chính: đặc tả và triển khai.
- Thiết kế kiến trúc chương trình và các trừu tượng (a)
- Mã hóa bản thiết kế, sử dụng ngôn ngữ lập trình cụ thể (b)
(a) Thiết kế kiến trúc chương trình và các trừu tượng
Các hoạt động lập trình độc lập với ngôn ngữ lập trình đóng vai trò quan trọng trong việc xây dựng kiến trúc chương trình và thiết kế trừu tượng Thiết kế trừu tượng được xem là công cụ giải quyết các vấn đề thực tế, và chúng có thể được phân loại theo thứ bậc dựa trên mức độ chi tiết của chúng Sự trừu tượng càng cao thì mức độ khái quát càng lớn, và nó cũng hiện diện trong cuộc sống hàng ngày mà chúng ta thường không để ý.
Ví dụ: Một số trừu tượng như:
Trong đó: “Bút chì” được đặc tả chi tiết hơn so với “công cụ để viết”, nhưng cả 2 đều là các trừu tượng
Để tạo ra một bản thiết kế chương trình độc lập, cần xây dựng dựa trên các khái niệm lập trình chung nhằm phát triển các trừu tượng Việc kết hợp nhiều phương pháp luận lập trình trong cùng một chương trình có thể bị coi là sai lầm, nhưng thực tế, điều này hoàn toàn chấp nhận được và tự nhiên Một chương trình tốt thường sử dụng nhiều phương pháp luận lập trình khác nhau.
(b) Mã hóa bản đặc tả, sử dụng ngôn ngữ lập trình cụ thể
Kỹ thuật mã hóa là quá trình chuyển đổi bản thiết kế chương trình thành mã nguồn cụ thể bằng cách sử dụng ngôn ngữ lập trình, công cụ và các tiêu chuẩn kỹ thuật Tương tự như việc xây dựng một cây cầu từ bản thiết kế, có thể sử dụng các vật liệu khác nhau như gỗ, sắt, hoặc sự kết hợp giữa chúng để tạo ra sản phẩm cuối cùng.
Hoạt động lập trình như định nghĩa ở trên gồm hai phần cơ bản:
- Kỹ thuật: Gồm các công cụ, các kỹ thuật thực hành, và các chuẩn cho phép ta lập trình
Nền tảng khoa học của lập trình bao gồm các lý thuyết giúp hiểu rõ hoạt động của nó Khoa học không chỉ giải thích kỹ thuật một cách trực tiếp mà còn hỗ trợ chúng ta trong việc nắm bắt sâu sắc vấn đề, từ đó có khả năng vận dụng, phân tích, tổng hợp và đề xuất các cải tiến hoặc kỹ thuật mới.
Khoa học và kỹ thuật cần phải kết hợp chặt chẽ để giải quyết triệt để các vấn đề Thiếu kỹ thuật, chúng ta chỉ có thể làm việc với các cơ chế một cách đơn giản Ngược lại, nếu không có khoa học, công việc sẽ trở nên thủ công và thiếu hiểu biết sâu sắc.
Phương pháp luận là gì
Phương pháp luận là cách tiếp cận để giải quyết vấn đề, trong khi phương pháp luận lập trình đề cập đến cách thức viết chương trình từ góc độ lý thuyết Từ khía cạnh kỹ thuật, phương pháp luận lập trình còn được gọi là kỹ thuật lập trình.
Các phương pháp triển khai chương trình
2.3.1 Triển khai chương trình từ trên xuống dưới và từ dưới lên trên
Khi áp dụng nguyên lý phân mức trong bài toán theo cấp độ trừu tượng hóa, chúng ta sẽ tìm hiểu hai phương pháp tiếp cận chính: từ trên xuống và từ dưới lên.
Cách tiếp cận Top – Down, được đề xuất bởi tác giả ngôn ngữ Pascal vào thập kỷ 70, gọi là làm mịn dần Quá trình làm mịn dần, hay chính xác dần chương trình, cần được thực hiện đồng thời với việc chính xác hóa dữ liệu Phương pháp này cho phép chúng ta bắt đầu từ máy giải trừu tượng và tiến dần đến máy giải cụ thể, được trang bị bởi ngôn ngữ lập trình cụ thể.
Cách tiếp cận Bottom-up bắt đầu từ những viên gạch cơ bản để xây dựng nền móng và phát triển từng tầng cho đến khi hoàn thiện kiến trúc Phương pháp này thường được áp dụng trong giáo dục và đào tạo, cũng như trong những tình huống mà chiến lược giải quyết vấn đề chưa được nghiên cứu.
Quá trình trừu tượng hóa được chia làm nhiều mức Mỗi mức nói chung được xác định bởi 4 công cụ:
Ngôn ngữ là công cụ quan trọng để mô tả cấu trúc dữ liệu và các thao tác cần thiết Nó có thể được sử dụng ở nhiều mức độ trừu tượng khác nhau, bao gồm ngôn ngữ tự nhiên hoặc ngôn ngữ tự nhiên có cấu trúc, như phi hình thức hoặc bán hình thức.
Máy giải ở mức cao là một loại máy trừu tượng, thể hiện sự giả định Khi nâng cao mức độ, mức độ trừu tượng cũng tăng lên, theo nguyên tắc “thấy cây chưa quan trọng bằng thấy rừng”.
Quá trình trừu tượng hóa diễn ra một cách chính xác và mượt mà qua các cấp độ khác nhau, cho đến khi tạo ra chương trình hoàn chỉnh được viết bằng ngôn ngữ lập trình cụ thể, sẵn sàng để thực thi trên nền tảng tương ứng.
Triển khai chương trình Phanso.Pas minh họa nguyên lý phân mức bài toán theo cấp độ trừu tượng hóa, với mục tiêu cuối cùng là tạo ra chương trình Pascal có tên là PHANSO.PAS, chạy trên máy tính IBM XT/AT.
Chúng ta có một cặp (bộ đôi) = Trong đó P là tập các phân số, F là tập các phép toán trên phân số, F = {+, - , *, /}
+ Những bộ đôi như vậy được gọi là hệ đại số Tổng quát thì hệ đại số = là một bộ đôi, trong đó:
- P là tập các phần tử
- F là tập các phép toán trên các phần tử của P Mỗi phần tử f trong F là một ánh xạ: f: P n -> P, trong đó P n là ký hiệu biểu diễn cho tích Decartes bậc n:
P n = PP P, mỗi phần tử của P n có dạng (x1, x2, ,xn), xi P; i:1 n
F còn được gọi là phép toán n ngôi
Khái niệm phân số ở mức 0 liên quan đến việc mô tả các tập hợp P và F Để mô tả một tập, có hai phương pháp chính: một là liệt kê tất cả các phần tử trong tập, hai là chỉ ra những tính chất xác định của các phần tử thuộc tập đó.
- Với P ta có thể mô tả:
(1) Bằng ngôn ngữ tự nhiên như sau:
Tập các phân số P bao gồm các cặp tử - mẫu, trong đó tử là một số nguyên, mẫu là một số tự nhiên
(2) Bằng các ký hiệu toán học như sau:
Lưu ý: dấu , trong (1) biểu diễn quan hệ “and”
Trong ngôn ngữ lập trình F, các phép toán cộng (+), trừ (-), nhân (*) và chia (/) được định nghĩa rõ ràng Do ký hiệu / đã được sử dụng để biểu diễn phân số, phép chia hai phân số sẽ được thay thế bằng ký hiệu : để tránh nhầm lẫn Cả hai phép toán này đều thuộc loại phép toán nhị phân.
Ví dụ: Muốn cộng hai phân số, ta quy đồng mẫu số của chúng rồi cộng tử số, giữ nguyên mẫu số chung, kết quả sẽ được giản ước
Tóm lại: Ở mức 0 ta có:
- Các phép toán: được mô tả ở (2)
Mức 1
- Chi tiết hóa các phép toán trên phân số o Mô tả phép cộng 2 phân số:
+ : PP P x: P z:P y:P z = x + y qđms (x,y); tu(z) = tu(x) + tu(y); mau(z) = mau(x); rutgon(z);
Thay hình vẽ về bộ biến đổi ta có thể ghi:
Máy giải được thiết kế để thực hiện hai thao tác chính: quy đồng mẫu số cho hai phân số (qđms) và rút gọn một phân số (rutgon) Các phép toán khác cũng được áp dụng tương tự, mang lại sự tiện lợi cho người sử dụng.
- : PP P x: P z:P y:P z = x - y qđms (x,y); tu(z) = tu(x) - tu(y); mau(z) = mau(x); rutgon(z);
* : PP P x: P z:P y:P z = x * y tu(z) = tu(x) * tu(y); mau(z) = mau(x)*mau(y);
: : PP P x: P z:P y:P z = x : y Yêu cầu: tu(y) 0; mau(z)>0 tu(z) = tu(x) * mau(x); mau(z) = mau(x)*tu(y); rutgon(z);
Mức 2 qđms : PP PP x: P x: P y: P y: P qđms(x,y) d= msc(mau(x), mau(y)); tspx = d:mau(x); tspy= d:mau(y); tu(x) = tu(x)*tspx; mau(x) = d; tu(y) = tu(y)*tspy; mau(y) = d;
Trong đó: msc – mẫu số chung tsp – thừa số phụ
Rutgon(x) d= ucln(tu(x), mau(x)); tu(x) = tu(x):d;
Mức 3 msc : N 2 N msc(a,b) bcnn(a,b); ucln: N 2 N ucln(a,b) khi b>0 r=du(a,b); a=b; b=r; dừng khi b=0; c =a; Đây là thuật toán Euclide: Muốn tìm ước số chung của hai số tự nhiên a, b, ta chia nguyên a cho b để lấy số dư r Sau đó, nếu r 0 ta lại lấy b chia cho r để tìm số dư mới Đến đây, chúng ta hãy áp dụng nguyên lý nhất quán sau đây để thực hiện một vài sửa đổi:
Ta định nghĩa phân số như sau:
P = {x/y| x Z, y N} (3) Trong thao tác rút gọn ta tính: d=ucln(tu(x),mau(x)) (4)
Dữ liệu được khai báo thế nào thì phải thao tác thế ấy Cần sớm phát hiện những mâu thuẫn giữa CTDL và thao tác để khắc phục ngay
Sau đó ta mô tả hàm ucln như là một ánh xạ NN N
Khi làm việc với các phân số có tử là số âm, chẳng hạn như -3/4, biểu thức ucln(-3,5) sẽ vi phạm mô tả 5 Điều này dẫn đến mâu thuẫn giữa (3) và (5) Để giải quyết mâu thuẫn này, có thể áp dụng một trong những biện pháp sau đây.
Biện pháp 1: Sửa lại mô tả ucln để hàm này có thể làm việc với các số âm:
Ucln: ZZN Sửa đổi này dĩ nhiên sẽ kéo theo một vài sửa đổi tương ứng trong hàm ucln
Biện pháp 2: Giữ nguyên định nghĩa cũ của ucln và sửa lại thao tác rút gọn
Dưới đây ta chọn biện pháp 2: Việc sửa đổi này được phản ánh ở mức triển khai số 4 dưới đây
Sau khi điều chỉnh một số chi tiết và thêm thao tác khởi tạo cho phân số, cùng với quy trình xác định đầu vào (input) và đầu ra (output), chúng ta đã có một mô tả gần gũi với ngôn ngữ lập trình truyền thống.
Lưu ý: Chú thích được viết trong cặp dấu (* và *)
Mức 4
(* 1- Mô tả kiểu dl phân số *)
(x:P, y: P): x+y: P input: x:P, y:P output: z:P (*z=x+y*) qđms(x,y); tu(z)=tu(x)+tu(y); mẫu(z) = mẫu(x); rutgon(z);
(x:P, y: P): x-y: P input: x:P, y:P output: z:P (*z=x-y*) qđms(x,y); tu(z)=tu(x)-tu(y); mẫu(z) = mẫu(x); rutgon(z);
22 tu(z)=tu(x)tu(y); mẫu(z) = mẫu(x)mẫu(y); rutgon(z);
(x:P, y: P): x : y: P input: x:P, y:P output: z:P (* z=x : y *) điều kiện: tu(y) 0
Ngược lại tử(z)=tử(x)mẫu(y); mẫu(z) =mẫu(x)*tử(y); nếu mẫu(z)
