Thuật toán – Wikipedia tiếng Việt

a và b ở các vị trí có tên A và B. Thuật toán tiến hành bằng các phép trừ liên tiếp trong hai vòng lặp: NẾU phép thử B ≥ A cho kết quả “đúng” (chính xác hơn, số b ở vị trí B lớn hơn hoặc bằng số a ở vị trí A) thì thuật toán chỉ định B ← B – A (nghĩa là số b – a thay thế b cũ). Tương tự, IF A> B, THEN A ← A – B. Quá trình kết thúc khi (nội dung của) B bằng 0, tạo ra ưcln trong A. (Thuật toán bắt nguồn từ Scott 2009: 13; các ký hiệu và kiểu vẽ từ Tausworthe 1977).Lưu đồ thuật toán (thuật toán Euclid ) để tính ước số chung lớn nhất (ưcln) của hai sốvàở các vị trí có tên A và B. Thuật toán tiến hành bằng các phép trừ liên tiếp trong hai vòng lặp: NẾU phép thử B ≥ A cho kết quả “đúng” (chính xác hơn,ở vị trí B lớn hơn hoặc bằngở vị trí A) thì thuật toán chỉ định B ← B – A (nghĩa là sốthay thếcũ). Tương tự, IF A> B, THEN A ← A – B. Quá trình kết thúc khi (nội dung của) B bằng 0, tạo ra ưcln trong A. (Thuật toán bắt nguồn từ Scott 2009: 13; các ký hiệu và kiểu vẽ từ Tausworthe 1977).

Trong toán học và khoa học máy tính, một thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.[1][2] Các thuật toán luôn rõ ràng và được sử dụng chỉ rõ việc thực hiện các phép tính, xử lý dữ liệu, suy luận tự động và các tác vụ khác.

Là một giải pháp hiệu suất cao, một thuật toán hoàn toàn có thể được trình diễn trong một khoảng chừng khoảng trống và thời hạn hữu hạn, [ 3 ] và bằng một ngôn từ hình thức được xác lập rõ ràng [ 4 ] để đo lường và thống kê một hàm số. [ 5 ] Bắt đầu từ trạng thái khởi đầu và nguồn vào bắt đầu ( hoàn toàn có thể trống ), [ 6 ] những hướng dẫn diễn đạt một phép tính, khi được thực thi, sẽ thực thi qua một số ít [ 7 ] hữu hạn những trạng thái sau đó được xác lập rõ, ở đầu cuối tạo ra ” đầu ra ” [ 8 ] và chấm hết ở trạng thái kết thúc sau cuối. Sự quy đổi từ trạng thái này sang trạng thái tiếp theo không nhất thiết phải mang tính xác lập ; 1 số ít thuật toán, được gọi là thuật toán ngẫu nhiên, phối hợp nguồn vào ngẫu nhiên. [ 9 ]Khái niệm thuật toán đã sống sót từ thời cổ đại. Các thuật toán số học, ví dụ điển hình như thuật toán chia, được sử dụng bởi những nhà toán học Babylon cổ đại vào khoảng chừng 2500 TCN và những nhà toán học Ai Cập vào khoảng chừng 1550 TCN. [ 10 ] Các nhà toán học Hy Lạp sau đó đã sử dụng những thuật toán trong sàng Eratosthenes để tìm số nguyên tố, [ 11 ] và thuật toán Euclide để tìm ước chung lớn nhất của hai số. [ 12 ] Các nhà toán học Ả Rập như al-Kindi vào thế kỷ thứ 9 đã sử dụng những thuật toán mật mã để phá mã, dựa trên nghiên cứu và phân tích tần số. [ 13 ]

Bản thân từ thuật toán (algorithm) từ bắt nguồn từ nhà toán học thế kỷ thứ 9 Muḥammad ibn Mūsā al-Khwārizmī, tên ông được Latinh hóa thành Algoritmi.[14] Việc chính thức hóa một phần những gì sẽ trở thành khái niệm thuật toán hiện đại bắt đầu với nỗ lực giải Entscheidungsproblem (vấn đề quyết định) do David Hilbert đặt ra vào năm 1928. Các công thức hóa sau này được đóng khung như những nỗ lực để xác định ” khả năng tính toán hiệu quả ” [15] hoặc “phương pháp hiệu quả”.[16] Những công thức hóa đó bao gồm các hàm đệ quy Gödel – Herbrand – Kleene của các năm 1930, 1934 và 1935, phép tính lambda của Alonzo Church năm 1936, Công thức 1 của Emil Post năm 1936 và các máy Turing của Alan Turing năm 1936–37 và 1939.

Định nghĩa không chính thức[sửa|sửa mã nguồn]

Một định nghĩa không chính thức hoàn toàn có thể là ” một tập hợp những quy tắc xác lập đúng mực một chuỗi hoạt động giải trí “, [ 17 ] mà sẽ gồm có tổng thể những chương trình máy tính ( gồm có cả những chương trình không thực thi phép tính số ) và ( ví dụ ) bất kể thủ tục hành chính pháp luật nào [ 18 ] hoặc công thức nấu ăn. [ 19 ]Nói chung, một chương trình chỉ là một thuật toán nếu ở đầu cuối nó dừng lại [ 20 ] – mặc dầu những vòng lặp vô hạn nhiều lúc hoàn toàn có thể đồng ý được .Một ví dụ nguyên mẫu của một thuật toán là thuật toán Euclid, được sử dụng để xác lập ước chung lớn nhất của hai số nguyên ; một ví dụ được diễn đạt bằng lưu đồ ở trên và là ví dụ trong phần sau .Boolos, Jeffrey và 1974, 1999 Lỗi harv : không có tiềm năng : CITEREFBoolosJeffrey1999 ( trợ giúp ) đưa ra một định nghĩa không chính thức cho thuật toán như sau :

• Không một con người nào có thể viết đủ nhanh, đủ dài, hoặc đủ nhỏ † († “nhỏ hơn và nhỏ hơn mà không có giới hạn… bạn đang cố viết trên phân tử, trên nguyên tử, trên electron”) để liệt kê tất cả các thành viên của vô số thiết lập bằng cách viết ra tên của họ, cái khác, trong một số ký hiệu. Nhưng con người có thể làm điều gì đó hữu ích không kém, trong trường hợp có nhiều tập hợp vô hạn nhất định: Họ có thể đưa ra các chỉ dẫn rõ ràng để xác định phần tử thứ n của tập hợp, cho n hữu hạn tùy ý. Những hướng dẫn như vậy phải được đưa ra khá rõ ràng, dưới hình thức mà chúng có thể được tuân theo bởi một máy tính toán hoặc bởi một con người chỉ có khả năng thực hiện các thao tác rất cơ bản trên các ký hiệu. [21]

“Tập hợp vô hạn liệt kê được” là tập hợp mà các phần tử của nó có thể được song ánh tương ứng 1-1 với các số nguyên. Vì vậy, Boolos và Jeffrey đang nói rằng một thuật toán ngụ ý hướng dẫn cho một quá trình “tạo” các số nguyên đầu ra từ một số nguyên “đầu vào” tùy ý hoặc các số nguyên, theo lý thuyết, có thể lớn tùy ý. Ví dụ: một thuật toán có thể là một phương trình đại số chẳng hạn như y = m + n (tức là hai “biến đầu vào” tùy ý m và n tạo ra đầu ra y), nhưng các nỗ lực của các tác giả khác nhau để xác định khái niệm cho thấy rằng từ đó ngụ ý nhiều hơn thế này, một cái gì đó theo thứ tự của (cho ví dụ bổ sung):

• Các hướng dẫn chính xác (bằng ngôn ngữ mà “máy tính” hiểu được) [22] để có một quy trình “tốt” [23] nhanh, hiệu quả, chỉ định các “động thái” của “máy tính” (máy hoặc con người, được trang bị bên trong thông tin và khả năng) [24] để tìm, giải mã và sau đó xử lý các số nguyên / ký hiệu đầu vào tùy ý m và n, ký hiệu + và = … và “hiệu quả” [25]

sản xuất ra, trong một thời gian “hợp lý”,[26] đầu ra-số nguyên y tại một nơi được chỉ định và với định dạng được chỉ định.

Khái niệm thuật toán cũng được sử dụng để định nghĩa khái niệm về khả năng giải mã — một khái niệm trung tâm để giải thích cách các hệ thống hình thức ra đời bắt đầu từ một tập hợp nhỏ các tiên đề và quy tắc. Về mặt logic, thời gian mà một thuật toán yêu cầu để hoàn thành không thể đo được, vì nó dường như không liên quan đến kích thước vật lý thông thường. Từ sự không chắc chắn như vậy, đặc trưng cho công việc đang diễn ra, dẫn đến việc không có định nghĩa thuật toán phù hợp với cả cách sử dụng thuật ngữ này một cách cụ thể (theo một nghĩa nào đó)

Hình thức hóa[sửa|sửa mã nguồn]

Các thuật toán rất thiết yếu cho cách máy tính giải quyết và xử lý tài liệu. Nhiều chương trình máy tính chứa những thuật toán trình diễn chi tiết cụ thể những hướng dẫn đơn cử mà máy tính phải triển khai — theo một thứ tự đơn cử — để triển khai một trách nhiệm đơn cử, ví dụ điển hình như tính tiền lương của nhân viên cấp dưới hoặc in phiếu điểm của học viên. Vì vậy, một thuật toán hoàn toàn có thể được coi là bất kể chuỗi hoạt động giải trí nào hoàn toàn có thể được mô phỏng bởi một mạng lưới hệ thống hoàn hảo Turing. Các tác giả chứng minh và khẳng định vấn đề này gồm có Minsky ( 1967 ), Savage ( 1987 ) và Gurevich ( 2000 ) :

• Minsky: “Nhưng chúng tôi cũng sẽ duy trì, với Turing… rằng bất kỳ thủ tục nào có thể” tự nhiên “được gọi là hiệu quả, trên thực tế, có thể được thực hiện bởi một chiếc máy (đơn giản). Mặc dù điều này có vẻ cực đoan, nhưng những lập luận… ủng hộ nó thì khó có thể bác bỏ ”.[27]
• Gurevich: “… Lập luận không chính thức của Turing ủng hộ luận điểm của ông ấy biện minh cho luận điểm mạnh mẽ hơn: mọi thuật toán đều có thể được mô phỏng bởi máy Turing… theo Savage [1987], thuật toán là một quá trình tính toán được xác định bởi máy Turing”.[28]

Máy Turing hoàn toàn có thể xác lập những quá trình thống kê giám sát không kết thúc. Các định nghĩa không chính thức của thuật toán thường nhu yếu thuật toán luôn kết thúc. Yêu cầu này làm cho trách nhiệm quyết định hành động xem một thủ tục chính thức có phải là một thuật toán không trong trường hợp chung – do một định lý chính của triết lý đo lường và thống kê được gọi là bài toán dừng .Thông thường, khi một thuật toán được link với giải quyết và xử lý thông tin, tài liệu hoàn toàn có thể được đọc từ nguồn nguồn vào, được ghi vào thiết bị đầu ra và được tàng trữ để giải quyết và xử lý thêm. Dữ liệu được tàng trữ được coi là một phần của trạng thái bên trong của thực thể thực thi thuật toán. Trong trong thực tiễn, trạng thái được tàng trữ trong một hoặc nhiều cấu trúc tài liệu .Đối với 1 số ít quy trình đo lường và thống kê này, thuật toán phải được xác lập ngặt nghèo : được chỉ định theo cách nó vận dụng trong mọi trường hợp hoàn toàn có thể phát sinh. Điều này có nghĩa là mọi bước có điều kiện kèm theo phải được giải quyết và xử lý một cách có mạng lưới hệ thống, theo từng trường hợp đơn cử ; những tiêu chuẩn cho từng trường hợp phải rõ ràng ( và hoàn toàn có thể đo lường và thống kê được ) .

Bởi vì một thuật toán là một danh sách chính xác của các bước chính xác, thứ tự tính toán luôn quan trọng đối với hoạt động của thuật toán. Các hướng dẫn thường được giả định là được liệt kê rõ ràng và được mô tả là bắt đầu “từ trên cùng” và đi “xuống dưới cùng” —một ý tưởng được mô tả chính thức hơn bằng luồng kiểm soát.

Cho đến nay, cuộc luận bàn về việc chính thức hóa một thuật toán đã giả định những tiền đề của lập trình mệnh lệnh. Đây là ý niệm phổ cập nhất – một ý niệm nỗ lực miêu tả một trách nhiệm bằng những phương tiện đi lại ” máy móc “, rời rạc. Duy nhất cho ý niệm về những thuật toán chính thức hóa này là phép toán gán, đặt giá trị của một biến. Nó bắt nguồn từ trực giác của ” bộ nhớ ” như một bàn di chuột. Dưới đây là một ví dụ về sự phân công như vậy .Đối với một số ít ý niệm sửa chữa thay thế về những gì tạo thành một thuật toán, hãy xem lập trình hàm và lập trình logic .

Diễn đạt thuật toán[sửa|sửa mã nguồn]

Các thuật toán hoàn toàn có thể được bộc lộ bằng nhiều loại ký hiệu, gồm có ngôn từ tự nhiên, mã giả, lưu đồ, biểu đồ drakon, ngôn từ lập trình hoặc bảng điều khiển và tinh chỉnh ( được giải quyết và xử lý bởi trình thông dịch ). Các biểu thức ngôn từ tự nhiên của những thuật toán có khuynh hướng dài dòng và mơ hồ, và hiếm khi được sử dụng cho những thuật toán phức tạp hoặc kỹ thuật. Mã giả, lưu đồ, biểu đồ drakon và bảng điều khiển và tinh chỉnh là những cách có cấu trúc để bộc lộ những thuật toán tránh nhiều sự mơ hồ thường gặp trong những câu lệnh dựa trên ngôn từ tự nhiên. Các ngôn từ lập trình đa phần nhằm mục đích mục tiêu biểu lộ những thuật toán dưới dạng hoàn toàn có thể được thực thi bởi máy tính, nhưng cũng thường được sử dụng như một cách để định nghĩa hoặc tài liệu hóa những thuật toán .Có thể có nhiều cách trình diễn khác nhau và người ta hoàn toàn có thể biểu lộ một chương trình máy Turing nhất định dưới dạng một chuỗi những bảng máy ( xem máy trạng thái hữu hạn, bảng quy đổi trạng thái và bảng tinh chỉnh và điều khiển để biết thêm ), dưới dạng lưu đồ và biểu đồ drakon ( xem biểu đồ trạng thái để biết thêm ), hoặc như một dạng mã máy thô sơ hoặc mã lắp ráp được gọi là ” bộ tứ ” ( xem máy Turing để biết thêm ) .Các đại diện thay mặt của thuật toán hoàn toàn có thể được phân loại thành ba Lever được gật đầu của diễn đạt máy Turing, như sau : [ 29 ]

1. Mô tả cấp cao

“… Văn xuôi để mô tả một thuật toán, bỏ qua các chi tiết triển khai. Ở cấp độ này, chúng tôi không cần phải đề cập đến cách máy quản lý băng hoặc đầu từ của nó.”

2. Mô tả triển khai

“… Văn xuôi được sử dụng để xác định cách máy Turing sử dụng đầu vào của nó và cách nó lưu trữ dữ liệu trên băng của nó. Ở cấp độ này, chúng tôi không đưa ra thông tin chi tiết về các trạng thái hoặc chức năng chuyển tiếp. “

3. Mô tả chính thức

Chi tiết nhất, “mức thấp nhất”, đưa ra “bảng trạng thái” của máy Turing.

Thiết kế thuật toán đề cập đến một chiêu thức hoặc một quy trình tiến độ toán học để xử lý yếu tố và những thuật toán kỹ thuật. Việc phong cách thiết kế những thuật toán là một phần của nhiều kim chỉ nan giải pháp nghiên cứu và điều tra hoạt động giải trí, ví dụ điển hình như lập trình động và chia để trị. Các kỹ thuật phong cách thiết kế và tiến hành những phong cách thiết kế thuật toán còn được gọi là những mẫu phong cách thiết kế thuật toán, [ 30 ] với những ví dụ gồm có mẫu chiêu thức mẫu và mẫu trang trí .Một trong những góc nhìn quan trọng nhất của phong cách thiết kế thuật toán nằm ở việc tạo ra thuật toán có thời hạn chạy hiệu quả, còn được gọi là Big O của nó .Các bước nổi bật trong quy trình tăng trưởng thuật toán :

1. Định nghĩa vấn đề
2. Phát triển một mô hình
3. Đặc điểm kỹ thuật của thuật toán
4. Thiết kế một thuật toán
5. Kiểm tra tính đúng đắn của thuật toán
6. Phân tích thuật toán
7. Thực hiện thuật toán
8. Chương trình thử nghiệm
9. Viết tài liệu

Thuật toán NAND logic được tiến hành điện tử trong chip 7400Hầu hết những thuật toán được phong cách thiết kế để triển khai như những chương trình máy tính. Tuy nhiên, những thuật toán cũng được thực thi bằng những phương tiện đi lại khác, ví dụ điển hình như trong mạng nơ-ron sinh học ( ví dụ, não người thực thi phép tính số học hoặc côn trùng nhỏ đang tìm kiếm thức ăn ), trong mạch điện hoặc trong một thiết bị cơ khí .

Thuật toán máy tính[sửa|sửa mã nguồn]

{{{1}}}) (hình thoi), GOTO không điều kiện (hình chữ nhật), các toán tử gán khác nhau (hình chữ nhật) và HALT (hình chữ nhật). Việc lồng các cấu trúc này vào bên trong các khối gán dẫn đến các sơ đồ phức tạp (xem Tausworthe 1977: 100, 114).Các ví dụ về lưu đồ về cấu trúc Böhm-Jacopini chính tắc : SEQUENCE ( hình chữ nhật xuống trang ), WHILE-DO và IF-THEN-ELSE. Ba cấu trúc được tạo bởi GOTO có điều kiện kèm theo nguyên thủy ( ) ( hình thoi ), GOTO không điều kiện kèm theo ( hình chữ nhật ), những toán tử gán khác nhau ( hình chữ nhật ) và HALT ( hình chữ nhật ). Việc lồng những cấu trúc này vào bên trong những khối gán dẫn đến những sơ đồ phức tạp ( xem Tausworthe 1977 : 100, 114 ) .

Trong các hệ thống máy tính, thuật toán về cơ bản là một ví dụ của logic được viết trong phần mềm bởi các nhà phát triển phần mềm, để có hiệu quả đối với (các) máy tính “đích” nhằm tạo ra đầu ra từ đầu vào (có thể là rỗng) nhất định. Một thuật toán tối ưu, thậm chí chạy trong phần cứng cũ, sẽ tạo ra kết quả nhanh hơn thuật toán không tối ưu (độ phức tạp thời gian cao hơn) cho cùng mục đích, chạy trong phần cứng hiệu quả hơn; đó là lý do tại sao các thuật toán, như phần cứng máy tính, được coi là công nghệ.

Chương trình “thanh lịch” (nhỏ gọn), chương trình “tốt” (nhanh): Khái niệm “đơn giản và thanh lịch” xuất hiện không chính thức ở Knuth và chính xác là ở Chaitin:

• Knuth: “… chúng tôi muốn có các thuật toán tốt theo một khía cạnh thẩm mỹ được xác định lỏng lẻo. Một tiêu chí… là khoảng thời gian thực hiện thuật toán…. Các tiêu chí khác là khả năng thích ứng của thuật toán với máy tính, tính đơn giản và sang trọng của nó, v.v. ” [31]
• Chaitin: “… một chương trình là ‘thanh lịch’, theo ý tôi thì đó là chương trình nhỏ nhất có thể để tạo ra kết quả đầu ra mà nó thực hiện” [32]

Chaitin mở màn cho định nghĩa của mình bằng : ” Tôi sẽ cho bạn thấy rằng bạn không hề chứng tỏ rằng một chương trình là ‘ lịch sự ‘ ” — ví dụ điển hình như một dẫn chứng sẽ xử lý được bài toán tạm dừng ( ibid ) .

Thuật toán so với hàm có thể tính toán bằng một thuật toán: Đối với một hàm đã cho, nhiều thuật toán có thể tồn tại. Điều này đúng, ngay cả khi không mở rộng tập lệnh có sẵn cho lập trình viên. Rogers nhận xét rằng “Điều quan trọng là phải phân biệt giữa khái niệm thuật toán, tức là thủ tục và khái niệm hàm có thể tính toán bằng thuật toán, tức là ánh xạ được tạo ra bởi thủ tục. Cùng một chức năng có thể có một số thuật toán khác nhau “.[33]

Thật không may, hoàn toàn có thể có sự cân đối giữa tính tốt ( vận tốc ) và tính lịch sự ( tính nhỏ gọn ) — một chương trình thanh lịch hoàn toàn có thể cần nhiều bước để triển khai xong một phép tính hơn một chương trình kém lịch sự hơn. Ví dụ sử dụng thuật toán Euclid Open bên dưới .

Máy tính, các mô hình tính toán: Máy tính (hay “máy tính” của con người [34]) là một loại máy bị hạn chế, một “thiết bị cơ khí xác định rời rạc” [35] làm theo hướng dẫn của nó một cách mù quáng.[36] Các mô hình sơ khai của Melzak và Lambek [37] giảm khái niệm này thành bốn yếu tố: (i) các vị trí rời rạc, dễ phân biệt, (ii) các bộ đếm rời rạc, không thể phân biệt được [38] (iii) một tác nhân, và (iv) một danh sách các hướng dẫn có hiệu quả so với khả năng của tác nhân.[39]

Minsky mô tả một biến thể phù hợp hơn của mô hình “bàn tính” của Lambek trong “Các cơ sở rất đơn giản để tính toán ” của ông.[40] Máy của Minsky tiến hành tuần tự thông qua năm (hoặc sáu, tùy thuộc vào cách đếm) lệnh, trừ khi IF – THEN GOTO có điều kiện hoặc GOTO không điều kiện thay đổi luồng chương trình không theo trình tự. Bên cạnh HALT, máy của Minsky bao gồm ba hoạt động gán (thay thế, thay thế) [41]: ZERO (ví dụ: nội dung của vị trí được thay thế bằng 0: L ← 0), SUCCESSOR (ví dụ: L ← L + 1) và DECREMENT (ví dụ: L ← L – 1).[42] Hiếm khi một lập trình viên phải viết “mã” với một tập lệnh giới hạn như vậy. Nhưng Minsky cho thấy (Melzak và Lambek cũng vậy) rằng cỗ máy của anh ấy là Turing hoàn chỉnh với chỉ bốn loại lệnh chung: GOTO có điều kiện, GOTO vô điều kiện, gán / thay thế / thay thế và HALT. Tuy nhiên, một số hướng dẫn gán khác nhau (ví dụ: DECREMENT, INCREMENT và ZERO / CLEAR / EMPTY cho máy Minsky) cũng được yêu cầu đối với tính năng Turing-completeness; đặc điểm kỹ thuật chính xác của chúng phần nào tùy thuộc vào nhà thiết kế. GOTO vô điều kiện là một sự tiện lợi; nó có thể được xây dựng bằng cách khởi tạo một vị trí chuyên dụng bằng 0, ví dụ như lệnh “Z ← 0”; sau đó lệnh IF Z = 0 THEN GOTO xxx là vô điều kiện.

Mô phỏng thuật toán: ngôn ngữ máy tính (computor): Knuth khuyên người đọc rằng “cách tốt nhất để học một thuật toán là thử nó.. Lấy ngay giấy bút và làm việc với một ví dụ”.[43] Nhưng những gì về một mô phỏng hoặc thực hiện các điều thực tế? Lập trình viên phải dịch thuật toán sang ngôn ngữ mà trình mô phỏng / máy tính / trình biên dịch có thể thực thi một cách hiệu quả. Stone đưa ra một ví dụ về điều này: khi tính toán căn bậc hai, người tính toán phải biết cách lấy căn bậc hai. Nếu không, thì thuật toán, để có hiệu quả, phải cung cấp một bộ quy tắc để trích xuất căn bậc hai.[44]

Điều này có nghĩa là lập trình viên phải biết một “ngôn ngữ” có hiệu quả so với tác nhân tính toán mục tiêu (máy tính). Nhưng mô hình nào nên được sử dụng cho mô phỏng? Van Emde Boas nhận xét “ngay cả khi chúng ta đặt lý thuyết phức tạp dựa trên lý thuyết trừu tượng thay vì máy móc cụ thể, sự tùy tiện trong việc lựa chọn mô hình vẫn còn. Chính tại thời điểm này, khái niệm mô phỏng đi vào “.[45] Khi tốc độ đang được đo, tập lệnh quan trọng. Ví dụ, chương trình con trong thuật toán Euclid để tính phần còn lại sẽ thực thi nhanh hơn nhiều nếu lập trình viên có sẵn lệnh ” modulus ” thay vì chỉ phép trừ (hoặc tệ hơn: chỉ “giảm dần” của Minsky).

Lập trình có cấu trúc, cấu trúc chuẩn: Theo luận điểm của Church – Turing, bất kỳ thuật toán nào cũng có thể được tính toán bằng một mô hình được gọi là Turing hoàn chỉnh và theo các minh chứng của Minsky, tính đầy đủ của Turing chỉ yêu cầu bốn loại lệnh — GOTO có điều kiện, GOTO không điều kiện, phép gán, HALT. Kemeny và Kurtz nhận thấy rằng, trong khi việc sử dụng “vô kỷ luật” GOTO vô điều kiện và IF-THEN GOTO có điều kiện có thể dẫn đến ” mã spaghetti “, một lập trình viên có thể viết các chương trình có cấu trúc chỉ bằng các hướng dẫn này; mặt khác “cũng có thể, và không quá khó, để viết các chương trình có cấu trúc tồi bằng một ngôn ngữ có cấu trúc”.[46] Tausworthe tăng cường ba cấu trúc kinh điển Böhm-Jacopini:[47] SEQUENCE, IF-THEN-ELSE và WHILE-DO, với hai cấu trúc khác: DO-WHILE và CASE.[48] Một lợi ích bổ sung của chương trình có cấu trúc là nó tự cho mình các bằng chứng về tính đúng đắn bằng cách sử dụng quy nạp toán học.[49]

Các ký hiệu lưu đồ hợp quy: Phụ tá đồ họa được gọi là lưu đồ, đưa ra cách mô tả và ghi lại một thuật toán (và một chương trình máy tính của một thuật toán). Giống như quy trình chương trình của máy Minsky, lưu đồ luôn bắt đầu ở đầu trang và tiếp tục xuống. Các ký hiệu chính của nó chỉ có bốn: mũi tên có hướng hiển thị luồng chương trình, hình chữ nhật (SEQUENCE, GOTO), hình thoi (IF-THEN-ELSE) và dấu chấm (OR-tie). Các cấu trúc kinh điển Böhm – Jacopini được tạo ra từ những hình dạng nguyên thủy này. Cấu trúc con có thể “lồng” trong hình chữ nhật, nhưng chỉ khi một lối ra duy nhất xảy ra từ cấu trúc thượng tầng. Các ký hiệu và cách sử dụng chúng để xây dựng các cấu trúc chính tắc được thể hiện trong sơ đồ.

Ví dụ thuật toán[sửa|sửa mã nguồn]

Một trong những thuật toán đơn thuần nhất là tìm số lớn nhất trong list những số có thứ tự ngẫu nhiên. Tìm giải thuật nhu yếu nhìn vào mọi số trong list. Từ đó dẫn đến một thuật toán đơn thuần, hoàn toàn có thể được nêu trong phần diễn đạt cấp cao bằng văn xuôi tiếng Anh, như :

Mô tả cấp cao:

1. Nếu không có số nào trong tập hợp thì không có số cao nhất.
2. Giả sử số đầu tiên trong tập hợp là số lớn nhất trong tập hợp.
3. Với mỗi số còn lại trong tập hợp: nếu số này lớn hơn số lớn nhất hiện tại thì coi số này là số lớn nhất trong tập hợp.
4. Khi không còn số nào trong tập hợp để lặp lại, hãy coi số lớn nhất hiện tại là số lớn nhất của tập hợp.

Bán mô tả chính thức: Được viết bằng văn xuôi nhưng gần với ngôn ngữ cấp cao của chương trình máy tính hơn nhiều, sau đây là cách mã hóa chính thức hơn của thuật toán bằng mã giả hoặc mã pidgin:

Input: A list of numbers L.
Output: The largest number in the list L.

 if L.size = 0 return null
 largest ← L[0]
 for each item in L, do
if item > largest, then
 largest ← item
 return largest

Thuật toán Euclid[sửa|sửa mã nguồn]

Sơ đồ ví dụ về thuật toán Euclid từ TL Heath ( 1908 ), có thêm chi tiết cụ thể. Euclid không vượt quá phép đo thứ ba và không đưa ra ví dụ số. Nic gastus đưa ra ví dụ về 49 và 21 : ” Tôi lấy số ít hơn trừ đi số lớn hơn ; 28 là còn lại ; sau đó một lần nữa tôi trừ cho điều này cùng 21 ( vì điều này là hoàn toàn có thể ) ; còn lại là 7 ; tôi trừ đi 21, 14 được left ; từ đó tôi lại trừ đi 7 ( vì điều này là hoàn toàn có thể ) ; còn lại là 7, nhưng không hề trừ 7 từ 7. ” Heath phản hồi rằng ” Cụm từ ở đầu cuối gây tò mò, nhưng ý nghĩa của nó là đủ rõ ràng, cũng như ý nghĩa của cụm từ về kết thúc ‘ tại một và cùng một số ít ‘. ” ( Heath 1908 : 300 ) .

Thuật toán của Euclid để tính ước số chung lớn nhất (ƯCLN) cho hai số xuất hiện dưới dạng Mệnh đề II trong Quyển VII (“Lý thuyết số cơ bản”) của tác phẩm Cơ sở của ông.[50] Do đó, Euclid đặt ra vấn đề: “Cho hai số không nguyên tố với nhau, hãy tìm số đo chung lớn nhất của chúng”. Ông định nghĩa “Một số [là] một vô số bao gồm các đơn vị”: một số đếm, một số nguyên dương không bao gồm số không. Để “đo” là đặt một chiều dài ngắn s liên tiếp (q lần) lên trên chiều dài l cho đến khi phần còn lại là r nhỏ hơn chiều dài ngắn s. [51] Nói cách hiện đại, phần dư r = l – q × s, q là thương số, hoặc phần dư r là “môđun”, phần nguyên còn lại sau phép chia.[52]

Để giải pháp Euclid thành công xuất sắc, độ dài khởi đầu phải thỏa mãn nhu cầu hai nhu yếu : ( i ) độ dài không được bằng 0, VÀ ( ii ) phép trừ phải “ hợp lệ ” ; tức là, một phép thử phải bảo vệ rằng số nhỏ hơn trong hai số bị trừ đi số lớn hơn ( hoặc hai số hoàn toàn có thể bằng nhau để phép trừ của chúng cho hiệu quả bằng không ) .

Chứng minh ban đầu của Euclid bổ sung thêm một yêu cầu thứ ba: hai độ dài không được nguyên tố với nhau. Euclid đã quy định điều này để ông có thể xây dựng một bằng chứng rút gọn là vô lý rằng số đo chung của hai số trên thực tế là lớn nhất.[53] Trong khi thuật toán của Nicomachus cũng giống như thuật toán của Euclid, khi các số nguyên tố với nhau, nó mang lại số “1” cho số đo chung của chúng. Vì vậy, chính xác mà nói, sau đây thực sự là thuật toán của Nicomachus.

1599 = 650 × 2 + 299 650 = 299×2 + 52
 299 = 52×5 + 39
 52 = 39×1 + 13
39 = 13 × 3 + 0

Biểu thức đồ họa của thuật toán Euclid để tìm ước số chung lớn nhất cho 1599 và 650 .

Ngôn ngữ máy tính cho thuật toán Euclid[sửa|sửa mã nguồn]

Chỉ một số loại lệnh được yêu cầu để thực thi thuật toán Euclid — một số phép thử logic (GOTO có điều kiện), GOTO không điều kiện, phép gán (thay thế) và phép trừ.

• Vị trí được ký hiệu bằng (các) chữ cái viết hoa, ví dụ: S, A, v.v.
• Số lượng (số) khác nhau ở một vị trí được viết bằng (các) chữ cái thường và (thường) được kết hợp với tên của vị trí. Ví dụ, vị trí L ở đầu có thể chứa số l = 3009.

Một chương trình đơn thuần cho thuật toán Euclid[sửa|sửa mã nguồn]

” Inelegant ” là bản dịch của phiên bản thuật toán của Knuth với vòng lặp phần dư dựa trên phép trừ thay thế sửa chữa việc sử dụng phép chia ( hoặc lệnh ” modulus ” ). Bắt nguồn từ Knuth 1973 : 2 – 4. Tùy thuộc vào hai số ” Không tương thích ” hoàn toàn có thể thống kê giám sát gcd trong ít bước hơn ” Thanh lịch ” .

Thuật toán sau đây được đóng khung như là phiên bản bốn bước của Knuth của Euclid’s và Nicomachus, nhưng thay vì sử dụng phép chia để tìm phần dư, nó sử dụng các phép trừ liên tiếp của độ dài s từ độ dài còn lại r cho đến khi r nhỏ hơn s. Mô tả cấp cao, được in đậm, được phỏng theo Knuth 1973: 2–4:

ĐẦU VÀO:

1 [Into two locations L and S put the numbers l and s that represent the two lengths]: INPUT L, S

2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]: R ← L

E0: [Đảm bảo r ≥ s. ]

3 [ Ensure the smaller of the two numbers is in S and the larger in R ] : IF R > S THEN the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6 : GOTO step 6 ELSE swap the contents of R and S .4 L ← R ( this first step is redundant, but is useful for later discussion ) .5 R ← S6 S ← L

E1: [Tìm phần dư]: Cho đến khi độ dài còn lại r trong R nhỏ hơn độ dài ngắn hơn s trong S, lặp đi lặp lại phép trừ số đo s trong S với độ dài còn lại r trong R.

7 IF S > R THEN done measuring so GOTO 10 ELSE measure again ,8 R ← R − S9 [ Remainder-loop ] : GOTO 7 .

E2: [Phần dư có bằng 0? ]: HOẶC (i) số đo cuối cùng là chính xác, phần còn lại trong R bằng 0 và chương trình có thể tạm dừng, HOẶC (ii) thuật toán phải tiếp tục: số đo cuối cùng để lại phần dư trong R nhỏ hơn số đo trong S.

10 IF R = 0 THEN done so GOTO step 15 ELSE CONTINUE TO step 11 ,

E3: [Đảo vị trí s và r ]: Điểm mấu chốt của thuật toán Euclid. Sử dụng phần dư r để đo số trước đó nhỏ hơn s; L phục vụ như một kho lưu trữ tạm thời.

11 L ← R12 R ← S13 S ← L14 [ Repeat the measuring process ] : GOTO 7

ĐẦU RA:

15 [ Done. S contains the greatest common divisor ] : PRINT S

XONG:

16 HALT, END, STOP .

Một chương trình đơn thuần cho thuật toán Euclid[sửa|sửa mã nguồn]

Phiên bản sau của thuật toán Euclid chỉ nhu yếu sáu lệnh cốt lõi để thực thi mười ba lệnh được nhu yếu bởi ” chương trình chưa lịch sự ” ; tệ hơn nữa là ” chương trình chưa lịch sự ” nhu yếu nhiều loại hướng dẫn hơn. [ làm rõ ] Bạn hoàn toàn có thể tìm thấy sơ đồ của ” Thanh lịch ” ở đầu bài viết này. Trong ngôn từ BASIC ( không có cấu trúc ), những bước được đánh số, và lệnh LET [ ] = [ ] là lệnh gán được ký hiệu bằng ← .

 5 REM Euclid's algorithm for greatest common divisor
 6 PRINT " Type two integers greater than 0 "
 10 INPUT A,B
 20 IF B=0 THEN GOTO 80
 30 IF 
A
Xem thêm: PC-COVID – Wikipedia tiếng Việt 
 > B THEN GOTO 60
 40 LET B=B-A
 50 GOTO 20
 60 LET A=A-B
 70 GOTO 20
 80 PRINT A
 90 END

Cách “chương trình thanh lịch” hoạt động: Thay cho “vòng lặp Euclid” bên ngoài, “Elegant” di chuyển qua lại giữa hai “co-vòng lặp”, một vòng lặp A> B tính A ← A – B và một vòng lặp B ≤ A tính toán B ← B – A. Điều này hoạt động bởi vì, khi cuối cùng giá trị nhỏ nhất M nhỏ hơn hoặc bằng dải con S (Chênh lệch = Minuend – Subtrahend), minuend có thể trở thành s (chiều dài đo mới) và subtrahend có thể trở thành r mới (độ dài được đo); nói cách khác, “ý nghĩa” của phép trừ đảo ngược.
Phiên bản sau có thể được sử dụng với các ngôn ngữ hướng đối tượng:

/ / Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B) {
 A=Math.abs(A) ;
 B=Math.abs(B) ;
 while (B! =0) {
   if (A>B) A=A-B;
   else B=B-A;
 }
 return A;
}

Kiểm tra những thuật toán Euclid[sửa|sửa mã nguồn]

Một thuật toán có làm được những gì mà tác giả của nó muốn nó làm không ? Một số trường hợp thử nghiệm thường phân phối 1 số ít đáng tin cậy về tính năng cốt lõi. Nhưng những thử nghiệm là không đủ. Đối với những trường hợp thử nghiệm, một nguồn [ 54 ] sử dụng 3009 và 884. Knuth yêu cầu 40902, 24140. Một trường hợp mê hoặc khác là hai số nguyên tố cùng nhau 14157 và 5950 .

Nhưng “trường hợp ngoại lệ” [55] phải được xác định và thử nghiệm. Liệu “Inelegant” có thực hiện đúng khi R> S, S> R, R = S không? Cũng vậy cho chương trình “Thanh lịch”: B> A, A> B, A = B? (Có cho tất cả). Điều gì xảy ra khi một số bằng 0, cả hai số đều bằng không? (“Chưa thanh lịch” rơi vào vòng lặp vĩnh viễn trong các trường hợp trên; “Thanh lịch” rơi vào vòng lặp vĩnh viễn khi A = 0.) Điều gì xảy ra nếu người dùng nhập số âm ? Số phân số? Nếu các số đầu vào, tức là miền của hàm được tính toán bởi thuật toán / chương trình, chỉ bao gồm các số nguyên dương bao gồm cả số 0, thì các lỗi ở số 0 chỉ ra rằng thuật toán (và chương trình khởi tạo nó) là một hàm riêng phần chứ không phải một hàm tổng. Một thất bại đáng chú ý do các ngoại lệ kiểu như vậy là sự cố tên lửa Ariane 5 Flight 501 (ngày 4 tháng 6 năm 1996).

Chứng minh tính đúng đắn của chương trình bằng cách sử dụng quy nạp toán học: Knuth chứng minh việc áp dụng quy nạp toán học cho phiên bản “mở rộng” của thuật toán Euclid và ông đề xuất “một phương pháp chung áp dụng để chứng minh tính hợp lệ của bất kỳ thuật toán nào”.[56] Tausworthe đề xuất rằng thước đo độ phức tạp của một chương trình là độ dài của bằng chứng tính đúng đắn của nó.[57]

Đo lường và cải tổ những thuật toán Euclid[sửa|sửa mã nguồn]

Thanh lịch (nhỏ gọn) so với tốt (tốc độ): Chỉ với sáu lệnh cốt lõi, “Thanh lịch” là chiến thắng rõ ràng, so với “Không thanh lịch” với 13 lệnh. Tuy nhiên, “Không thanh lịch” nhanh hơn (nó đến HALT trong ít bước hơn). Phân tích thuật toán [58] chỉ ra lý do tại sao lại như vậy: “Thanh lịch” thực hiện hai phép thử điều kiện trong mỗi vòng trừ, trong khi “Không thanh lịch” chỉ thực hiện một phép thử. Vì thuật toán (thường) yêu cầu nhiều lần lặp lại, nên trung bình sẽ lãng phí nhiều thời gian để thực hiện “B = 0?” kiểm tra chỉ cần thiết sau khi phần còn lại được tính toán.

Các thuật toán có thể được cải thiện không?: Một khi lập trình viên đánh giá một chương trình “phù hợp” và “hiệu quả” – nghĩa là nó tính toán chức năng mà tác giả của nó dự định – thì câu hỏi sẽ trở thành, liệu nó có thể được cải thiện không?

Có thể cải thiện độ nhỏ gọn của “Không thanh lịch” bằng cách loại bỏ năm bước. Nhưng Chaitin đã chứng minh rằng việc nén một thuật toán không thể được tự động hóa bằng một thuật toán tổng quát;[59] đúng hơn, nó chỉ có thể được thực hiện theo kinh nghiệm; tức là, bằng cách tìm kiếm đầy đủ, thử và sai, thông minh, sáng suốt, áp dụng suy luận quy nạp, v.v. Quan sát các bước 4, 5 và 6 được lặp lại trong các bước 11, 12 và 13. So sánh với “Thanh lịch” cung cấp gợi ý rằng các bước này, cùng với các bước 2 và 3, có thể bị loại bỏ. Điều này làm giảm số lượng lệnh cốt lõi từ 13 xuống 8, làm cho nó “thanh lịch” hơn “Thanh lịch”, với chín bước.

Tốc độ của ” Thanh lịch ” hoàn toàn có thể được cải tổ bằng cách vận động và di chuyển ” B = 0 ? ” kiểm tra bên ngoài của hai vòng trừ. Thay đổi này nhu yếu bổ trợ ba lệnh ( B = 0 ?, A = 0 ?, GOTO ). Bây giờ ” Thanh lịch ” đo lường và thống kê những số ví dụ nhanh hơn ; mặc dầu điều này luôn đúng so với bất kể A, B và R, S nào cho trước hay không sẽ nhu yếu một nghiên cứu và phân tích cụ thể .

Source: https://vh2.com.vn
Category : Ứng Dụng