Trong toán học, khoa học máy tính và các học thuyết liên quan khác, thuật toán được định nghĩa là một tập hợp các giới luật được thiết lập và rõ ràng, được tìm thấy một cách có phương pháp và theo một cách hạn chế cho phép thực hiện các phép tính, xử lý thông tin nhất định, cung cấp giải pháp cho các vấn đề và thực hiện các hoạt động khác nhau. Khi bạn bắt đầu từ trạng thái ban đầu và một mục nhập, tuân theo các thủ tục bắt buộc, bạn sẽ đạt đến trạng thái cuối cùng và thu được kết quả. Thuật toán là đối tượng nghiên cứu của thuật toán và mặc dù nhiều người có thể không tin nhưng chúng cũng có thể được sử dụng trong mọi khía cạnh của cuộc sống hàng ngày.
Một thuật toán là gì
Mục lục
Trong máy tính, nó thường được định nghĩa là một chuỗi các lệnh tuần tự, trong đó một số quá trình được thực hiện để đáp ứng các quyết định hoặc nhu cầu nhất định. Theo cách tương tự, các thuật toán thường xuyên được sử dụng trong logic và toán học, cũng như là nền tảng cho việc phát triển các hướng dẫn sử dụng, sách mỏng minh họa, v.v. Một trong những điểm nổi bật nhất trong toán học là phương pháp do nhà hình học Euclides, để đạt được ước số chung lớn nhất của hai số nguyên dương và "phương pháp Gaussian" nổi tiếng để xác định hệ phương trình tuyến tính.
Liên quan đến khoa học máy tính, phép tính này có thể được gọi là trình tự các hướng dẫn cần tuân theo để xác định một vấn đề thông qua việc sử dụng máy tính.
Do đó, thuật toán được hiểu là ngành học tập trung vào việc phân tích và thiết kế các thuật toán. Xét cách thứ nhất, nó tìm cách kiểm tra các tính chất như tính đúng đắn và hiệu quả của nó đối với thời gian và không gian, để hiểu các vấn đề có thể được giải quyết theo thuật toán. Đối với thứ hai, nó tìm cách nghiên cứu các mô hình đã được thiết lập và đề xuất các ví dụ mới.
Thuật toán nằm ở trung tâm của tiến trình tính toán và quan trọng trong các lĩnh vực khác nhau của nó. Theo cách này, các dịch vụ thành công như Facebook và Google sẽ không thể xử lý lượng thông tin mà họ có nếu không có sự hợp tác của các thuật toán hoặc cấu trúc dữ liệu chuyên biệt. Tuy nhiên, trong cuộc sống hàng ngày, các thuật toán cũng được sử dụng, một ví dụ về trường hợp này là sự đánh lửa của bếp, vì nó bắt đầu vào thời điểm người đó vào bếp, quan sát nó và kết thúc, khi nó tiến hành đốt lửa..
Đặc điểm của một thuật toán
Mặc dù thuật toán được gọi là tập hợp có thứ tự và hữu hạn của các bước khác nhau dẫn đến giải quyết một vấn đề, nhưng người ta nói rằng bản chất của những khó khăn này thay đổi tùy theo bối cảnh mà chúng được tìm thấy, theo cách này, có những vấn đề hóa học, toán học, triết học, trong số những người khác. Như vậy có thể nói bản chất của nó rất đa dạng và việc thực hiện bằng máy tính là không cần thiết. Ngoài mọi thứ được giải thích trước đây, các thuật toán có những đặc điểm cơ bản để xác định chúng là gì ngày nay và sẽ được đề cập bên dưới.
- Các hướng dẫn có trong một thuật toán phải cụ thể để tránh tạo chỗ cho bất kỳ loại nhầm lẫn nào, điều này có nghĩa là các hướng dẫn tương ứng phải được tuân theo một cách thích hợp hoặc ngược lại, biểu diễn đồ họa của luồng mà bạn đang đăng ký sẽ không tạo điều kiện cho giải pháp. chính xác.
- Nó phải được định nghĩa hoàn hảo, cố gắng làm theo nó nhiều lần nhất có thể để thu được cùng một kết quả và trong trường hợp điều ngược lại xảy ra, thuật toán sẽ không đáng tin cậy và sẽ không đóng vai trò là hướng dẫn khi đưa ra quyết định.
- Chúng được biết đến với đặc thù là hữu hạn, chúng thường kết thúc vào một thời điểm nào đó và sau đó chúng sẽ đưa ra một kết quả ở cuối mỗi bước. Nếu thuật toán kéo dài vô hạn, quay trở lại điểm ban đầu nào đó mà không bao giờ có thể giải quyết được, thì sẽ có sự hiện diện của một nghịch lý hoặc “vòng lặp” lặp lại nổi tiếng.
- Cuối cùng, người ta nói rằng khả năng đọc của các thuật toán là yếu tố then chốt, bởi vì nếu đối số của nó là không thể hiểu được, thì không thể tuân theo các hướng dẫn tương ứng, thêm vào đó, nó đòi hỏi phải diễn đạt trực tiếp, rõ ràng và dễ hiểu của văn bản được tìm thấy trong mỗi thuật toán.
Các phần của thuật toán
Mọi hoạt động thuật toán có ba phần khác nhau tuân theo cấu trúc cơ bản của hệ thống và đó là:
- Đầu vào: còn được gọi là tiêu đề hoặc điểm bắt đầu, nó là hướng dẫn ban đầu đại diện cho nguồn gốc của thuật toán và là động lực thúc đẩy việc đọc của nó.
- Quy trình: còn được gọi là khai báo, nó là sự xây dựng chính xác được cung cấp bởi thuật toán và về cơ bản nó là trung kế của các khóa của nó để tạo ra các lệnh.
- Đầu ra: trong giai đoạn cuối cùng này là các lệnh cụ thể được xác định bởi thuật toán, ví dụ, các lệnh hoặc độ phân giải của nó.
Ví dụ về thuật toán
Các ví dụ phổ biến của phép tính toán học bao gồm 2 + 3 = 5 cho phép cộng và 15-9 = 6 cho phép trừ. Một cách khác để hình dung các thuật toán đơn giản là trong các công thức nấu ăn trong nhà bếp, vì chúng mô tả một quy trình cụ thể và có trật tự, ví dụ: “trước tiên bạn phải đặt một nửa nồi nước để đun nóng, sau đó bạn phải thêm một chút muối và cuối cùng hạt tiêu sẽ được chia để lấy hạt và dây thần kinh ”. Trong mô hình này, phần đầu, quá trình và phần kết thúc được trình bày, về cơ bản là những gì xác định các thuật toán.
Các loại thuật toán
Trong số các loại thuật toán khác nhau hiện có trên khắp thế giới, người ta nhấn mạnh vào những thuật toán được phân loại theo hệ thống dấu hiệu và những thuật toán khác theo chức năng của chúng. Thuật toán về cơ bản là giải pháp tốt nhất được biết đến để giải quyết bất kỳ vấn đề cụ thể nào và theo các chiến lược và chức năng của nó, có các loại khác nhau, trong số đó là động, ngược, bạo lực, cơ hội, đánh dấu, ngẫu nhiên, v.v. Ngoài các thuật toán nói trên, có hàng ngàn thuật toán trong số này phù hợp để giải quyết các khó khăn trong bất kỳ lĩnh vực nào.
Theo hệ thống dấu hiệu của bạn
Định tính và định lượng nằm trong danh mục này.
- Các thuật toán định tính được đặc trưng bởi có các yếu tố bằng lời nói, ví dụ trong số này là các hướng dẫn hoặc "từng bước" được công nhận được truyền miệng, chẳng hạn như công thức nấu ăn hoặc quy trình thực hiện công việc thủ công.
- Các thuật toán định lượng hoàn toàn trái ngược với các thuật toán định tính, do sự hiện diện của các yếu tố số nhất định và việc sử dụng toán học để thực hiện các phép tính, ví dụ, khi tìm thấy căn bậc hai hoặc các phương trình được giải.
Trong phân loại này cũng có các thuật toán tính toán và không tính toán. Các thuật toán tính toán được thực hiện bằng máy tính và có đặc điểm là phức tạp đến mức yêu cầu máy móc phải thực hiện, ngoài ra, chúng là các thuật toán định lượng có thể được tối ưu hóa. Những cái không tính toán không có nghĩa vụ phải được thực hiện bằng máy hoặc máy tính; một ví dụ rõ ràng về điều này là chương trình truyền hình.
Theo chức năng của nó
Những điều sau đây nằm trong phân loại này.
1. Thuật toán đánh dấu
Điều này được đặc trưng bởi việc sử dụng tự động hóa để đặt giá một cách thận trọng, tập trung vào các yếu tố như hành vi của người dùng và còn được gọi là khả năng tự động xác định giá để giảm giá các thành phần nhằm tăng lợi nhuận của người dùng. người bán hàng. Nó đã đóng một vai trò rất quan trọng trong việc thực hiện chung của hãng hàng không ngành công nghiệp kể từ đầu những năm 1990.
Thuật toán đánh dấu được phân biệt bởi là một trong những thực tiễn phổ biến nhất trong các ngành có tính cạnh tranh cao, đề cập đến các đại lý du lịch hoặc các cơ sở trực tuyến đó. Loại thuật toán này có thể trở nên cực kỳ phức tạp hoặc tương đối đơn giản, vì trong nhiều trường hợp, người ta lưu ý rằng chúng được tối ưu hóa hoặc tự học với tính liên tục của các bài kiểm tra nhất định. Ngoài tất cả những điều đó, các thuật toán gắn thẻ cũng có thể trở nên không phổ biến với khách hàng vì các cá nhân có xu hướng coi trọng cả sự ổn định và công bằng.
2. Các thuật toán xác suất
Chúng là những thuật toán mà cách mà kết quả thu được phụ thuộc vào xác suất, chúng thường được gọi là thuật toán ngẫu nhiên.
Trong một số ứng dụng, việc xử lý loại hoạt động này là phổ biến, ví dụ, khi hành vi của bất kỳ hệ thống hiện có hoặc được phát minh ra được mô phỏng theo thời gian, trong đó kết quả là một giải pháp tình cờ. Trong các trường hợp khác, vấn đề cần giải quyết thường là xác định, nhưng có khả năng biến nó thành một vấn đề ngẫu nhiên, để giải quyết nó bằng cách áp dụng thuật toán xác suất. Điều tích cực của những cái ngẫu nhiên là ứng dụng của chúng không đòi hỏi những nghiên cứu toán học quá phức tạp.
Ngoài ra, trong nhóm này có ba loại chính được gọi là số, Monte Carlo và Las Vegas.
- Thuật toán số có thể cung cấp kết quả gần đúng của bài toán và thường được áp dụng trong kỹ thuật.
- Các thuật toán Monte Carlo có thể đưa ra giải pháp đúng hoặc sai và có một biên độ sai số nhất định và cuối cùng.
- Các thuật toán Las Vegas được phân biệt bằng cách không bao giờ để lại một câu trả lời sai, trên thực tế, chúng tìm ra giải pháp chính xác hoặc chỉ đơn giản là thông báo cho bạn về sự thất bại có thể xảy ra.
Lập trình động đề cập đến phương pháp mà thuật toán tính toán kết quả. Đôi khi giải pháp của một số yếu tố có vấn đề phụ thuộc vào kết quả của các vấn đề nhỏ hơn khác. Vì vậy, để giải các bài toán này, các giá trị giống nhau phải được tính toán lại để giải các bài toán con nhỏ nhất, tuy nhiên, điều này có thể tạo ra sự lãng phí các chu trình. Để khắc phục điều này, có thể sử dụng lập trình động và trong trường hợp này, giải pháp của mỗi bài toán con được ghi nhớ, sử dụng cùng một giá trị này thay vì lặp lại nhiều lần.
3. Các thuật toán heuristic
Chúng được phân biệt bằng cách tìm lời giải và thậm chí vì vậy chúng không đảm bảo rằng câu trả lời đúng nhất sẽ được tìm thấy, vì lý do này, chúng có thể được coi là thuật toán gần đúng. Chúng có thể được sử dụng khi việc tìm kiếm một giải pháp thông qua một con đường bình thường được coi là không thể. Heuristics cung cấp các cách sử dụng sẽ được giải thích bên dưới. Trong lập kế hoạch, chúng được sử dụng để lập lịch trình các hoạt động trong một khoảng thời gian ngắn, trong thiết kế, chúng được sử dụng để phác thảo các hệ thống điện hoặc kỹ thuật số và trong mô phỏng, chúng được sử dụng để xác minh các quy trình nhất định.
4. Thuật toán quay lui
Chúng được gọi là chiến lược đệ quy giải quyết các vấn đề như câu đố, mê cung hoặc các mảnh tương tự, trong đó tìm kiếm sâu được thực hiện để tìm ra giải pháp khả thi. Tên của nó đề cập đến thực tế là trong các yêu cầu được thực hiện để tìm ra kết quả, nó luôn quay trở lại điểm trước đó để có thể kiểm tra các lựa chọn thay thế. Chúng thường được thu hồi để quan sát tác động của chúng đối với nền kinh tế, đối với thị trường, đối với việc định giá, đối với một số hoạt động nhất định và thậm chí đối với bản thân xã hội.
5. Thuật toán tham lam
Nó được gọi là kẻ hủy diệt hoặc chiếc răng ngọt ngào và được áp dụng trong các bài toán tối ưu hóa, trong mỗi bước của thuật toán này, một lựa chọn hợp lý và tối ưu được thực hiện để đưa ra giải pháp tốt nhất trong số các giải pháp toàn cầu. Tuy nhiên, cần phải tính đến rằng một khi đã nhận định, tuyệt đối không thể làm gì để sửa chữa hoặc thay đổi nó trong tương lai. Phép toán này có tên này bởi vì trong mỗi bước, phần tốt nhất có thể "nuốt" được chọn mà không cần lo lắng về những gì xảy ra sau đó.
Thuộc tính của một thuật toán
Nhiều tác giả khác nhau đã cố gắng xác định các thuật toán một cách chính thức trong khi sử dụng các mô hình toán học. Tuy nhiên, những mẫu vật này có liên quan chặt chẽ đến một loại thông tin đặc biệt bao gồm số, ký hiệu và một số biểu đồ, đồng thời hoạt động trên một lượng lớn dữ liệu phân phối. Nói chung, phần chung của mỗi định nghĩa được tóm tắt trong ba tính chất sau:
Báo cáo vấn đề
Giải quyết vấn đề bằng máy tính có thể bao gồm một quy trình trong đó một vấn đề được mô tả và một chương trình có khả năng giải quyết nó được phép phát triển. Quá trình này yêu cầu phân tích vấn đề, thiết kế một thuật toán và chuyển đổi nó thành một chương trình, cũng như việc thực hiện và xác nhận nó. Hai bước đầu tiên là phức tạp nhất trong quá trình này, nhưng khi bạn đã xem xét vấn đề và có được một thuật toán có thể giải quyết nó, nhiệm vụ của bạn chủ yếu là dịch nó sang ngôn ngữ lập trình mong muốn.
Phân tích giải pháp chung
Khi vấn đề được xác định, đã đến lúc phân tích những điều sau:
- Các thông tin của vé mà họ cung cấp cho chúng.
- Kết quả mong muốn.
- Lĩnh vực công việc, tuyên bố hoặc các yếu tố cần thiết khác.
Phân tích các thuật toán được coi là phần quan trọng nhất của lý thuyết độ phức tạp tính toán rộng hơn, vì nó cung cấp các tính toán lý thuyết cho các tài nguyên mà bất kỳ thuật toán nào yêu cầu để giải quyết một vấn đề tính toán nhất định. Khi thực hiện một khảo sát lý thuyết, người ta thường tính toán các biến chứng của nó theo nghĩa tiệm cận để có được kích thước đầu vào đủ lớn. Giới hạn trên của tiệm cận cùng với ký hiệu theta và omega được sử dụng cho mục đích này và cần lưu ý rằng số đo không tiệm cận có thể được tính toán.
Các thước đo chính xác về hiệu quả thực sự hữu ích đối với những người thực sự sử dụng các thuật toán, vì chúng có độ chính xác cao hơn và điều này cho phép họ xác định thời gian thực thi. Đối với một số cá nhân như người tạo trò chơi điện tử, hằng số ẩn có thể có nghĩa là sự khác biệt lớn giữa thành công và thất bại. Đánh giá thời gian có thể phụ thuộc vào cách xác định một bước nhất định và để việc phân tích có ý nghĩa, nó phải được đảm bảo rằng thời gian được giới hạn rõ rệt bởi một hằng số.
Xây dựng thuật toán
Để thực hiện việc phát triển một hoạt động, điều quan trọng là phải thực hiện một loạt các thủ tục để tuân thủ việc giải quyết một vấn đề. Để bắt đầu, một phân tích trước về độ khó phải được thực hiện và điều này được thực hiện thông qua một nghiên cứu chứng minh hoạt động thực sự của vấn đề rất lâu trước khi bất kỳ thuật toán nào được thực hiện. Do đó, định nghĩa các yêu cầu được đánh giá, trong bước này bạn phải có ý tưởng rõ ràng về vấn đề cần giải quyết, có thể là tổng của hai số, thứ tự của một danh sách các số, v.v.
Sau đó, việc xác định các mô-đun tương ứng được thực thi, vì việc triển khai chính xác các thuật toán phụ thuộc vào nó để cung cấp các giải pháp khả thi cho các yêu cầu đã xác định ở trên.
Cuối cùng, phép tính được thực hiện bằng một ngôn ngữ lập trình mà máy tính có thể hiểu được để máy tính có thể hiểu được các hướng dẫn mà nó mô hình hóa và do đó có thể thực hiện chúng, đạt được kết quả mong đợi. Trong thủ tục cuối cùng này, có thể nói về một chương trình bao gồm một loạt các lệnh được sắp xếp lần lượt và quản lý để giải quyết các yêu cầu đã thiết lập.
Điều quan trọng cần đề cập là trong thời gian tuần tự, các thuật toán thực hiện chức năng của chúng trong một khoảng thời gian tùy ý và tìm cách xác định trình tự các trạng thái tính toán trong mỗi đầu vào được coi là hợp lệ. Ở trạng thái trừu tượng, các phép toán này là các phần tử độc lập và người ta coi rằng trong đó các cấu trúc trật tự nguyên thủy có thể trở nên bất biến theo thuyết đẳng cấu. Trong thăm dò có giới hạn, quá trình chuyển đổi từ trạng thái này sang trạng thái khác được thiết lập đầy đủ bởi một giải thích vĩnh viễn và hữu hạn, trong đó giữa trạng thái này và trạng thái tiếp theo, chỉ tính đến một số thuật ngữ giới hạn ở trạng thái hiện tại.
Cũng không nên bỏ qua rằng các thuật toán thường được thể hiện thông qua ngôn ngữ lập trình "mã giả" ngôn ngữ thông thường và thậm chí cả các lưu đồ nổi tiếng. Tương tự như vậy, điều quan trọng cần đề cập là các thuật toán đóng một vai trò cơ bản trong tính toán do sự biểu diễn dữ liệu của chúng dưới dạng chuỗi các bit. Từ một góc độ khác, một chương trình được định nghĩa là thuật toán diễn đạt cho máy tính biết các bước cụ thể mà nó phải tuân theo để thực hiện đầy đủ các hoạt động nhất định. Mặt khác, học viết mã giả làm cho việc lập trình dễ dàng hơn và do đó sẽ được giải thích ở phần sau.
Ngôn ngữ lập trình được biết đến như một ngôn ngữ chính thức hoặc ngôn ngữ nhân tạo vì chúng có các quy tắc ngữ pháp được xác định rõ ràng, nó có khả năng cung cấp cho người lập trình khả năng văn bản hóa một loạt các hướng dẫn hoặc kế thừa các quy định dưới dạng thuật toán với mục đích để duy trì sự kiểm soát liên quan đến hành vi vật lý và logic của máy tính, bằng cách này, có thể tiếp cận các loại thông tin khác nhau. Tập hợp các giới luật này được viết bằng ngôn ngữ lập trình được chỉ định là một chương trình.
Ngôn ngữ lập trình thường được tạo thành từ một tập hợp các ký hiệu và các quy tắc ngữ pháp và ngữ nghĩa xác định các cấu trúc hiện tại của ngôn ngữ và ý nghĩa của chúng. Từ một góc độ khác, ngôn ngữ máy tính cũng bao gồm các ngôn ngữ lập trình, một ví dụ rõ ràng về điều này là HTML, là ngôn ngữ đáp ứng các chỉ dẫn nhất định để thực hiện nội dung của các tài liệu khác nhau. Ngôn ngữ lập trình có thể cho phép đặc tả chính xác những dữ liệu phải được vận hành bởi phần mềm cụ thể trong nhiều trường hợp.
Mặt khác, mã giả là ngôn ngữ mô tả thuật toán sử dụng các quy ước cơ bản của một ngôn ngữ lập trình thực, nhưng được thiết kế để con người đọc thay vì đọc thông qua máy, duy trì sự độc lập với bất kỳ loại ngôn ngữ lập trình. Mã giả bỏ qua các chi tiết không được coi là cần thiết đối với sự hiểu biết của con người về thuật toán, chẳng hạn như mã hệ thống, khai báo biến và thậm chí một số chương trình con. Bằng cách này, ngôn ngữ lập trình tìm cách tự bổ sung bằng các mô tả chính xác bằng ngôn ngữ tự nhiên hoặc với các ký hiệu toán học nhỏ gọn.
