Chuyển tới nội dung
Home » Khái Niệm Thuật Toán | Các Tiêu Chí Đánh Giá Một Thuật Toán

Khái Niệm Thuật Toán | Các Tiêu Chí Đánh Giá Một Thuật Toán

Chủ đề F Bài 1. Khái niệm thuật toán

Ví dụ[sửa | sửa mã nguồn]

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

Một trong những thuật toán đơn giản nhất là tìm số lớn nhất trong danh sách các số có thứ tự ngẫu nhiên. Tìm lời giải yêu cầu nhìn vào mọi số trong danh sách. Từ đó dẫn đến một thuật toán đơn giản, có thể được nêu trong phần mô 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]

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]

Để phương pháp Euclid thành công, độ dài bắt đầu phải thỏa mãn hai yêu cầ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 đảm bảo rằng số nhỏ hơn trong hai số bị trừ đi số lớn hơn (hoặc hai số có thể bằng nhau để phép trừ của chúng cho kết 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

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 giản cho thuật toán Euclid[sửa | sửa mã nguồn]

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 ← S

6 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 − S

9 [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 ← R

12 R ← S

13 S ← L

14 [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 giả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ỉ yêu cầu sáu lệnh cốt lõi để thực hiện mười ba lệnh được yêu cầu bởi “chương trình chưa thanh lịch”; tệ hơn nữa là “chương trình chưa thanh lịch” yêu cầu nhiều loại hướng dẫn hơn. [làm rõ] Bạn có thể tìm thấy sơ đồ của “Thanh lịch” ở đầu bài viết này. Trong ngôn ngữ BASIC (không có cấu trúc), các 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 > 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 các 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 cung cấp một số tin cậy về chức năng cốt lõi. Nhưng các thử nghiệm là không đủ. Đối với các trường hợp thử nghiệm, một nguồn [54] sử dụng 3009 và 884. Knuth đề xuất 40902, 24140. Một trường hợp thú vị 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 thiện các 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” có thể được cải thiện bằng cách di chuyển “B = 0?” kiểm tra bên ngoài của hai vòng trừ. Thay đổi này yêu cầu bổ sung ba lệnh (B = 0 ?, A = 0 ?, GOTO). Bây giờ “Thanh lịch” tính toán các số ví dụ nhanh hơn; cho dù điều này luôn đúng đối với bất kỳ A, B và R, S nào cho trước hay không sẽ yêu cầu một phân tích chi tiết.

Tổng hợp 12 loại thuật toán cơ bản cần biết

Sau đây là tổng hợp các thuật toán cơ bản mà lập trình viên cần biết để hỗ trợ tốt hơn cho công việc của mình:

Thuật toán Hashing

Hashing là thuật toán tham gia vào quá trình phát hiện và xác định dữ liệu thích hợp thông qua key và ID. Vai trò chính của hashing chính là phát hiện lỗi, quản lý bộ nhớ cache, mật mã và tra cứu. Cụ thể, hàm hashing được tích hợp vào khóa và cho ra các giá trị chính xác nhất.

Hàm hashing còn được sử dụng như một định danh duy nhất cho những tập dữ liệu và các phép tính toán cho những người dùng để tạo ra các giá trị dữ liệu không bị trùng lặp. Thường thì hàm hashing được sử dụng trong các bộ định tuyến để lưu trữ địa chỉ IP.

Thuật toán tìm kiếm

Thuật toán tìm kiếm thường được áp dụng cho dãy cấu trúc dữ liệu tuyến tính hay cấu trúc dữ liệu về đồ họa. Đây được gọi là thuật toán tìm kiếm nhị phân nhằm giúp cho các nhà phát triển dễ dàng tìm kiếm sự hiệu quả trên những tập dữ liệu đã được sắp xếp với hàm phức tạp với thời gian của O (log N).

Cơ chế của thuật toán tìm kiếm nhị phân là chia danh sách thành hai nửa cho đến khi thấy được mục đích yêu cầu. Sau đó, dùng nó để gỡ lỗi, đặc biệt là những lỗi có sự liên quan đến git bisection.

Thuật toán sắp xếp

Các nhà phát triển sử dụng thuật toán này để có thể đặt dữ liệu theo cách có tổ chức. Các thành phần cơ bản của thuật toán QuickSort là các phần dữ liệu được dùng để so sánh với nhau nhằm xác định được thứ tự tương ứng của chúng.

Mức độ phức tạp thời gian của O (nlogn) được dùng để thực hiện vào việc so sánh. Tuy nhiên, Radix Sort có kỹ thuật xử lý nhanh hơn QuickSort. Lý do nó được sắp xếp các phần tử trong một mô hình tuyến tính với độ phức tạo thời gian O (n). Các thuật toán sắp xếp khác như: sắp xếp đếm, sắp xếp hợp nhất và sắp xếp nhóm.

Thuật toán lập trình động

thuật toán lập trình động là một hàm được dùng với mục đích giải quyết các vấn đề phức tạp có sự liên quan đến trí tuệ thông qua quá trình tách các vấn đề thành, các bài toán con nhỏ hơn. Sau khi đã giải quyết được các bài toán rồi thì thực hiện xây dựng lại thành một vấn đề phức tạp, đòi hỏi bộ nhớ của các kết quả nhỏ hơn để đưa ra câu trả lời cho các vấn đề phức tạp.

thuật toán trong lập trình thích hợp để ghi nhớ, thông qua đó cho phép lưu trữ các vấn đề đã được giải quyết trước đó. Trường hợp tiếp theo xuất hiện thì vấn đề sẽ được giải quyết nhanh hơn rất nhiều.

Thuật toán Dijkstra

Một vấn đề cực kỳ quan trọng khác mà các nhà phát triển làm việc là tìm đường dẫn. Đồ thị hóa một cách cực kỳ linh hoạt để mô tả tất cả các loại vấn đề liên quan đến mạng lưới các đối tượng riêng biệt.

thuật toán Dijkstra là một cách tìm đường đi nhanh nhất giữa hai nút trong biểu đồ. Đây chính là nền tảng của hầu hết các công việc được thực hiện trong việc tìm kiếm đường đi và được sử dụng trong mọi thứ, từ trí tuệ nhân tạo cho đến thiết kế trò chơi.

Thuật toán phân tích liên kết

thuật toán phân tích liên kết thường được ứng dụng chủ yếu trong lĩnh vực mạng. thuật toán này cung cấp khả năng tương quan trong cùng một tên miền với nhiều thực thể khác nhau.

Phân tích liên kế sử dụng trong những ma trận phức tạp và biểu diễn đồ họa nhằm liên kết các căn cứ tương tự trong cùng một miền hiện tại. Loại thuật toán cơ bản này thường được dùng trong các công cụ như: Google, Facebook, Twitter.

Thuật toán Mô-đun

Các thuật toán mã hóa phức tạp nếu được phân tích dựa trên thuật toán mô-đun sẽ trở nên đơn giản và trở nên dễ dàng hơn rất nhiều. Đối với số học mô-đun, các thông số hiện tại đang xử lý chỉ là số nguyên và các phép toán chủ yếu được dùng chính là cộng, trừ, nhân, chia.

Thuật toán phân tích cú pháp và xâu ký tự

Quy trình tạo xâu luôn đặc biệt và quan trọng đối với miền và phân tử mạng. Để giúp thuật toán xâu ký tự có thể phát huy được hết khả năng thì các xâu phải khớp trong cùng một chuỗi dài hoặc khi xác nhận chuỗi bằng cách phân tích cú pháp qua giới hạn đã được xác định từ trước. thuật toán phân tích cú pháp và xâu ký tự được dùng chủ yếu trong quá trình phát triển web cho URL.

Thuật toán biến đổi Fourier

thuật toán biến đổi Fourier thường được biết đến là một trong những thuật toán đơn giản nhưng lại rất mạnh. Loại thuật toán này được dùng để giúp chuyển đổi tín hiệu từ tên miền thời gian sang miền tần số và ngược lại.

Hiện tại, các mạng kỹ thuật số như: wifi, internet, máy tính, điện thoại, vệ tinh, bộ định vị,…đều sử dụng thuật toán biến đổi Fourier để vận hành.

Thuật toán mã hóa Huffman

thuật toán mã hóa Huffman chính là nền tảng của nén văn bản hiện đại. Nó thường hoạt động bằng cách xem xét tần suất các ký tự khác nhau, xuất hiện trong một văn bản và sắp xếp chúng trong một cây dựa trên tần suất này.

Thuật toán các tập không giao nhau

thuật toán các tập không giao nhau chính là một cấu trúc dữ liệu, nó đóng vai trò như một cấu trúc trợ giúp một thuật toán được dùng để biểu diễn nhiều tập hợp khác nhau trong mảng riêng lẻ. Và mỗi mục chính là một phần tử của nhiều tập hợp. Do đó, các bộ tách rời được đại diện cho những phần tử được kết nối với nhau trong cùng một thuật toán đồ thị hay phân đoạn của hình ảnh.

Hệ số tích phân

thuật toán hệ số tích phân chính là thuật toán cung cấp hướng dẫn từng bước về cách lấy các thừa số nguyên tố của một số tổng hợp. Hệ số tích phân sẽ giúp bạn giải quyết các vấn đề phức tạp trong nền tảng mã hóa yêu cầu, bạn cần phải giải quyết các số nguyên phức hợp lớn.

Trên đây là những chia sẻ về khái niệm thuật toán là gì, tầm quan trọng cũng như các loại thuật toán phổ biến hiện nay. Mong rằng với những chia sẻ trên đây sẽ giúp bạn đọc có thể hiểu rõ hơn về thuật toán và biết cách ứng dụng thuật toán hiệu quả cho công việc lập trình của mình. Cùng theo dõi HR Insider để xem thêm nhiều thông tin hữu ích hơn nhé!

Bài viết dành riêng cho thành viên của HR Insider.

Khái niệm ‘thuật toán’ ra đời như thế nào?

Thuật toán (algorithm), bắt nguồn từ tên nhà toán học người Ba Tư trong thế kỷ 8, là một tập hợp các bước để giải quyết một vấn đề.

Khái niệm ‘thuật toán’ ra đời như thế nào?

Video: BBC

Khái niệm ‘thuật toán’ ra đời như thế nào?

Thuật toán (algorithm), bắt nguồn từ tên nhà toán học người Ba Tư trong thế kỷ 8, là một tập hợp các bước để giải quyết một vấn đề.

Khái niệm ‘thuật toán’ ra đời như thế nào?

Video: BBC

Bài 11: Thuật toán và Phân tích thuật toán

Thuật toán và những tính chất của thuật toán

Chủ đề F Bài 1. Khái niệm thuật toán
Chủ đề F Bài 1. Khái niệm thuật toán

Tại sao cần dùng thuật toán?

Tối ưu hóa việc tìm kiếm

Thuật toán chính là những chỉ dẫn để tìm thấy kết quả cho vấn đề một cách tối ưu nhất. Các lập trình viên thường sử dụng thuật toán để tìm ra con đường ngắn nhất để giải quyết vấn đề.

Ví dụ như: Google Map, Grab, Uber là những ứng dụng thường sử dụng thuật toán để tính toán quãng đường ngắn nhất, thuận tiện nhất khi hướng dẫn và hỗ trợ khách hàng di chuyển.

Một ví dụ dễ hiểu khác chính là Google, bạn có thể tìm bất cứ thông tin gì tại nơi đây. Vì Google luôn cập nhật và nâng cấp thuật toán của mình để cung cấp thông tin cho người dùng về mọi lĩnh vực, với tốc độ trả kết quả cực kỳ nhanh, chỉ trong 1 giây có thể hiển thị lên đến hàng ngàn kết quả.

Khả năng bảo mật cao

Thuật toán đều sẽ được mã hóa thành các chuỗi ký tự. Vì thế, khi truyền tải và nhận dữ liệu đều cần phải mã hóa. Điều này thể giảm sự xâm nhập từ các hacker và thể hiện khả năng bảo mật tốt của thuật toán.

Tham khảo[sửa | sửa mã nguồn]

  1. ^ “The Definitive Glossary of Higher Mathematical Jargon — Algorithm”. Math Vault (bằng tiếng Anh). ngày 1 tháng 8 năm 2019. Bản gốc lưu trữ ngày 28 tháng 2 năm 2020. Truy cập ngày 14 tháng 11 năm 2019.
  2. ^ “Definition oALGORITHM”. Merriam-Webster Online Dictionary (bằng tiếng Anh). Bản gốc lưu trữ ngày 14 tháng 2 năm 2020. Truy cập ngày 14 tháng 11 năm 2019.
  3. ^ “Any classical mathematical algorithm, for example, can be described in a finite number of English words” (Rogers 1987:2).
  4. ^ Well defined with respect to the agent that executes the algorithm: “There is a computing agent, usually human, which can react to the instructions and carry out the computations” (Rogers 1987:2).
  5. ^ “an algorithm is a procedure for computing a function (with respect to some chosen notation for integers)… this limitation (to numerical functions) results in no loss of generality”, (Rogers 1987:1).
  6. ^ “An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins” (Knuth 1973:5).
  7. ^ “A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a ‘computational method'” (Knuth 1973:5).
  8. ^ “An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs” (Knuth 1973:5).
  9. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: “a computation is carried out in a discrete stepwise fashion, without the use of continuous methods or analogue devices… carried forward deterministically, without resort to random methods or devices, e.g., dice” (Rogers 1987:2).
  10. ^ Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip. Springer Science & Business Media. tr. 7–8. ISBN 9783642181924.
  11. ^ “Hellenistic Mathematics”. The Story of Mathematics. Bản gốc lưu trữ ngày 11 tháng 9 năm 2019. Truy cập ngày 14 tháng 11 năm 2019.
  12. ^ Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons. ISBN 978-1-118-46029-0.
  13. ^ Dooley, John F. (2013). A Brief History of Cryptology and Cryptographic Algorithms. Springer Science & Business Media. tr. 12–3. ISBN 9783319016283.
  14. ^ “Al-Khwarizmi – Islamic Mathematics”. The Story of Mathematics. Bản gốc lưu trữ ngày 25 tháng 7 năm 2019. Truy cập ngày 14 tháng 11 năm 2019.
  15. ^ Kleene 1943 in Davis 1965:274
  16. ^ Rosser 1939 in Davis 1965:225
  17. ^ Stone 1973:4
  18. ^ Simanowski, Roberto (2018). The Death Algorithm and Other Digital Dilemmas. Untimely Meditations. 14. Chase, Jefferson biên dịch. Cambridge, Massachusetts: MIT Press. tr. 147. ISBN 9780262536370. Bản gốc lưu trữ ngày 22 tháng 12 năm 2019. Truy cập ngày 27 tháng 5 năm 2019.

    […] the next level of abstraction of central bureaucracy: globally operating algorithms.

  19. ^ Dietrich, Eric (2001) [1999]. “Algorithm”. Trong Wilson, Robert Andrew; Keil, Frank C. (biên tập). The MIT Encyclopedia of the Cognitive Sciences. MIT Cognet library. Cambridge, Massachusetts: MIT Press. tr. 11. ISBN 9780262731447. Truy cập ngày 22 tháng 7 năm 2020.

    An algorithm is a recipe, method, or technique for doing something.

  20. ^ Stone simply requires that “it must terminate in a finite number of steps” (Stone 1973:7–8).
  21. ^ Boolos and Jeffrey 1974,1999:19
  22. ^ cf Stone 1972:5
  23. ^ Knuth 1973:7 states: “In practice we not only want algorithms, we want good algorithms… one criterion of goodness is the length of time taken to perform the algorithm… other criteria are the adaptability of the algorithm to computers, its simplicity, and elegance, etc.”
  24. ^ cf Stone 1973:6
  25. ^ Stone 1973:7–8 states that there must be, “…a procedure that a robot [i.e., computer] can follow in order to determine precisely how to obey the instruction”. Stone adds finiteness of the process, and definiteness (having no ambiguity in the instructions) to this definition.
  26. ^ Knuth, loc. cit
  27. ^ Minsky 1967Lỗi harv: không có mục tiêu: CITEREFMinsky1967 (trợ giúp)
  28. ^ Gurevich 2000:1, 3
  29. ^ Sipser 2006:157
  30. ^ Algorithm Design: Foundations, Analysis, and Internet Examples, ISBN 978-0-471-38365-9
  31. ^ Knuth 1973:7
  32. ^ Chaitin 2005:32
  33. ^ Rogers 1987:1–2
  34. ^ In his essay “Calculations by Man and Machine: Conceptual Analysis” Seig 2002:390 credits this distinction to Robin Gandy, cf Wilfred Seig, et al., 2002 Reflections on the foundations of mathematics: Essays in honor of Solomon Feferman, Association for Symbolic Logic, A.K. Peters Ltd, Natick, MA.
  35. ^ cf Gandy 1980:126, Robin Gandy Church’s Thesis and Principles for Mechanisms appearing on pp. 123–148 in J. Barwise et al. 1980 The Kleene Symposium, North-Holland Publishing Company.
  36. ^ A “robot”: “A computer is a robot that performs any task that can be described as a sequence of instructions.” cf Stone 1972:3
  37. ^ Lambek’s “abacus” is a “countably infinite number of locations (holes, wires etc.) together with an unlimited supply of counters (pebbles, beads, etc). The locations are distinguishable, the counters are not”. The holes have unlimited capacity, and standing by is an agent who understands and is able to carry out the list of instructions” (Lambek 1961:295). Lambek references Melzak who defines his Q-machine as “an indefinitely large number of locations… an indefinitely large supply of counters distributed among these locations, a program, and an operator whose sole purpose is to carry out the program” (Melzak 1961:283). B-B-J (loc. cit.) add the stipulation that the holes are “capable of holding any number of stones” (p. 46). Both Melzak and Lambek appear in The Canadian Mathematical Bulletin, vol. 4, no. 3, September 1961.
  38. ^ If no confusion results, the word “counters” can be dropped, and a location can be said to contain a single “number”.
  39. ^ “We say that an instruction is effective if there is a procedure that the robot can follow in order to determine precisely how to obey the instruction.” (Stone 1972:6)
  40. ^ cf Minsky 1967: Chapter 11 “Computer models” and Chapter 14 “Very Simple Bases for Computability” pp. 255–281 in particular
  41. ^ cf Knuth 1973:3.
  42. ^ But always preceded by IF–THEN to avoid improper subtraction.
  43. ^ Knuth 1973:4
  44. ^ Stone 1972:5. Methods for extracting roots are not trivial: see Methods of computing square roots.
  45. ^ Leeuwen, Jan (1990). Handbook of Theoretical Computer Science: Algorithms and complexity. Volume A. Elsevier. tr. 85. ISBN 978-0-444-88071-0.
  46. ^ John G. Kemeny và Thomas E. Kurtz 1985 Back to Basic: The History, Corruption, and Future of the Language, Addison-Wesley Publishing Company, Inc. Reading, MA, ISBN 0-201-13433-0.
  47. ^ Tausworthe 1977:101
  48. ^ Tausworthe 1977:142
  49. ^ Knuth 1973 section 1.2.1, expanded by Tausworthe 1977 at pages 100ff and Chapter 9.1
  50. ^ Heath 1908:300; Hawking’s Dover 2005 edition derives from Heath.
  51. ^ ” ‘Let CD, measuring BF, leave FA less than itself.’ This is a neat abbreviation for saying, measure along BA successive lengths equal to CD until a point F is reached such that the length FA remaining is less than CD; in other words, let BF be the largest exact multiple of CD contained in BA” (Heath 1908:297)
  52. ^ For modern treatments using division in the algorithm, see Hardy and Wright 1979:180, Knuth 1973:2 (Volume 1), plus more discussion of Euclid’s algorithm in Knuth 1969:293–297 (Volume 2).
  53. ^ Euclid covers this question in his Proposition 1.
  54. ^ “Euclid’s Elements, Book VII, Proposition 2”. Aleph0.clarku.edu. Bản gốc lưu trữ ngày 24 tháng 5 năm 2012. Truy cập ngày 20 tháng 5 năm 2012.
  55. ^ While this notion is in widespread use, it cannot be defined precisely.
  56. ^ Knuth 1973:13–18. He credits “the formulation of algorithm-proving in terms of assertions and induction” to R W. Floyd, Peter Naur, C.A.R. Hoare, H.H. Goldstine and J. von Neumann. Tausworth 1977 borrows Knuth’s Euclid example and extends Knuth’s method in section 9.1 Formal Proofs (pp. 288–298).
  57. ^ Tausworthe 1997:294
  58. ^ cf Knuth 1973:7 (Vol. I), and his more-detailed analyses on pp. 1969:294–313 (Vol II).
  59. ^ Breakdown occurs when an algorithm tries to compact itself. Success would solve the Halting problem.

Ngày đăng: 30/10/2022 | Không có phản hồi

Ngày cập nhật: 30/10/2022

Thuật toán là gì? Thuật toán quan trọng như thế nào trong lập trình? Có bao nhiêu thuật toán được sử dụng trong lập trình? Nếu bạn đang thắc mắc về những vấn đề này thì đừng bỏ qua bài viết sau đây của Glints. Theo dõi ngay để hiểu rõ hơn về thuật toán nhé.

Thuật toán là gì? Thuật toán hay còn gọi là giải thuật có khá nhiều định nghĩa khác nhau. Hiểu một cách đơn giản thuật toán là một tập hợp hữu hạn bao gồm các hướng dẫn được xác định rõ ràng, bạn có thể thực hiện được bằng máy tính, thường được dùng để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.

Nói một cách dễ hiểu hơn, mỗi bài toán được ví như một chiếc hòm đựng đầy kho báu, và chìa khóa chính là “giải thuật”.Nếu sử dụng không đúng chìa bạn vẫn có thể mở được hòm kho báu, tuy nhiên sẽ mất khá nhiều thời gian và công sức, hoặc nếu mở được hòm thì kho báu bên trong cũng bị méo mó, không được toàn vẹn.

Việc sử dụng đúng chìa khóa sẽ giúp bạn dễ dàng lấy được kho báu nhanh chóng. Dĩ nhiên, mỗi hòm sẽ luôn cần đến một loại chìa khóa khác nhau, tương tự như thuật toán luôn có những giải thuật xác định.

Sẽ không có chiếc chìa khóa nào có thể mở được tất cả các hòm kho báu, và cũng không có giải thuật nào có thể giải được toàn bộ các bài toán.

Sau đây là các thuật toán cơ bản lập trình viên cần biết để hỗ trợ tốt hơn cho công việc của mình. Cùng tìm hiểu để biết được các thuật toán đó là gì nhé.

Hashing là một trong những thuật toán tham gia vào quá trình phát hiện và xác định dữ liệu thích hợp thông qua key và ID. Vai trò chính của hashing là phát hiện lỗi, quản lý bộ nhớ cache, mật mã và tra cứu, cụ thể hàm hashing được tích hợp vào khóa và cho ra các giá trị chính xác nhất.

Hàm hashing còn được sử dụng như một định danh duy nhất cho các tập dữ liệu và các phép tính toán cho người dùng để tạo ra các giá trị dữ liệu không trùng lặp. Thường hàm hashing được sử dụng trong các bộ định tuyến để lưu trữ địa chỉ IP.

Đọc thêm: C++ Là Gì? Ứng Dụng Ngôn Ngữ Lập Trình C++ Trong Thực Tế

Thuật toán tìm kiếm được áp dụng cho dãy cấu trúc dữ liệu tuyến tính hay cấu trúc dữ liệu đồ họa. Đây còn được gọi là thuật toán tìm kiếm nhị phân, giúp cho các nhà phát triển dễ dàng tìm kiếm các hiệu quả trên những tập dữ liệu đã được sắp xếp với hàm phức tạp thời gian của O (log N).

Cơ chế của thuật toán tìm kiếm nhị phân là chia danh sách thành hai nửa cho đến khi thấy được mục đích yêu cầu, sau đó dùng nó để gỡ lỗi, đặc biệt những lỗi liên quan đến git bisection.

Các nhà phát triển sử dụng thuật toán này để đặt dữ liệu theo cách có tổ chức. Các thành phần cơ bản của thuật toán QuickSort là các phần dữ liệu được dùng để so sánh với nhau nhằm xác định thứ tự tương ứng của chúng.

Mức độ phức tạp thời gian của O (nlogn) được dùng để thực hiện vào việc so sánh. Tuy nhiên, Radix Sort có kỹ thuật xử lý nhanh hơn QuickSort, lý do vì nó sắp xếp các phần tử trong một mô hình tuyến tính với độ phức tạo thời gian O (n). Các thuật toán sắp xếp khác như: sắp xếp đếm, sắp xếp hợp nhất và sắp xếp nhóm.

Thuật toán lập trình động thường là một hàm được dùng với mục đích giải quyết các vấn đề phức tạp liên quan đến trí tuệ thông qua quá trình tách các vấn đề thành các bài toán con nhỏ hơn. Sau khi đã giải quyết các bài toán rồi thì thực hiện xây dựng trở lại thành một vấn đề phức tạp đòi hỏi bộ nhớ của các kết quả nhỏ hơn để đưa ra câu trả lời cho vấn đề phức tạp ban đầu.

Thuật toán trong lập trình có thể tích hợp để ghi nhớ, thông qua đó cho phép lưu trữ các vấn đề đã được giải quyết trước đó. Trường hợp lần tiếp theo xuất hiện thì vấn đề sẽ được giải quyết nhanh hơn rất nhiều.

Đọc thêm: ASP Net Là Gì? Từ Điển A-Z Về ASP.net Framework Trong Lập Trình

Một vấn đề cực kỳ quan trọng khác mà các nhà phát triển làm việc là tìm đường dẫn. Đồ thị hóa một cách cực kỳ linh hoạt để mô tả tất cả các loại vấn đề liên quan đến mạng lưới các đối tượng riêng biệt.

Thuật toán Dijkstra là một cách tìm đường đi nhanh nhất giữa hai nút trong biểu đồ. Đây cũng chính là nền tảng của hầu hết các công việc được thực hiện trong việc tìm kiếm đường đi và được sử dụng trong mọi thứ, từ trí tuệ nhân tạo đến thiết kế trò chơi.

Thuật toán phân tích liên kết được ứng dụng chủ yếu trong lĩnh vực mạng, thuật toán nào cung cấp khả năng tương quan trong cùng một tên miền với nhiều thực thể khác nhau.

Phân tích liên kế sử dụng ma trận phức tạp và biểu diễn đồ họa nhằm liên kết các căn cứ tương tự trong cùng một miền hiện tại. Loại thuật toán cơ bản này được dùng trong các công cụ như Google, Facebook, Twitter.

Các thuật toán mã hóa phức tạp nếu được phân tích dựa trên thuật toán mô-đun sẽ trở nên đơn giản và dễ dàng hơn rất nhiều. Đối với số học mô-đun, các thông số hiện tại đang xử lý chỉ là số nguyên và các phép toán chủ yếu được dùng là cộng, trừ, nhân và chia.

Có thể nói quy trình tạo xâu luôn đặc biệt quan trọng đối với miền và phân tử mạng. Để giúp thuật toán xâu ký tự có thể phát huy hết khả năng thì các xâu phải khớp trong cùng một chuỗi dài hoặc khi xác nhận chuỗi bằng cách phân tích cú pháp qua giới hạn đã được xác định từ trước. Thuật toán phân tích cú pháp và xâu ký tự được dùng chỉ yếu trong quá trình phát triển web cho URL.

Thuật toán biến đổi Fourier được biết đến là một trong những thuật toán đơn giản nhưng rất mạnh. Loại thuật toán lập trình này được dùng để chuyển đổi tín hiệu từ tên miền thời gian sang miền tần số và ngược lại.

Hiện tại, các mạng kỹ thuật số như wifi, internet, máy tính, điện thoại, vệ tinh, bộ định vị đều sử dụng thuật toán biến đổi Fourier để vận hành.

Mã hóa Huffman là nền tảng của nén văn bản hiện đại. Nó hoạt động bằng cách xem xét tần suất các ký tự khác nhau xuất hiện trong một văn bản và sắp xếp chúng trong một cây dựa trên tần suất này.

Thuật toán các tập không giao nhau là một cấu trúc dữ liệu đóng vai trò như một cấu trúc trợ giúp một thuật toán được dùng để biểu diễn nhiều tập hợp trong mảng riêng lẻ. Và mỗi mục chính là một phần tử của nhiều tập hợp.

Do đó, các bộ tách rời được đại diện cho các phần tử được kết nối với nhau trong cùng một thuật toán đồ thị hay phân đoạn của một hình ảnh.

Thuật toán hệ số tích phân là một thuật toán cung cấp hướng dẫn từng bước cho bạn về cách lấy các thừa số nguyên tố của một số tổng hợp. Hệ số tích phân giúp bạn giải quyết các vấn đề phức tạp trong nền tảng mã hóa yêu cầu bạn phải giải quyết các số nguyên phức hợp lớn.

Đọc thêm: Abap Là Gì? Tìm Hiểu Về Ngôn Ngữ Lập Trình Có Thu nhập Khủng

Trên đây là những chia sẻ của Glints về khái niệm thuật toán là gì? Có những loại thuật toán nào được sử dụng rộng rãi trong quá trình lập trình. Mong rằng từ những chia sẻ trên bạn đọc sẽ hiểu rõ hơn về thuật toán và biết cách ứng dụng thuật toán hiệu quả cho công việc lập trình của mình.

Theo dõi Glints để xem thêm nhiều thông tin hữu ích khác nhé!

Chúng tôi rất buồn khi bài viết không hữu ích với bạn

Hãy giúp chúng tôi cải thiện bài viết này!

Làm sao để chúng tôi cải thiện bài viết này?

Có thể bạn cũng thích

Khám phá ngay 10k+ công việc mới tại GlintsNền tảng tuyển dụng hàng đầu Đông Nam Á

Lý thuyết: Bài toán và thuật toán trang 32 SGK Tin học 10>

1. Khái niệm bài toán

– Bài toán là một việc nào đó mà con người muốn máy tính thực hiện.

– Các yếu tố của một bài toán:

+ Input: Thông tin đã biết, thông tin đưa vào máy tính.

+ Output: Thông tin cần tìm, thông tin lấy ra từ máy tính.

– Ví dụ: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương, khi đó:

+ Input: hai số nguyên dương A, B.

+ Output: ước chung lớn nhất của A và B

2. Khái niệm thuật toán

a) Khái niệm

Thuật toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.

b) Biểu diễn thuật toán

– Sử dụng cách liệt kê: nêu ra tuần tự các thao tác cần tiến hành.

– Sử dụng sơ đồ khối để mô tả thuật toán.

c) Các tính chất của thuật toán

– Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác.

– Tính xác định: sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo.

– Tính đúng đắn: sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.

3. Một số ví dụ về thuật toán

Ví dụ 1: Kiểm tra tính nguyên tố của 1 số nguyên dương

• Xác định bài toán

– Input: N là một số nguyên dương;

– Output: ″N là số nguyên tố″ hoặc ″N không là số nguyên tố″.

• Ý tưởng:

– Định nghĩa: ″Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N″

– Nếu N = 1 thì N không là số nguyên tố.

– Nếu 1 < N < 4 thì N là số nguyên tố.

– N ≥ 4: Tìm ước i đầu tiên > 1 của N.

+ Nếu i < N thì N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N).

+ Nếu i = N thì N là số nguyên tố.

• Xây dựng thuật toán

a) Cách liệt kê

– Bước 1: Nhập số nguyên dương N;

– Bước 2: Nếu N=1 thì thông báo ″N không là số nguyên tố″, kết thúc;

– Bước 3: Nếu N<4 thì thông báo ″N là số nguyên tố″, kết thúc;

– Bước 4: i ← 2;

– Bước 5: Nếu i là ước của N thì đến bước 7;

– Bước 6: i ← i+1 rồi quay lại bước 5; (Tăng i lên 1 đơn vị)

– Bước 7: Nếu i = N thì thông báo ″N là số nguyên tố″, ngược lại thì thông báo ″N không là số nguyên tố″, kết thúc;

b) Sơ đồ khối

Lưu ý: Nếu N >= 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố.

Ví dụ 2: Sắp xếp bằng cách tráo đổi

• Xác định bài toán

– Input: Dãy A gồm N số nguyên a1, a2,…, an

– Output: Dãy A được sắp xếp thành dãy không giảm.

• Ý tưởng

– Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. (Các số lớn sẽ được đẩy dần về vị trí xác định cuối dãy).

– Việc này lặp lại nhiều lượt, mỗi lượt tiến hành nhiều lần so sánh cho đến khi không có sự đổi chỗ nào xảy ra nữa.

• Xây dựng thuật toán

a) Cách liệt kê

– Bước 1: Nhập N, các số hạng a1, a2,…, an;

– Bước 2: M ← N;

– Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp, rồi kết thúc;

– Bước 4: M ← M – 1, i ← 0;

– Bước 5: i ← i + 1;

– Bước 6: Nếu i > M thì quay lại bước 3;

– Bước 7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;

– Bước 8: Quay lại bước 5;

b) Sơ đồ khối

Ví dụ 3: Bài toán tìm kiếm

• Xác định bài toán

– Input : Dãy A gồm N số nguyên khác nhau a1, a2,…, an và một số nguyên k (khóa)

Ví dụ : A gồm các số nguyên ″ 5 7 1 4 2 9 8 11 25 51″ và k = 2 (k = 6).

– Output: Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 2 trong dãy là 5 (không tìm thấy 6)

• Ý tưởng

Tìm kiếm tuần tự được thực hiện một cách tự nhiên: Lần lượt đi từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khóa cho đến khi gặp một số hạng bằng khóa hoặc dãy đã được xét hết mà không tìm thấy giá trị của khóa trên dãy.

• Xây dựng thuật toán

a) Cách liệt kê

– Bước 1: Nhập N, các số hạng a1, a2,…, aN và giá trị khoá k;

– Bước 2: i ← 1;

– Bước 3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;

– Bước 4: i ←i+1;

– Bước 5: Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc;

– Bước 6: Quay lại bước 3;

b) Sơ đồ khối

Ví dụ 4: Tìm kiếm nhị phân

• Xác định bài toán

– Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2,…, an và một số nguyên k.

Ví dụ: Dãy A gồm các số nguyên 2 4 5 6 9 21 22 30 31 33 và k = 21 (k = 25)

– Output : Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 21 trong dãy là 6 (không tìm thấy 25)

• Ý tưởng

Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh vùng tìm kiếm bằng cách so sánh k với số hạng ở giữa phạm vi tìm kiếm (agiữa), khi đó chỉ xảy ra một trong ba trường hợp:

– Nếu agiữa= k thì tìm được chỉ số, kết thúc;

– Nếu agiữa > k thì việc tìm kiếm thu hẹp chỉ xét từ adầu (phạm vi) → agiữa – 1;

– Nếu agiữa < k việc tìm kiếm thu hẹp chỉ xét từ agiữa + 1→acuối (phạm vi).

Quá trình trên được lặp lại cho đến khi tìm thấy khóa k trên dãy A hoặc phạm vi tìm kiếm bằng rỗng.

• Xây dựng thuật toán

a) Cách liệt kê

– Bước 1: Nhập N, các số hạng a1, a2,…, aN và giá trị khoá k;

– Bước 2: Đầu ←1; Cuối ←N;

– Bước 3: Giữa←[(Đầu+Cuối)/2];

– Bước 4: Nếu agiữa = k thì thông báo chỉ số Giữa, rồi kết thúc;

– Bước 5: Nếu agiữa > k thì đặt Cuối = Giữa – 1 rồi chuyển sang bước 7;

– Bước 6: Đầu ←Giữa + 1;

– Bước 7: Nếu Đầu > Cuối thì thông báo không tìm thấy khóa k trên dãy, rồi kết thúc;

– Bước 8: Quay lại bước 3.

b) Sơ đồ khối

Loigiaihay.com

  • Câu 1 trang 44 SGK Tin học 10
  • Câu 3 trang 44 SGK Tin học 10
  • Câu 2 trang 44 SGK Tin học 10
  • Câu 4 trang 44 SGK Tin học 10
  • Câu 6 trang 44 SGK Tin học 10

>> Xem thêm

Các bài khác cùng chuyên mục

  • Câu 6 trang 162 SGK Tin học lớp 10
  • Câu 2 trang 162 SGK Tin học 10
  • Lý thuyết Thực hành 10: Sử dụng trình duyệt Internet Explorer trang 152 SGK Tin học 10
  • Hướng dẫn thực hành 10: Sử dụng trình duyệt Internet Explorer trang 152 SGK Tin học 10
  • Bài thực hành 11: Thư điện tử và máy tìm kiếm thông tin trang 155 SGK Tin học 10

Thuật toán là một phương thức gồm tập hợp các câu lệnh hay các bước được thực hiện theo một thứ tự nhất định nhằm giải quyết một vấn đề logic nào đó. Từ thuật toán còn được gọi là Algorithm, nó được đặt theo tên của một nhà toán học người Trung Á là al’Khwarizmi. Ông là tác giả của một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng và mạch lạc cách giải những bài toán. Sau này, phương pháp này đã được xem là một chuẩn mực và được nhiều nhà toán học khác áp dụng theo.

Trong toán học và khoa học máy tính, thuật toán máy tính, hay còn gọi là giải thuật, là một tập hợp 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, nhằm giải quyết một lớp vấn đề hoặc để thực hiện một phép tính. Các thiết bị máy tính sử dụng thuật toán để thực hiện các chức năng của nó một cách rõ ràng như thực hiện các phép tính, suy luận tự động, xử lý dữ liệu (database), và các tác vụ khác.

Tìm việc làm, tuyển dụng software developer có thể bạn quan tâm:

– Software Developer (ASP.Net MVC / DotNet / Java)

– Software Developer (ReactJs/ React Native)

Thuật toán là một tập hợp các bước để giải quyết một vấn đề cụ thể. Còn cấu trúc dữ liệu là một vị trí được đặt tên và có thể được sử dụng để lưu trữ, tổ chức dữ liệu. Thuật toán và cấu trúc dữ liệu cho phép chúng ta viết các chương trình rên laptop một cách hiệu quả và tối ưu. Hai thành phần này hỗ trợ nhau, các thuật toán sẽ cần cấu trúc dữ liệu bên trong để làm cho chúng hoạt động theo đúng kỳ vọng. Ví dụ, nếu chúng ta cần sắp xếp một danh sách thì có thể sử dụng cấu trúc dữ liệu mảng để lưu trữ và dùng thuật toán để sắp xếp các phần tử trong danh sách đó theo mong muốn.

Tối ưu hóa việc tìm kiếm: thuật toán chính là chỉ dẫn để tìm thấy kết quả cho vấn đề một cách tối ưu nhất. Các lập trình viên sử dụng thuật toán để tìm ra con đường ngắn nhất để giải quyết vấn đề. Chẳng hạn, Google Map, Grab, Uber sử dụng thuật toán để tính toán quãng đường ngắn nhất, thuận tiện nhất khi hướng dẫn, hỗ trợ khách hàng di chuyển. Một ví dụ khách là Google, bạn có thể tìm bất cứ thông tin gì tại đây. Vì Google luôn cập nhật và nâng cấp thuật toán để cung cấp thông tin cho người dùng về mọi lĩnh vực, với tốc độ trả kết quả cực kỳ nhanh, chỉ trong 1 giây có thể hiển thị lên đến vài ngàn kết quả.

Khả năng bảo mật tốt: thuật toán đều được mã hóa thành các chuỗi ký tự. Khi truyền tải và nhận dữ liệu đều cần mã hóa. Vì thế, có thể giảm sự xâm nhập từ các hacker. Điều này thể hiện khả năng bảo mật tốt của thuật toán.

Tính “không mập mờ” và “có thể thực thi được” được gọi chung là tính xác định. Trong kỹ thuật phần mềm, thuật toán phải là một dãy hữu hạn các bước rõ ràng, không mập mờ và có thể thực thi được, theo đúng trình tự để ra được kết quả như ta mong muốn. Vì vậy, bất kỳ thuật toán nào cũng phải có những bước được xác định, theo một trình tự nhất định, được thiết lập ngay từ ban đầu.

Số bước hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính hữu hạn. Số bước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Tính “dừng” hay hữu hạn là tính chất rất dễ bị vi phạm vì sai sót khi trình bày thuật toán. Mọi thuật toán đều nhằm thực hiện một công việc nhất định và cho ra kết quả khi thực hiện xong. Nếu thuật toán không thỏa được tính hữu hạn thì ta nói rằng thuật toán bị lặp vô tận hoặc bị quẩn, không cho ra được kết quả cuối cùng.

Khi giải một bài toán, tất nhiên chúng ta đều mong muốn đạt được kết quả đúng đắn. Và thuật toán được sinh ra chính là để tìm ra được kết quả đúng cho bài toán hay vấn đề cụ thể. Tuy nhiên tính “đúng” dù là một tính chất khá hiển nhiên nhưng cũng khó để đạt tới. Bởi vì trong thực tế, có những vấn đề mà chúng ta cần phải nghiên cứu và thử nghiệm nhiều lần mới tìm ra được thuật toán hoàn hảo nhất để đưa ra đúng kết quả.

Tính hiệu quả của thuật toán là một yếu tố được đánh giá để chọn lựa cách giải quyết cho vấn đề bài toán trên thực tế. Tính hiệu quả của thuật toán được đánh giá dựa trên các tiêu chuẩn như khối lượng tính toán, thời gian và không gian khi thi hành thuật toán. Ngoài ra, một tiêu chuẩn cũng được sử dụng nhiều để đánh giá tính hiệu quả của thuật toán đó là độ phức tạp và logic của thuật toán.

Tính tổng quát của thuật toán nói đến việc thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không chỉ áp dụng được cho một số trường hợp riêng biệt nào đó. Có thể hiểu rằng thuật toán phải giống như các công thức toán học, có thể áp dụng nhiều. Tuy nhiên trong thực tế, cũng có các thuật toán được xây dựng dành riêng cho một bài toán, một vấn đề. Vì vậy, không phải thuật toán nào cũng cần đảm bảo được tính tổng quát mà phải tùy vào trường hợp sử dụng.

– Phân tích và phác thảo thuật toán: Bước đầu tiên, chúng ta cần phân tích rõ vấn đề, sau đó hình dung được hướng giải quyết và chiến thuật thiết kế thuật toán. Để hoàn thành được này, ta cần đến khá nhiều kiến thức căn bản của môn Cấu trúc dữ liệu và giải thuật, cụ thể, tiêu biểu là 5 chiến thuật thiết kế thuật toán sau: Chia để trị – divide and conquer, Giải thuật tham ăn – Greedy Method

Lập trình quy hoạch động – Dynamic Programming, Back Tracking và Branch and Bound. Trong đó, chiến thuật chia để trị là được sử dụng phổ biến nhất.

– Kiểm tra thuật toán: Sau khi thiết kế xong thuật toán, ta cần kiểm tra tính đúng đắn của nó bằng cách đưa thuật toán vào máy tính. Sau đó, nhập input, tức tài liệu nguồn vào ở định dạng tương thích. Bước kiểm tra này là để đảm bảo thuật toán sẽ hoạt động trơn tru trên mọi ngôn từ lập trình.

– Đánh giá thuật toán: Để biết được thuật toán có hiệu quả hay không thì chúng ta cần phải đánh giá nó. Ta có thể đánh giá hiệu năng thuật toán theo 2 yếu tố là thời hạn thực thi và bộ nhớ sử dụng. Vì trong quá trình chạy thuật toán thì CPU cần tiêu tốn thời gian quyết và xử lý để thực thi những phép toán, còn bộ nhớ sẽ là nơi chứa tài liệu và chương trình thực thi.

– Test chương trình thuật toán: Việc test chương trình được thực hiện bởi các Tester sẽ chia thành 2 giai đoạn là debugging và profiling. Debugging là quá trình thực thi chương trình dựa trên một tập dữ liệu mẫu để xác định các lỗi xảy ra (loại lỗi, vị trí lỗi,…) và khắc phục chúng. Tuy nhiên giai đoạn này hầu như không bao giờ phát hiện được 100% lỗi. Profiling cũng là quá trình thực thi chương trình trên một tập dữ liệu mẫu nhưng trong giai đoạn này, người ta sẽ đo thời gian cũng như dung lượng bộ nhớ.

– Hoàn thiện thuật toán và ứng dụng: Sau khi đã hoàn tất các bước trên thì ta sẽ một lần nữa kiểm thử lại, đảm bảo thuật toán không còn lỗi hay sai sót nào. Và cuối cùng là sử dụng thuật toán để giải quyết vấn đề hay bài toán mà bạn hay công ty đang gặp phải.

Dùng ngôn ngữ tự nhiên là phương pháp biểu diễn thuật toán bằng cách mô tả các bước thực thi theo ngôn ngữ thường ngày. Phương pháp này không đòi hỏi người viết và người đọc thuật toán phải nắm các nguyên tắc. Tuy nhiên nó khiến cho việc biểu diễn thuật toán trở nên dài dòng, không trực quan, không thể hiện được cấu trúc thuật toán nên có thể gây khó hiểu hoặc hiểu lầm. Vì không có nguyên tắc nào cho phương pháp này nên nếu sử dụng thì bạn nên phân cấp từng bước theo số thứ tự một cách dễ hiểu nhất.

Hiện nay, có rất nhiều các phần mềm vẽ lưu đồ nhanh và tốt nên sẽ thuận tiện cho việc biểu diễn thuật toán. Bên cạnh đó, bạn nên áp dụng theo các thao tác sau đây để có một lưu đồ hoàn chỉnh nhất.

– Thao tác chọn lựa (decision): Thao tác chọn lựa được biểu diễn bằng một hình thoi, ở trong chứa biểu thức điều kiện.

– Thao tác xử lý (process): Thao tác xử lý được biểu diễn bằng một hình chữ nhật, ở trong chứa nội dung xử lý.

– Ðường đi (route): Để thể hiện trình tự thực hiện các thao tác, người ta sử dụng đường cung nối các bước kế tiếp nhau. Trên đường cung có mũi tên để chỉ hướng hay thứ tự thực hiện.

– Ðiểm cuối (terminator): Ðifểm cuối là điểm khởi đầu và cũng là điểm kết thúc của thuật toán, nó được biểu diễn bằng hình ovan, bên trong có ghi chữ start/begin/bắt đầu hoặc end/kết thúc. Nếu là điểm khởi đầu thì điểm cuối chỉ có cung đi ra còn là điểm kết thúc thì có cung đi vào.

– Ðiểm nối (connector): Ðiểm nối dùng để nối các phần khác nhau của một lưu đồ. Bên trong điểm nối, người ta đặt một ký hiệu để biết sự liên hệ giữa các điểm nối đó.

– Ðiểm nối sang trang (off-page connector): Điểm nối sang trang cũng giống như điểm nối nhưng nó được dùng khi lưu đồ quá lớn, phải vẽ trên nhiều trang. Bên trong điểm nối sang trang, người ta cũng đặt một ký hiệu để biết được sự liên hệ giữa điểm nối của các trang.

Phương pháp biểu diễn thuật toán thứ ba chính là mã giả. Khi sử dụng phương pháp này để biểu diễn thuật toán, ta cần vay mượn các cú pháp của một ngôn ngữ lập trình nào đó và vẫn sử dụng một phần ngôn ngữ tự nhiên. Tất nhiên, mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Phương pháp dùng mã giả để biểu diễn thuật toán vừa tận dụng được các khái niệm trong các loại ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán.

Một lập trình viên có cần thiết phải học và biết về thuật toán hay không? Bạn vẫn có thể là một lập trình viên giỏi nếu không biết thuật toán. Tuy nhiên, đây là chìa khóa giúp bạn tiết kiệm được rất nhiều thời gian và công sức. Ví dụ, nếu ai đó đưa cho bạn một dãy các số và yêu cầu bạn phải tìm xem một con số bất kỳ có nằm trong dãy số đó hay không. Nếu bạn không biết thuật toán, bạn phải làm nó theo cách thủ công. Nhưng khi bạn biết thuật toán, dù số lượng có nhiều đến đâu, bạn chỉ cần dùng thuật toán và tìm ra nó một cách dễ dàng.

Hơn nữa, việc giải thuật toán cũng giống như giải quyết các vấn đề. Khi đã thành thạo giải thuật toán, tức là kỹ năng giải quyết vấn đề của bạn đã được rèn luyện và cải thiện rất nhiều. Vì thế, doanh nghiệp luôn ưu tiên tuyển dụng những lập trình viên hiểu biết về thuật toán.

Sau đây là 10 loại thuật toán mà lập trình viên nên biết để ghi điểm với nhà tuyển dụng và tối ưu hóa quy trình làm việc:

Thuật toán Hashing: hashing là thuật toán dùng để phát hiện và xác định dữ liệu phù hợp thông qua khóa, ID. Mục đích của Hashing là tìm ra lỗi, quản lý cache, mã hóa và tra cứu. Cụ thể, hashing được tích hợp sẵn trên key để cho ra giá trị chính xác nhất. Đây cũng là mã định danh duy nhất cho bộ dữ liệu và tính toán để người dùng tạo các giá trị dữ liệu duy nhất.

Thuật toán tìm kiếm: thuật toán tìm kiếm sử dụng các cấu trúc dữ liệu tuyến tính hoặc đồ thị. Nó cho phép các nhà phát triển dễ dàng tìm thấy hiệu quả của việc sắp xếp các tập dữ liệu với các hàm có độ phức tạp thời gian O(log N).

Thuật toán sắp xếp: thuật toán sắp xếp giúp sắp đặt các dữ liệu một cách có tổ chức. Các khối xây dựng cơ bản của thuật toán sắp xếp là các phần dữ liệu được so sánh với nhau để xác định thứ tự tương ứng của chúng. Ngoài ra, còn các thuật toán sắp xếp khác như: sắp xếp đếm, sắp xếp hợp nhất và sắp xếp theo nhóm.

Thuật toán lập trình động: là thuật toán dùng để giải các bài toán trí tuệ phức tạp thông qua quá trình phân rã bài toán thành các bài toán con nhỏ hơn. Khi vấn đề được giải quyết, việc xây dựng lại một câu hỏi phức tạp đòi hỏi phải ghi nhớ các kết quả nhỏ hơn để trả lời câu hỏi phức tạp ban đầu. Lần sau nếu có vấn đề phát sinh, nó sẽ được giải quyết nhanh hơn nhiều.

Thuật toán Dijkstra: đây là một phương pháp dùng để tìm ra cách di chuyển nhanh nhất giữa 2 vị trí. Nó được áp dụng cho phổ biến các ứng dụng tìm đường, vận chuyển ngày nay hoặc trong trí tuệ nhân tạo, các trò chơi.

Thuật toán phân tích liên kết: được sử dụng chủ yếu trong lĩnh vực mạng, nhằm tăng khả năng liên kết với nhiều thực thể khác nhau trong cùng một miền.Thuật toán liên kết sử dụng các ma trận phức tạp và biểu diễn đồ họa để liên kết các thành phần tương tự trong cùng một miền. Thuật toán này được các ông lớn như Google, Facebook, Twitter,… sử dụng.

Thuật toán Mô-đun: thuật toán mô-đun giúp các bài toán phức tạp trở nên dễ dàng hơn. Các thông số được thuật toán mô-đun giải quyết là các số nguyên, thông qua phép tính chủ yếu là cộng, trừ, nhân, chia

Thuật toán biến đổi Fourier: thuật toán này tuy đơn giản nhưng có tác dụng rất lớn. Nó được dùng để chuyển đổi tín hiệu từ tên miền thời gian sang miền tần số và được áp dụng cho các mạng kỹ thuật số hiện nay như: wifi, internet, máy tính, điện thoại, vệ tinh, bộ định vị đều sử dụng thuật toán biến đổi Fourier để vận hành.

Thuật toán các tập không giao nhau: là một cấu trúc trợ giúp thuật toán, được dùng để biểu diễn nhiều tập hợp trong mảng riêng lẻ. Và mỗi mục chính là một phần tử của nhiều tập hợp

Hệ số tích phân: dùng để hướng dẫn từng bước về cách lấy các thừa số nguyên tố của một số tổng hợp. Hệ số tích phân dùng để giải quyết các vấn đề phức tạp trong nền tảng mã hóa yêu cầu bạn phải giải quyết các số nguyên phức hợp lớn.

Xem thêm:

– Cách viết CV xin việc ngành IT, CNTT đơn giản mà chuẩn nhất

– ICT là gì? Ứng dụng trong ngành IT và mọi lĩnh vực đời sống

– Tuyển tập bài test và bộ câu hỏi phỏng vấn IT thường gặp

Hy vọng rằng, qua bài viết này bạn đã có cái nhìn rõ ràng hơn về thuật toán để áp dụng trong công việc của mình. Nếu thấy bài viết này hay và có ích thì đừng quên chia sẻ hoặc bình luận bên dưới nhé!

Nguồn tham khảo: https://vi.wikipedia.org/wiki/Thuật_toán

Tin Học Lớp 6 Bài 1 Chủ Đề F | Khái Niệm Thuật Toán | Trang 80 – 82 | Cánh Diều
Tin Học Lớp 6 Bài 1 Chủ Đề F | Khái Niệm Thuật Toán | Trang 80 – 82 | Cánh Diều

Áp dụng vào bài toán

Bây giờ, ta cùng xem một ví dụ về đề bài trong các cuộc thi lập trình thi đấu:

Một đề bài trên trang web lập trình codeforces.com

Những đề bài như trên rất phổ biến ở các trang web lập trình online, và đôi khi là cả ở các đề thi HSG cấp quận (huyện), tỉnh (thành phố), quốc gia,…Nó cho chúng ta biết giới hạn thời gian và không gian của bài toán:

  • Giới hạn thời gian (Time limit per test): giây.
  • Giới hạn không gian (Memory limit per test): Megabytes.

Những ràng buộc này cho chúng ta biết, chương trình phải cho ra kết quả sau tối đa 2 giây, và bộ nhớ sử dụng không được vượt quá Megabytes. Để tính toán, trước hết ta sẽ tính độ phức tạp thời gian và không gian của thuật toán đã cài đặt, giả sử lần lượt là và . Sau đó, dựa vào một số kiến thức dưới đây để cải tiến thuật toán nếu cần:

  • Thời gian thực thi thuật toán sẽ giây nếu như .
  • Không gian sử dụng sẽ bằng tích giữa và kích thước của kiểu dữ liệu đầu vào. Chẳng hạn, và có kiểu dữ liệu

    long long

    , ta sẽ tính được không gian sử dụng là khoảng bytes, tương đương với khoảng gần Megabytes – hoàn toàn đáp ứng được ràng buộc. Thông thường, giới hạn không gian cho phép trong các bài toán là khoảng Megabytes, vì vậy nên nếu là kiểu

    int

    , và khoảng nếu là kiểu

    long long

    .

Sau khi tính toán được các yếu tố trên, các bạn sẽ tối ưu lại thuật toán để thỏa mãn được các ràng buộc.

Tài liệu tham khảo

All rights reserved

Đị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 có thể là “một tập hợp các quy tắc xác định chính xác một chuỗi hoạt động”,[17] mà sẽ bao gồm tất cả các chương trình máy tính (bao gồm cả các chương trình không thực hiện phép tính số) và (ví dụ) bất kỳ thủ tục hành chính quy định 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 cuối cùng nó dừng lại [20] – mặc dù các vòng lặp vô hạn đôi khi có thể chấp nhận đượ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 định ước chung lớn nhất của hai số nguyên; một ví dụ được mô tả bằng lưu đồ ở trên và là ví dụ trong phần sau.

Boolos, Jeffrey & 1974, 1999Lỗi harv: không có mục tiêu: 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 đó)

Giới thiệu về các thuật toán - Khoa học Máy tính tập 13 | Tri thức nhân loại
Giới thiệu về các thuật toán – Khoa học Máy tính tập 13 | Tri thức nhân loại

Thuật toán là gì?

Thuật toán là gì? thuật toán hay còn gọi là giải thuật được hiểu một cách đơn giản là một tập hợp hữu hạn bao gồm các hướng dẫn được xác định rõ ràng, thực hiện được bằng máy tính, thường được dùng để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính nào đó.

Nói một cách dễ hiểu hơn, mỗi bài toán thường sẽ được ví như một chiếc hòm đựng đầy kho báu, và chìa khóa chính là “thuật toán”. Nếu sử dụng không đúng chìa khóa đó thì bạn vẫn có thể mở được hòm kho báu, tuy nhiên sẽ mất khá nhiều thời gian và công sức, hoặc nếu mở được hòm thì kho báu bên trong cũng sẽ có thể bị méo mó, không được toàn vẹn.

Việc sử dụng đúng chìa khóa “thuật toán” sẽ giúp bạn dễ dàng lấy được kho báu nhanh chóng. Dĩ nhiên, mỗi hòm kho báu sẽ luôn cần đến một loại chìa khóa khác nhau, tương tự như thuật toán sẽ luôn có những giải thuật xác định.

Xem thêm:

  • Lập trình viên là gì? 10 Bí quyết trở thành lập trình viên giỏi
  • Trình hướng đối tượng là gì? 5 ngôn ngữ lập trình phổ biến
  • Kỹ sư phần mềm là gì? 8 kỹ năng cần có của kỹ sư phần mềm
  • Lập trình nhúng là gì? Mức lương & Kỹ năng quan trọng nhất
  • Software engineer là gì? Mức lương hiện nay và yêu cầu công việc
  • Lập trình game là gì? Cơ hội việc làm và mức thu nhập 2023

Các đặc trưng của thuật toán

Mỗi thuật toán luôn luôn có đủ đặc trưng sau:

  • Có đầu vào (Input): Thuật toán nhận dữ liệu vào từ một tập nào đó.
  • Có đầu ra (Output): Từ dữ liệu đầu vào, thuật toán sẽ tính toán và đưa ra kết quả tương ứng với đầu vào đó.
  • Tính chính xác: Các bước của thuật toán được mô tả chính xác.
  • Tính hữu hạn: Thuật toán cần phải đưa ra được output sau một số hữu hạn các bước với mọi input.
  • Tính đơn trị: Các kết quả trung gian của từng bước thực hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc và input và kết quả của các bước trước.
  • Tính tổng quát: Thuật toán có thể áp dụng để giải mọi bài toán có cùng dạng với bài toán đã giải.

Chẳng hạn, dưới đây là thuật toán tìm số ước của một số nguyên dương được viết trong một hàm

int count_divisors(int N)


int count_divisors(int N) { int divisors = 0; for (int i = 1; i <= N; ++i) if (N % i == 0) ++divisors; return divisors; }

Phân tích tính hiệu quả của thuật toán

KHÁI NIỆM BÀI TOÁN VÀ THUẬT TOÁN [TIN HỌC]
KHÁI NIỆM BÀI TOÁN VÀ THUẬT TOÁN [TIN HỌC]

Khái niệm

Thuật toán – hay còn gọi là giải thuật – là khái niệm quan trọng nhất trong Tin học. Nó là nền tảng cho mọi khía cạnh của Tin học. Khái niệm về thuật toán đã tồn tại từ thời cổ đại, sớm nhất ở đế chế Babylonia với thuật toán chia vào năm 2500 TCN. Khái niệm về thuật toán có thể phát biểu như sau:

Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề.

Với sự phát triển chóng mặt của khoa học máy tính, các thuật toán cũng ngày càng phát triển về số lượng cũng như chất lượng. Trong phạm vi của lập trình thi đấu, chúng ta sẽ tập trung nghiên cứu chuyên sâu về các thuật toán từ dễ đến khó, phục vụ cho các kỳ thi về thuật toán như HSG Tin học, Tin học trẻ hay các kỳ thi thuật toán online. Toàn bộ các cài đặt sẽ được viết ở ngôn ngữ C++ vì như đã nói ở các chuyên đề lập trình cơ bản, C++ là một ngôn ngữ rất mạnh trong lập trình thi đấu.

Các quy tắc đánh giá độ phức tạp không gian

Trước tiên, ta cùng xem lại bảng không gian lưu trữ tiêu tốn của các kiểu dữ liệu nguyên thủy trong C++:

Các kiểu dữ liệu đều có kích thước bộ nhớ ( byte, byte,…). Byte là một đơn vị đo dung lượng lưu trữ trên máy tính, bên dưới nó là bit ( byte bit) và bên trên nó có các đơn vị khác như Kilobyte (KB), Megabyte (MB), Gigabyte (GB), Terabyte (TB),…Các đơn vị này có một đặc điểm chung từ Byte trở lên:

Đơn vị sau Đơn vị trước

Chẳng hạn như MB = KB, TB = MB,…

Độ phức tạp không gian của một thuật toán sẽ được tính toán thông qua hàm trước, rồi mới đổi ra giá trị dung lượng cụ thể. Nó là tổng của tất cả bộ nhớ sử dụng trong việc nhập dữ liệu đầu vào và bộ nhớ phụ sử dụng khi thực hiện thuật toán. Các quy tắc tính toán cơ bản như sau:

  • Các biến đơn khi khai báo (một hoặc nhiều biến): .
  • Khai báo mảng một chiều kích thước : .
  • Khai báo mảng nhiều chiều có kích thước các chiều lần lượt là : .
  • Lời gọi đệ quy: Phụ thuộc vào số lượng lời gọi đệ quy lưu đồng thời trong phân vùng bộ nhớ call stack (sẽ học ở bài Hàm đệ quy).

Tổng bộ nhớ sử dụng trong toàn bộ chương trình sẽ hợp thành độ phức tạp không gian của chương trình là . Sau khi tính được ta sẽ quy đổi nó ra dung lượng bộ nhớ tương ứng với kiểu dữ liệu của input để tính ra được bộ nhớ sử dụng một cách tương đối chính xác.

Hướng dẫn học Tin Học lớp 6 - Bài 15: Thuật toán
Hướng dẫn học Tin Học lớp 6 – Bài 15: Thuật toán

Các quy tắc đánh giá độ phức tạp thời gian

Để đánh giá thời gian thực hiện thuật toán, ta xuất phát từ các lệnh đơn trong chương trình, rồi tới các câu lệnh có cấu trúc, các khối lệnh phức tạp hơn, sau đó hợp lại thành thời gian thực hiện cả chương trình. Cụ thể ta có các quy tắc:

  • Các lệnh đơn (lệnh khai báo, gán, nhập xuất dữ liệu, phép toán số học,…): Thời gian .
  • Các khối lệnh: Giả sử một khối lệnh gồm các câu lệnh có thời gian thực hiện lần lượt là thì thời gian thực hiện của cả khối lệnh là: .
  • Câu lệnh rẽ nhánh: Ta có cú pháp lệnh rẽ nhánh là:

    Giả sử thời gian thực hiện của câu lệnh và câu lệnh lần lượt là và thì thời gian thực hiện lệnh rẽ nhánh là: .


    if ({Điều_kiện}) {Câu_lệnh_1} else {Câu_lệnh_2}

  • Câu lệnh lặp: Giả sử thời gian thực hiện phần thân của lệnh lặp là và số lần lặp tối đa của vòng lặp là thì thời gian thực hiện của cả vòng lặp là . Điều này áp dụng cho tất cả các vòng lặp

    for

    ,

    while



    do...while

    .
  • Sau khi đánh giá được thời gian thực hiện của tất cả các câu lệnh trong chương trình, thời gian thực hiện của toàn bộ chương trình sẽ là thời gian thực hiện của câu lệnh có thời gian thực hiện lớn nhất. Ngoài ra, nếu như độ phức tạp tính toán là với là một hằng số nhỏ, ta có thể bỏ qua và coi như thuật toán có độ phức tạp là – chẳng hạn như có thể coi như .

Thiết kế[sửa | sửa mã nguồn]

Thiết kế thuật toán đề cập đến một phương pháp hoặc một quy trình toán học để giải quyết vấn đề và các thuật toán kỹ thuật. Việc thiết kế các thuật toán là một phần của nhiều lý thuyết giải pháp nghiên cứu hoạt động, chẳng hạn như lập trình động và chia để trị. Các kỹ thuật thiết kế và triển khai các thiết kế thuật toán còn được gọi là các mẫu thiết kế thuật toán,[30] với các ví dụ bao gồm mẫu phương pháp mẫu và mẫu trang trí.

Một trong những khía cạnh quan trọng nhất của thiết kế thuật toán nằm ở việc tạo ra thuật toán có thời gian chạy hiệu quả, còn được gọi là Big O của nó.

Các bước điển hình trong quá trình phát triển 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
Tin học 10 - Bài 4: Bài toán và thuật toán - Khái niệm thuật toán
Tin học 10 – Bài 4: Bài toán và thuật toán – Khái niệm thuật toán

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

Các thuật toán rất cần thiết cho cách máy tính xử lý dữ liệu. Nhiều chương trình máy tính chứa các thuật toán trình bày chi tiết các hướng dẫn cụ thể mà máy tính phải thực hiện — theo một thứ tự cụ thể — để thực hiện một nhiệm vụ cụ thể, chẳng hạn như tính tiền lương của nhân viên hoặc in phiếu điểm của học sinh. Vì vậy, một thuật toán có thể được coi là bất kỳ chuỗi hoạt động nào có thể được mô phỏng bởi một hệ thống hoàn chỉnh Turing. Các tác giả khẳng định luận điểm này bao gồm 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 có thể xác định các quy trình tính toán 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 yêu cầu thuật toán luôn kết thúc. Yêu cầu này làm cho nhiệm vụ quyết định 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 lý thuyết tính toán được gọi là bài toán dừng.

Thông thường, khi một thuật toán được liên kết với xử lý thông tin, dữ liệu có thể được đọc từ nguồn đầu vào, được ghi vào thiết bị đầu ra và được lưu trữ để xử lý thêm. Dữ liệu được lưu trữ được coi là một phần của trạng thái bên trong của thực thể thực hiện thuật toán. Trong thực tế, trạng thái được lưu trữ trong một hoặc nhiều cấu trúc dữ liệu.

Đối với một số quá trình tính toán này, thuật toán phải được xác định chặt chẽ: được chỉ định theo cách nó áp dụng trong mọi trường hợp có thể phát sinh. Điều này có nghĩa là mọi bước có điều kiện phải được xử lý một cách có hệ thống, theo từng trường hợp cụ thể; các tiêu chí cho từng trường hợp phải rõ ràng (và có thể tính toán đượ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 thảo luận về việc chính thức hóa một thuật toán đã giả định các tiền đề của lập trình mệnh lệnh. Đây là quan niệm phổ biến nhất – một quan niệm cố gắng mô tả một nhiệm vụ bằng các phương tiện “máy móc”, rời rạc. Duy nhất cho quan niệm về các 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ố quan niệm 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 có thể được thể hiện bằng nhiều loại ký hiệu, bao gồm ngôn ngữ tự nhiên, mã giả, lưu đồ, biểu đồ drakon, ngôn ngữ lập trình hoặc bảng điều khiển (được xử lý bởi trình thông dịch). Các biểu thức ngôn ngữ tự nhiên của các thuật toán có xu hướng dài dòng và mơ hồ, và hiếm khi được sử dụng cho các 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 là những cách có cấu trúc để thể hiện các thuật toán tránh nhiều sự mơ hồ thường gặp trong các câu lệnh dựa trên ngôn ngữ tự nhiên. Các ngôn ngữ lập trình chủ yếu nhằm mục đích thể hiện các thuật toán dưới dạng 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 các thuật toán.

Có thể có nhiều cách biểu diễn khác nhau và người ta có thể thể hiện một chương trình máy Turing nhất định dưới dạng một chuỗi các bảng máy (xem máy trạng thái hữu hạn, bảng chuyển đổi trạng thái và bảng đ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 của thuật toán có thể được phân loại thành ba cấp độ được chấp nhận của mô 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.

Sự cần thiết của thuật toán hiệu quả

Công nghệ càng phát triển thì sẽ dẫn tới độ lớn dữ liệu cần tính toán ngày càng lớn, tất nhiên khả năng tính toán của máy tính cũng ngày càng phát triển. Nhưng không phải vì việc máy tính hiện đại mà chúng ta có thể bỏ qua tầm quan trọng của một thuật toán hiệu quả. Để làm rõ vấn đề này, tôi xin trích lại một ví dụ trong sách giáo khoa chuyên Tin quyển về thuật toán kiểm tra tính nguyên tố của một số.


bool is_prime(int N) { if (N < 2) // Nếu N nhỏ hơn 2 thì chắc chắn không phải số nguyên tố. return false; // Nếu N có ước trong đoạn [2, N - 1] thì N không phải số nguyên tố. for (int i = 2; i < N; ++i) if (N % i == 0) return false; return true; }

Bên trên là cách cài đặt đơn giản nhất của giải thuật kiểm tra tính nguyên tố. Thuật toán này cần bước kiểm tra trong vòng lặp. Hãy giả sử cần kiểm tra một số có khoảng chữ số, và ta sở hữu một siêu máy tính có thể tính toán được một trăm nghìn tỉ () phép tính trên giây, thì tổng thời gian cần để kiểm tra là:

\frac{10^{25}}{10^{14} \times 60 \times 60 \times 24 \times 365} \approx 3170 \text{ năm!}$$ Tuy nhiên, nếu tinh ý ta có thể nhận xét như sau: Một số $N$ có ước là $x \ (x \le \sqrt{N})$ thì chắc chắn nó cũng có ước là $\frac{N}{x} \ge \sqrt{N}$. Do đó, thay vì duyệt từ $2$ tới $N – 1$ thì ta chỉ cần duyệt từ $2$ tới $\sqrt{N}$ là có thể biết được $N$ có ước nào trong đoạn này hay không: “`cpp bool is_prime(int N) { if (N < 2) // Nếu N nhỏ hơn 2 thì chắc chắn không phải số nguyên tố. return false; // Nếu N có ước trong đoạn [2, N – 1] thì N không phải số nguyên tố. for (int i = 2; i * i <= N; ++i) if (N % i == 0) return false; return true; } “` Theo phương pháp này, vẫn là một số nguyên có khoảng $25$ chữ số nhưng thời gian kiểm tra sẽ giảm xuống còn: $$\frac{\sqrt{10^{25}}}{10^{14}} \approx 0.03 \text{ giây!}

Phương pháp đánh giá độ phức tạp thuật toán

Khai Xuân , Mừng Xuân lixi và bán lấy lộc! Audio Tiến Dũng (098.119.3686) đang phát trực tiếp!
Khai Xuân , Mừng Xuân lixi và bán lấy lộc! Audio Tiến Dũng (098.119.3686) đang phát trực tiếp!

Các đặc trưng nổi bật của thuật toán

Thuật toán sẽ có những đặc trưng nổi bật nhất định có thể giúp bạn nhận biết rõ hơn. Vậy những đặc trưng của thuật toán là gì? Xem chi tiết sau đây:

Tính xác định

Tính “không mập mờ” và “có thể thực thi được” của thuật toán được gọi chung là tính xác định. Trong kỹ thuật phần mềm, thuật toán phải là một dãy hữu hạn các bước rõ ràng, và có thể thực thi được theo đúng trình tự để đưa ra được kết quả như mong muốn. Vì vậy, bất kỳ thuật toán nào cũng có những bước được xác định theo một trình tự nhất định, và được thiết lập ngay từ ban đầu.

Tính hữu hạn

Số bước hữu hạn của thuật toán và tính chất dừng được gọi chung là “tính hữu hạn”. Số bước hữu hạn của thuật toán chính là một tính chất hiển nhiên. Tính “dừng” hay hữu hạn là tính chất rất dễ bị vi phạm vì sai sót khi trình bày một thuật toán. Mọi thuật toán đều nhằm thực hiện một công việc nhất định và cho ra kết quả khi đã thực hiện xong. Nếu thuật toán không thỏa được tính hữu hạn thì thuật toán sẽ bị lặp vô tận hoặc bị quẩn, không cho ra được kết quả cuối cùng.

Tính đúng

Khi giải một bài toán, chúng ta đều mong muốn đạt được kết quả đúng đắn. Và thuật toán được sinh ra chính là để tìm ra được kết quả đúng cho bài toán hay vấn đề cụ thể đang đặt ra. Tuy nhiên tính “đúng” dù là một tính chất khá hiển nhiên nhưng khó để đạt tới. Bởi vì trong thực tế, có những vấn đề mà chúng ta cần phải nghiên cứu cũng như cần thử nghiệm nhiều lần mới có thể tìm ra được thuật toán hoàn hảo để đưa ra đúng kết quả.

Tính tổng quát

Tính tổng quát của thuật toán chính là đang nói đến việc thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không chỉ áp dụng được cho một số trường hợp riêng biệt mà thôi. Có thể hiểu rằng, thuật toán phải giống như công thức toán học, có thể áp dụng nhiều trường hợp. Tuy nhiên, trong thực tế cũng sẽ có các thuật toán được xây dựng dành riêng cho một bài toán hay một vấn đề riêng biệt. Vì vậy, không phải thuật toán nào cũng cần phải đảm bảo được tính tổng quát mà cần phải tùy vào trường hợp sử dụng.

Tính hiệu quả

Tính hiệu quả của thuật toán chính là một yếu tố được đánh giá để chọn lựa cách giải quyết cho vấn đề bài toán dựa trên thực tế. Tính hiệu quả của thuật toán được đánh giá dựa trên các tiêu chuẩn như khối lượng tính toán, thời gian và không gian khi thi hành thuật toán. Ngoài ra, một tiêu chuẩn cũng được sử dụng để đánh giá tính hiệu quả của thuật toán đó là độ phức tạp và logic của thuật toán.

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).

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ở đầu cho định nghĩa của mình bằng: “Tôi sẽ cho bạn thấy rằng bạn không thể chứng minh rằng một chương trình là ‘thanh lịch ‘” —chẳng hạn như một bằng chứng sẽ giải quyết đượ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, có thể có sự cân bằng giữa tính tốt (tốc độ) và tính thanh lịch (tính nhỏ gọn) —một chương trình thanh lịch có thể cần nhiều bước để hoàn thành một phép tính hơn một chương trình kém thanh lịch hơn. Ví dụ sử dụng thuật toán Euclid xuất hiện 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ơ đồ.

Tiên Tri TẬN THẾ, Dị Tượng HOA ÂM PHỦ Nở Rộ, Th.ảm H0ạ Đang Tới?| VĐTH
Tiên Tri TẬN THẾ, Dị Tượng HOA ÂM PHỦ Nở Rộ, Th.ảm H0ạ Đang Tới?| VĐTH

Quy trình để viết một thuật toán

Dưới đây chính là quy trình để có thể viết một thuật toán mà bạn có thể tham khảo để hiểu chi tiết hơn:

Phân tích, phác thảo thuật toán

Bước đầu tiên, cần phân tích rõ vấn đề sau đó hình dung được hướng giải quyết và chiến thuật thiết kế thuật toán. Để hoàn thành bước này, chúng ta cần đến những kiến thức căn bản của môn “Cấu trúc dữ liệu và giải thuật”, cụ thể là 5 chiến thuật thiết kế thuật toán sau: Chia để trị – divide and conquer, Giải thuật tham ăn – Greedy Method.

Kiểm tra thuật toán

Sau khi thiết kế xong thuật toán, chúng ta ta cần triển khai kiểm tra tính đúng đắn của nó bằng cách đưa thuật toán vào máy tính. Sau đó, nhập input, tức tài liệu nguồn vào ở định dạng tương thích. Bước kiểm tra này nhằm giúp đảm bảo thuật toán sẽ hoạt động trơn tru trên mọi ngôn từ lập trình.

Đánh giá thuật toán

Để biết được thuật toán có hiệu quả hay không chúng ta cần phải đánh giá nó. Ta có thể đánh giá hiệu năng thuật toán với 2 yếu tố là thời hạn thực thi và bộ nhớ sử dụng. Bởi vì trong quá trình chạy thuật toán, CPU cần tiêu tốn thời gian quyết và xử lý để thực thi những phép toán, còn bộ nhớ sẽ là nơi chứa tài liệu và các chương trình thực thi.

Test chương trình

Việc test chương trình sẽ được thực hiện bởi các Tester và được chia thành 2 giai đoạn là debugging và profiling. Debugging là quá trình thực thi chương trình dựa trên tập dữ liệu mẫu nhằm để xác định các lỗi xảy ra (loại lỗi, vị trí lỗi,…) và khắc phục chúng. Giai đoạn này hầu như không bao giờ phát hiện được 100% lỗi. Profiling là quá trình thực thi chương trình trên một tập dữ liệu mẫu, nhưng trong giai đoạn này người ta sẽ đo thời gian cũng như dung lượng bộ nhớ.

Hoàn thiện và ứng dụng

Sau khi đã hoàn tất các bước trên thì chúng ta sẽ kiểm tra thử lại một lần nữa, đảm bảo thuật toán không còn lỗi hay sai sót nào. Cuối cùng là sử dụng thuật toán để có thể giải quyết vấn đề hay bài toán đang gặp phải.

Các tiêu chí đánh giá một thuật toán

Thông thường, khi giải một bài toán, chúng ta luôn luôn có xu hướng chọn cách giải “tốt” nhất. Nhưng thế nào là “tốt”? Trong toán học, một cách giải “tốt” có thể là cách giải ngắn gọn, xúc tích, hoặc trên tiêu chí sử dụng những kiến thức dễ hiểu. Còn đối với thuật toán trong Tin học thì dựa vào hai tiêu chuẩn sau:

  • Thuật toán đơn giản, dễ hiểu, dễ cài đặt.
  • Thuật toán hiệu quả: Dựa vào hai yếu tố là thời gian thực hiện thuật toán (còn gọi là độ phức tạp thời gian) và dung lượng bộ nhớ cần thiết để lưu trữ dữ liệu (còn gọi là độ phức tạp không gian). Tuy nhiên, trong bối cảnh hiện tại khi các máy tính có khả năng lưu trữ rất lớn thì yếu tố mà chúng ta cần quan tâm nhiều hơn là độ phức tạp thời gian.
Chuyên gia phong thủy Song Hà: Năm Giáp Thìn sẽ là một năm nhiều biến động về kinh tế | VTC Now
Chuyên gia phong thủy Song Hà: Năm Giáp Thìn sẽ là một năm nhiều biến động về kinh tế | VTC Now

Thuật toán

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 phương pháp hiệu quả, một thuật toán có thể được biểu diễn trong một khoảng không gian và thời gian hữu hạn,[3] và bằng một ngôn ngữ hình thức được xác định rõ ràng [4] để tính toán một hàm số.[5] Bắt đầu từ trạng thái ban đầu và đầu vào ban đầu (có thể trống),[6] các hướng dẫn mô tả một phép tính, khi được thực thi, sẽ tiến hành qua một số [7] hữu hạn các trạng thái kế tiếp được xác định rõ, cuối cùng tạo ra “đầu ra” [8] và chấm dứt ở trạng thái kết thúc cuối cùng. Sự chuyển đổ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 định; một số thuật toán, được gọi là thuật toán ngẫu nhiên, kết hợp đầu vào ngẫu nhiên.[9]

Khái niệm thuật toán đã tồn tại từ thời cổ đại. Các thuật toán số học, chẳng hạn như thuật toán chia, được sử dụng bởi các nhà toán học Babylon cổ đại vào khoảng 2500 TCN và các nhà toán học Ai Cập vào khoảng 1550 TCN.[10] Các nhà toán học Hy Lạp sau đó đã sử dụng các 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 các thuật toán mật mã để phá mã, dựa trên 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.

Phân tích ví dụ

Ví dụ 1: Phân tích độ phức tạp thuật toán của đoạn chương trình sau


#include

using namespace std; int main() { int n; // (1) cin >> n; // (2) int s1 = 0; // (3) for (int i = 1; i <= n; ++i) // (4) s1 += i; // (5) int s2 = 0; // (6) for (int i = 1; i <= n; ++i) // (7) s2 += i * i; // (8) cout << s1 << endl << s2; // (9) return 0; }

Thời gian thực hiện chương trình trên phụ thuộc vào số . Ta phân tích chi tiết:

  • Các lệnh đều có thời gian thực hiện là .
  • Vòng

    for

    số có số lần lặp là và câu lệnh ở phần thân (là câu lệnh ) có thời gian thực hiện . Vậy cả vòng lặp có thời gian thực hiện là . Tương tự với vòng lặp số .

Vậy thời gian thực hiện của cả thuật toán là:

Về độ phức tạp không gian, ta nhận thấy đoạn chương trình hoàn toàn sử dụng các biến đơn không hề phụ thuộc vào giá trị input :

  • Biến : Chỉ có một biến nguyên được sử dụng, không phụ thuộc vào đầu vào độ phức tạp không gian của biến này là .
  • Các biến và : Vì chúng chỉ được sử dụng trong các vòng lặp và không lưu trữ thông tin nào sau khi vòng lặp kết thúc, không có đóng góp vào độ phức tạp không gian cuối cùng. Độ phức tạp không gian của các biến này cũng là .
  • Biến : Đây là biến đại diện cho giá trị đầu vào của chương trình. Biến này chỉ lưu trữ một giá trị nguyên và không phụ thuộc vào kích thước của dữ liệu đầu vào. Do đó, độ phức tạp không gian của biến này cũng là .

Vì vậy độ phức tạp bộ nhớ có thể coi là .

Ví dụ 2: Phân tích độ phức tạp thuật toán của đoạn chương trình sau


#include

using namespace std; int main() { int sum = 0; // (1) for (int i = 1; i <= N; ++i) // (2) for (int j = 1; j <= i; ++j) // (3) sum = sum + 1; // (4) cout << sum; // (5) }

Đoạn chương trình trên có thời gian thực hiện phụ thuộc vào số . Phân tích chi tiết:

  • Câu lệnh và có thời gian thực hiện .
  • Câu lệnh có thời gian thực hiện .
  • Ứng với mỗi giá trị của câu lệnh lặp thì:

    • Khi lệnh lặp thực hiện lần.
    • Khi lệnh lặp thực hiện lần.
    • Khi lệnh lặp thực hiện lần. Như vậy, lệnh lặp có số lần thực hiện là từ đó suy ra cả lệnh lặp có thời gian thực hiện là .

Cả chương trình có thời gian thực hiện là .

Độ phức tạp không gian cũng vẫn là do đoạn chương trình chỉ sử dụng các biến đơn.

Ví dụ 3: Phân tích độ phức tạp thuật toán của đoạn chương trình sau:


#include

using namespace std; const int maxn = 1000; int a[maxn + 1][maxn + 1]; int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j]; // Tính tổng đường chéo chính của ma trận. int sum = 0; for (int i = 1; i <= n; ++i) sum += a[i][i]; cout << sum; return 0; }

Đoạn chương trình trên dùng để tính tổng các phần tử trên đường chéo chính của một ma trận vuông.

Về độ phức tạp thời gian, ta có thể thấy hai vòng lặp lồng nhau dùng để nhập ma trận là tốn nhiều thời gian thực thi nhất, vì vậy thời gian tổng quát của thuật toán là .

Về độ phức tạp bộ nhớ, ta thấy đoạn chương trình khai báo một mảng hai chiều kích thước còn lại đều là các biến đơn. Như vậy độ phức tạp bộ nhớ tổng quát là .

'Thần số học' Trương Mỹ Lan
‘Thần số học’ Trương Mỹ Lan

Phương pháp đánh giá bằng lý thuyết

Trong lập trình thi đấu, người ta sẽ đánh giá độ phức tạp thuật toán bằng phương pháp lý thuyết. Trong phương pháp này, ta quan tâm tới yêu tố kích thước của dữ liệu đầu vào, thông thường là một con số . Mối liên hệ giữa yếu tố này và số lượng các phép tính toán cũng như kích thước bộ nhớ lưu trữ để tìm ra được kết quả của bài toán gọi chung là độ phức tạp thuật toán (chứ không phải thời gian cụ thể như hay giây). Ta sử dụng hai hàm số và để biểu diễn thời gian thực hiện của thuật toán và không gian lưu trữ của thuật toán với dữ liệu đầu vào kích thước là .

Độ lớn của hàm được biểu diễn bằng một hàm với và là hai hàm số thực không âm. Nếu một thuật toán có thời gian thực hiện là thì ta nói thuật toán đó có thời gian thực hiện cấp . Nói một cách dễ hiểu, sẽ biểu diễn số phép tính tối đa cần thực hiện trong thuật toán với một bộ dữ liệu đầu vào cấp chẳng hạn trong bài toán kiểm tra tính nguyên tố của số nếu là số nguyên tố thì thuật toán sẽ phải thực hiện nhiều lần thử nhất.

Còn độ lớn của hàm cũng được biểu diễn bằng một hàm với và là hai hàm số thực không âm. Nếu một thuật toán tiêu tốn bộ nhớ thì ta nói thuật toán đó có không gian lưu trữ cấp . Một cách đơn giản hơn, sẽ biểu diễn tổng dung lượng bộ nhớ cần sử dụng trong thuật toán với một bộ dữ liệu đầu vào cấp . Trong bài toán kiểm tra tính nguyên tố của số mỗi biến khai báo ra đều đóng góp vào vì chúng đều tiêu tốn bộ nhớ của chương trình.

Keywords searched by users: khái niệm thuật toán

Lý Thuyết: Bài Toán Và Thuật Toán Trang 32 Sgk Tin Học 10 | Sgk Tin Học Lớp  10
Lý Thuyết: Bài Toán Và Thuật Toán Trang 32 Sgk Tin Học 10 | Sgk Tin Học Lớp 10
Tin Học 10 - Bài 4: Bài Toán Và Thuật Toán - Khái Niệm Thuật Toán - Youtube
Tin Học 10 – Bài 4: Bài Toán Và Thuật Toán – Khái Niệm Thuật Toán – Youtube
Code Learn
Code Learn
Thuật Toán Là Gì? Có Mấy Loại Thuật Toán?
Thuật Toán Là Gì? Có Mấy Loại Thuật Toán?
Thuật Toán Là Gì? Các Phương Pháp Biểu Diễn Thuật Toán
Thuật Toán Là Gì? Các Phương Pháp Biểu Diễn Thuật Toán
Lý Thuyết: Bài Toán Và Thuật Toán Trang 32 Sgk Tin Học 10 | Sgk Tin Học Lớp  10
Lý Thuyết: Bài Toán Và Thuật Toán Trang 32 Sgk Tin Học 10 | Sgk Tin Học Lớp 10
Code Learn
Code Learn
Chủ Đề: Bài Toán Và Thuật Toán
Chủ Đề: Bài Toán Và Thuật Toán
Lý Thuyết Tin Học 6 Kết Nối Tri Thức Bài 15: Thuật Toán
Lý Thuyết Tin Học 6 Kết Nối Tri Thức Bài 15: Thuật Toán
Tin Học 6 - Bài Khái Niệm Thuật Toán - Chủ Đề Giải Quyết Vấn Đề Với Sự Trợ  Giúp Của Máy Tính - Youtube
Tin Học 6 – Bài Khái Niệm Thuật Toán – Chủ Đề Giải Quyết Vấn Đề Với Sự Trợ Giúp Của Máy Tính – Youtube
Thuật Toán – Wikipedia Tiếng Việt
Thuật Toán – Wikipedia Tiếng Việt
Thuật Toán Là Gì? Tìm Hiểu Về Thuật Toán Trong Lập Trình
Thuật Toán Là Gì? Tìm Hiểu Về Thuật Toán Trong Lập Trình
Chủ Đề F - Bài 1: Khái Niệm Thuật Toán - Tin 6 - Bộ Sách Cánh Diều|Time -  Youtube
Chủ Đề F – Bài 1: Khái Niệm Thuật Toán – Tin 6 – Bộ Sách Cánh Diều|Time – Youtube
Bài 4: Bài Toán Và Thuật Toán - Hoc24
Bài 4: Bài Toán Và Thuật Toán – Hoc24
Câu 1: Khái Niệm Thuật Toán, Đầu Vào, Đầu Ra Của Thuật Toán; Hai Phương  Phápbiểudiễn Thuật Toán; Quy Ước Biểu Diễn Thuật Toán Bằng Sơ Đồ Khối; Lợi  Ích Khi
Câu 1: Khái Niệm Thuật Toán, Đầu Vào, Đầu Ra Của Thuật Toán; Hai Phương Phápbiểudiễn Thuật Toán; Quy Ước Biểu Diễn Thuật Toán Bằng Sơ Đồ Khối; Lợi Ích Khi
Chủ Đề F Bài 1. Khái Niệm Thuật Toán - Youtube
Chủ Đề F Bài 1. Khái Niệm Thuật Toán – Youtube
Lý Thuyết Mô Tả Thuật Toán, Cấu Trúc Tuần Tự Trong Thuật Toán Tin Học 6  Cánh Diều
Lý Thuyết Mô Tả Thuật Toán, Cấu Trúc Tuần Tự Trong Thuật Toán Tin Học 6 Cánh Diều
Tin Học 10 - Bài 4: Bài Toán Và Thuật Toán - Khái Niệm Thuật Toán - Youtube
Tin Học 10 – Bài 4: Bài Toán Và Thuật Toán – Khái Niệm Thuật Toán – Youtube
Thuật Toán – Wikipedia Tiếng Việt
Thuật Toán – Wikipedia Tiếng Việt
Cấu Trúc Dữ Liệu Và Giải Thuật
Cấu Trúc Dữ Liệu Và Giải Thuật
Thuật Toán Là Gì? Tính Chất Thuật Toán Mà Lập Trình Viên Cần Biết
Thuật Toán Là Gì? Tính Chất Thuật Toán Mà Lập Trình Viên Cần Biết
Thuật Toán Bert: Khái Niệm, Hoạt Động Và Cách Tối Ưu Website
Thuật Toán Bert: Khái Niệm, Hoạt Động Và Cách Tối Ưu Website
4. Khái Niệm Về Big O Trong Thuật Toán. - Youtube
4. Khái Niệm Về Big O Trong Thuật Toán. – Youtube
Lý Thuyết: Bài Toán Và Thuật Toán Trang 32 Sgk Tin Học 10 | Sgk Tin Học Lớp  10
Lý Thuyết: Bài Toán Và Thuật Toán Trang 32 Sgk Tin Học 10 | Sgk Tin Học Lớp 10
Cập Nhật Nhanh Chóng Các Thuật Toán Của Google Mới Nhất 2024
Cập Nhật Nhanh Chóng Các Thuật Toán Của Google Mới Nhất 2024
Tin Học Lớp 6 Bài 1 Chủ Đề F | Khái Niệm Thuật Toán | Trang 80 – 82 | Cánh  Diều - Youtube
Tin Học Lớp 6 Bài 1 Chủ Đề F | Khái Niệm Thuật Toán | Trang 80 – 82 | Cánh Diều – Youtube
10 Thuật Toán Google Phải Hiểu Để Tăng Trưởng Ranking 2022 | Bởi Doãn Kiên  | Brands Vietnam
10 Thuật Toán Google Phải Hiểu Để Tăng Trưởng Ranking 2022 | Bởi Doãn Kiên | Brands Vietnam
Giải Sgk Tin Học 6 Bài 1 (Cánh Diều): Khái Niệm Thuật Toán
Giải Sgk Tin Học 6 Bài 1 (Cánh Diều): Khái Niệm Thuật Toán

See more here: kientrucannam.vn

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *