A Complexity Measure

Thomas J. McCabe, 1976, IEEE Transactions on Software Engineering

About this paperEnglishbeside English

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

Một Phép đo Độ phức tạp

THOMAS J. McCABE

Chú thích—Bài báo này mô tả một phép đo độ phức tạp theo lý thuyết đồ thị và minh họa cách nó có thể được sử dụng để quản lý và kiểm soát độ phức tạp của chương trình. Trước tiên, bài báo giải thích cách áp dụng các khái niệm lý thuyết đồ thị và đưa ra một giải thích trực quan về các khái niệm đồ thị theo các thuật ngữ lập trình. Các đồ thị điều khiển của một số chương trình Fortran thực tế sau đó được trình bày để minh họa mối tương quan giữa độ phức tạp trực quan và độ phức tạp theo lý thuyết đồ thị. Một số tính chất của độ phức tạp theo lý thuyết đồ thị sau đó được chứng minh, cho thấy, ví dụ, rằng độ phức tạp độc lập với kích thước vật lý (việc thêm hoặc bớt các câu lệnh hàm không làm thay đổi độ phức tạp) và độ phức tạp chỉ phụ thuộc vào cấu trúc quyết định của một chương trình.

Vấn đề sử dụng luồng điều khiển không có cấu trúc cũng được thảo luận. Một đặc trưng của các đồ thị điều khiển không có cấu trúc được đưa ra và một phương pháp đo lường “tính có cấu trúc” của một chương trình được phát triển. Mối quan hệ giữa cấu trúc và khả năng rút gọn được minh họa bằng một số ví dụ.

Phần cuối cùng của bài báo này đề cập đến một phương pháp luận kiểm thử được sử dụng kết hợp với phép đo độ phức tạp; một chiến lược kiểm thử được định nghĩa, trong đó quy định rằng một chương trình có thể đạt được một mức kiểm thử tối thiểu nhất định hoặc chương trình có thể được rút gọn về mặt cấu trúc.

Thuật ngữ chỉ mục—Cơ sở, phép đo độ phức tạp, luồng điều khiển, phân rã, lý thuyết đồ thị, tính độc lập, tuyến tính, mô-đun hóa, lập trình, rút gọn, phần mềm, kiểm thử.

References

  1. C. Berge, Graphs and Hypergraphs. Amsterdam, The Netherlands: North-Holland, 1973.
  2. B. W. Boehm, "Software and its impact: A quantitative assessment," Datamation, vol. 19, pp. 48-59, May 1973.
  3. W. B. Cammack and H. J. Rogers, "Improving the programming process," IBM Tech. Rep. TR 00.2483, Oct. 1973.
  4. D. E. Knuth, "Structured programming with GOTO statements," Computing Surveys, vol. 6, pp. 261-301, Dec. 1974.
  5. R. Kosaraju, "Analysis of structured programs," J. Comput. Syst. Sci., vol. 9, pp. 232-255, Dec. 1974; also, Dep. Elec. Eng., The Johns Hopkins Univ., Baltimore, MD, Tech. Rep. 72-11, 1972.
  6. H. Legard and M. Marcotty, "A generalogy of control structures," Commun. Assoc. Comput. Mach., vol. 18, pp. 629-639, Nov. 1975.
  7. H. D. Mills, "Mathematical foundations for structured programming," Federal System Division, IBM Corp., Gaithersburg, MD, FSC 72-6012, 1972.

Read off the page by a vision model reading the page images using gpt-5. Translated into Tiếng Việt by gpt-5, against glossary version 6. Translated from the English.