10 thuật toán cơ bản thống trị khoa học thế giới

Ngày đăng: 2014-08-23
Tình cờ khi đang trên đường tới Reddit, Tôi tìm thấy một bài viết thú vị mà người ta gọi đó là 10 thuật toán thống trị thế giới của chúng ta của tác giả George Dvorsky. Tác giả đã giải thích tầm quan trọng của các thuật toán đó với thế giới ngày nay.

Bây giờ nếu bạn đã nghiên cứu các thuật toán điều đầu tiên mà có thể đến để tâm trí của bạn trong khi đọc bài viết này là "Có phải tác giả biết một thuật toán là gì không?" Hoặc có thể "nguồn tin Facebook là một thuật toán không?" Bởi vì nếu nguồn cấp dữ liệu tin tức Facebook là một thuật toán  thì hầu như bạn có thể phân loại gần như tất cả mọi thứ là một thuật toán. Vì vậy, tôi sẽ cố gắng giải thích những gì trong bài viết này là một thuật toán và đó là những thuật toán thực tế 10 (hoặc có thể hơn) mà thống trị thế giới của chúng ta.

Một thuật toán  gì?
    
Thông thường, một thuật toán bất kỳ thủ tục tính toán được xác định rõ rằng phải mất một số giá trị, hoặc thiết lập các giá trị, như đầu vào và sản xuất một số giá trị, hoặc thiết lập các giá trị, như  đầu ra.

Do đó một thuật toán là một chuỗi các bước tính toán để biến đổi đầu vào đầu ra. (Thomas H. Cormen, Chales E. Leiserson (2009))

 

Trong thuật ngữ đơn giản, có thể nói rằng một thuật toán là một chuỗi các bước cho phép để giải quyết một công việc nhất định (Vâng, không chỉ các máy tính sử dụng các thuật toán, con người cũng sử dụng chúng). Bây giờ, một thuật toán cần phải có ba đặc điểm quan trọng để được coi là hợp lệ:

  Nó phải là hữu hạn: Nếu thuật toán của bạn không bao giờ  cố gắng kết thúc  để giải quyết vấn đề nó được thiết kế để giải quyết
thì nó sẽ là vô ích

nên được hướng dẫn rõ ràng:  Mỗi bước của thuật toán phải được xác định một cách chính xác; các hướng dẫn rõ ràng nên được quy định cho từng trường hợp.
phải hiệu quả: Các thuật toán cần giải quyết vấn đề nó được thiết kế để giải quyết. chúng ta có thể chứng minh rằng các thuật toán hội tụ chỉ với một giấy và bút chì.

Ngoài ra, điều quan trọng chỉ ra rằng thuật toán không chỉ được sử dụng trong Khoa học máy tính mà còn là một thực thể toán học. Trong thực tế, thuật toán toán học đầu tiên được ghi mà chúng ta có ngày từ 1600 TCN - Babylon phát triển các thuật toán sớm nhất được biết đến với nhân tử hóa và tìm căn bậc hai. Vì vậy, ở đây chúng tôi có vấn đề đầu tiên với bài viết đã đề cập trước, nó xử lý các thuật toán như các đơn vị tính toán, nhưng nếu bạn ý nghĩa chính thức của từ thực top 10 thuật toán thống trị thế giới có thể được tìm thấy trong một cuốn sách về số học (cộng, trừ, nhân, vv).

Tuy nhiên, cho phép máy tính thuật toán như định nghĩa của chúng ta về thuật toán
trong bài viết này, vì vậy câu hỏi vẫn còn đó:  10 thuật toán nào thống trị thế giới? Ở đây tôi đã đặt cùng một danh sách nhỏ, không theo thứ tự cụ thể.      

1. Merge Sort, Quick Sort and Heap Sort

Các thuật toán tốt nhất để sắp xếp các yếu tố là gì? Nó phụ thuộc vào những gì bạn cần, và đó là lý do tại sao tôi đặt thường xuyên thêm việc sử dụng 3 thuật toán sắp xếp trong cùng một vị trí; có thể bạn có một sở thích cho một, nhưng tất cả chúng đều quan trọng như nhau.


Thuật toán trộn là một trong những thuật toán quan trọng nhất của ngày nay. Đây là một thuật toán sắp xếp so sánh dựa trên sử dụng phương pháp chia để trị để giải quyết một vấn đề đã từng là một O (n ^ 2). Nó được phát minh bởi nhà toán học John von Neumann vào năm 1945.

Sắp xếp nhanh một cách tiếp cận khác nhau cho vấn đề phân loại, nó có thể sử dụng tại chỗ các thuật toán phân vùng và là một thuật toán chia để trị như đã từng. Vấn đề với thuật toán này
là nó không phải là một loại ổn định nhưng thực sự hiệu quả để phân loại các mảng bộ nhớ RAM.

Cuối cùng, thuật toán
Heap sử dụng một hàng đợi ưu tiên làm giảm thời gian tìm kiếm trong dữ liệu. Thuật toán này cũng là một thuật toán tại chỗ và không phải là loại ổn định.

Các thuật toán này là một cải tiến lớn so với các phương pháp khác trước đây được sử dụng như sắp xếp
nổi bọt, trên thực tế, đó là nhờ họ mà ngày nay chúng ta dữ liệu khai thác, trí tuệ nhân tạo, phân tích liên kết và hầu hết các công cụ máy tính trên thế giới bao gồm cả các trang web.

2. Fourier Transform and Fast Fourier Transform

Toàn bộ thế giới kỹ thuật số của chúng ta sử dụng các thuật toán đơn giản nhưng thực sự mạnh mẽ, chuyển đổi tín hiệu từ miền thời gian của họ vào miền tần số của họ và ngược lại. Trong thực tế, bạn đang nhìn thấy bài này nhờ vào các thuật toán đó.

Internet, WiFi, điện thoại thông minh, điện thoại, máy tính, router, vệ tinh, gần như tất cả mọi thứ của bạn có bên trong
một máy tính đều sử dụng các thuật toán trong cách này hay cách khác để tiến hành. Bạn không thể có được một trình độ trong thiết bị điện tử, máy tính hoặc viễn thông mà không nghiên cứu các thuật toán quan trọng.

3. Dijkstra’s algorithm

Nó không phải là điên rồ khi nói rằng Internet sẽ không làm việc một cách hiệu quả như nó nếu không phải là thuật toán này. Thuật toán tìm kiếm đồ thị này được sử dụng trong các ứng dụng khác nhau nơi mà vấn đề có thể được mô hình hóa như một đồ thị và bạn phải tìm đường đi ngắn nhất giữa hai nút.

Hôm nay, ngay cả khi chúng ta có giải pháp tốt hơn cho vấn đề của việc tìm kiếm đường đi ngắn nhất, thuật toán Dijkstra vẫn được sử dụng trong các hệ thống đòi hỏi phải có sự ổn định.

4. RSA algorithm

Internet sẽ không quan trọng như ngày nay nếu không cho mật mã an ninh mạng. Bạn có thể nghĩ rằng "Chắc chắn, an ninh trong thời đại của NSA cơ quan tình báo khác" hoặc "Bạn đã thực sự ngây thơ khi nghĩ rằng bạn đang an toàn trên Internet"; nhưng, mọi người cần phải cảm thấy rằng họ được an toàn để tiêu tiền. Sau khi tất cả, bạn sẽ không nhập số thẻ tín dụng của bạn trên một dịch vụ web nếu bạn biết điều đó  không an toàn.

Và từ lĩnh vực mật mã một thuật toán mà vẫn là một trong những
thuật toán quan trọng nhất trên thế giới: các thuật toán RSA. Được phát triển bởi những người sáng lập của công ty RSA, thuật toán này được thực hiện mật mã có sẵn cho tất cả mọi người trên thế giới và giúp hình thành như thế nào mật mã làm việc ngày hôm nay. Các thuật toán RSA là một giải pháp cho một vấn đề đơn giản nhưng phức tạp: làm thế nào để chia sẻ khóa công khai giữa các nền tảng độc lập và người sử dụng cuối cùng, để cho phép mật mã (Tôi cho rằng nó đã không được giải quyết hoàn toàn, tôi nghĩ rằng chúng ta cần phải làm việc nhiều hơn trong hướng này).

5. Secure Hash Algorithm

Đây không phải là một thuật toán mà là một liên quan của hàm băm  mật mã  đã được phát triển bởi NIST ở Mỹ. Nhưng gia đình của các thuật toán này là nền tảng cho hoạt động của thế giới. Từ cửa hàng của bạn ứng dụng, email của bạn, chống virus của bạn, trình duyệt của bạn, vv, tất cả trong số họ sử dụng các thuật toán (trong thực tế băm là kết quả của chúng) để xác định xem bạn đã tải về những gì bạn muốn, hoặc nếu bạn đã là nạn nhân của một người đàn ông trong cuộc tấn công trung bình hoặc có thể là một cuộc tấn công lừa đảo.

6. Integer factorization

Đây là một thuật toán toán học được sử dụng nhiều trong lĩnh vực máy tính. Nếu không có thuật toán này, mật mã sẽ được nhiều hơn nữa không an toàn. Thuật toán là một loạt các bước sử dụng để có được sự thừa số của một số tổng hợp vào ước không tầm thường nhỏ hơn. Đây được xem là một vấn đề FNP, đó là một phần mở rộng của Vườn quốc gia lớp học làm cho vấn đề thực sự khó khăn để giải quyết.

Nhiều giao thức mã hoá dựa trên những khó khăn của bao thanh toán số nguyên tổng hợp lớn hay một vấn đề ví dụ liên quan, vấn đề RSA. Một thuật toán có hiệu quả các yếu tố một số nguyên tùy ý sẽ làm cho RSA dựa trên khóa công khai mật mã không an
 toàn.

Sự ra đời của máy tính lượng tử là làm cho nó dễ dàng hơn để giải quyết vấn đề này, mở ra một lĩnh vực hoàn toàn mới, sử dụng tài sản của thế giới lượng tử để làm cho hệ thống an toàn.

7. Link Analysis

Trong thời đại của Internet, việc phân tích các mối quan hệ giữa các thực thể khác nhau là rất quan trọng.

Từ các công cụ tìm kiếm và mạng xã hội để tiếp thị công cụ phân tích, tất cả mọi người đang cố gắng để tìm thấy những cấu trúc thực sự của Internet thông qua thời gian.
Phân tích liên kết được cho là một trong những thuật toán với hầu hết những huyền thoại sự nhầm lẫn trong công chúng.

 Vấn đề là có những cách khác nhau để làm phân tích liên kết và đó cũng là những đặc điểm mà làm cho mỗi thuật toán một chút khác nhau (cho phép cấp bằng sáng chế các thuật toán) nhưng trong các căn cứ của họ, họ là tương tự.
Ý tưởng đằng sau liên kết phân tích rất đơn giản, bạn có thể đại diện cho một đồ thị trong một hình thức ma trận làm cho nó một vấn đề giá trị riêng.

Giá trị riêng này có thể cung cấp cho bạn một cách tiếp cận thực sự tốt về cấu trúc của đồ thị và tầm quan trọng tương đối của mỗi nút. Các thuật toán đã được phát triển vào năm 1976 bởi Gabriel Pinski và Francis Narin.

Người sử dụng thuật toán này? Google Page Rank của nó, Facebook khi nó cho bạn thấy nguồn tin của bạn (đây là lý do tại sao nguồn tin Facebook không phải là một thuật toán nhưng kết quả của một), Google+ và Facebook gợi ý bạn, đề nghị LinkedIn cho công việc địa chỉ liên lạc, Netflix và Hulu cho phim, YouTube cho video
.

Mỗi người có một số mục tiêu khác nhau khác nhau, nhưng toán học đằng sau mỗi vẫn giữ nguyên.

Cuối cùng, tôi muốn nói rằng thậm chí còn nghĩ nó có vẻ như Google là công ty đầu tiên làm việc với các loại thuật toán, vào năm 1996 (hai năm trước khi Google) một công cụ tìm kiếm nhỏ gọi là "RankDex", được thành lập bởi Robin Li, đã sử dụng ý tưởng này để xếp hạng trang. Cuối cùng Massimo Marchiori, người sáng lập "HyperSearch", sử dụng một thuật toán xếp hạng trang dựa trên các mối quan hệ giữa các trang duy nhất. (Hai nhà sáng lập được đề cập trong bằng sáng chế của Google)

8. Proportional Integral Derivative Algorithm

Bạn đã từng sử dụng một chiếc máy bay, ô tô, một dịch vụ truyền hình vệ tinh hoặc một mạng điện thoại di động? Bạn đã bao giờ được trong một nhà máy hoặc nhìn thấy một robot? Nếu vậy, sau đó bạn đã thấy thuật toán này trong hành động.

Về cơ bản, thuật toán này sử dụng một cơ chế phản hồi điều khiển vòng lặp để giảm thiểu sai số giữa tín hiệu đầu ra mong muốn và tín hiệu đầu ra thực tế. Nó được sử dụng bất cứ nơi nào bạn cần xử lý tín hiệu hoặc bạn cần một hệ thống điện tử kiểm soát một hệ thống cơ khí, thủy lực hoặc nhiệt sử dụng tự động hóa.

Bạn có thể nói rằng nếu không có thuật toán này nền văn minh hiện đại của chúng tôi sẽ không tồn tại.

9. Data compression algorithms

d
Nơi bạn có thể tìm thấy chúng, ngoài các tài liệu nén rõ ràng? Trang web này sử dụng nén dữ liệu sẽ được tải về vào máy tính của bạn, trong các trò chơi video, video, âm nhạc, lưu trữ dữ liệu, điện toán đám mây, cơ sở dữ liệu, vv Bạn có thể nói rằng tất cả mọi thứ sử dụng thuật toán nén dữ liệu; họ giúp làm cho các hệ thống rẻ hơn và hiệu quả hơn.

10. Random Number Generation

Hôm nay chúng ta không có một máy phát điện số ngẫu nhiên thật, nhưng chúng tôi có một số máy phát điện số giả ngẫu nhiên là đủ. Chúng được sử dụng trong một số lượng lớn các ứng dụng, từ kết nối trao đổi link, mật mã, thuật toán băm an toàn, trò chơi video, trí tuệ nhân tạo, tối ưu hóa, điều kiện ban đầu cho các vấn đề, tài chính, vv

Cuối cùng tôi chỉ muốn thêm rằng danh sách này nên được thực hiện như một ý kiến, không phải là một danh sách đầy đủ, bởi vì có một số thuật toán trong các lĩnh vực như máy học tập, nhân ma trận, phân loại, vv, mà rất quan trọng trong thế giới của chúng tôi và không được đề cập ở đây
.

Dịch theo medium.com

.

Loading...

Bài giảng nổi bật

Loading...