10 thuật toán kỳ lạ, rực rỡ nhất từng được phát minh và chúng thực sự làm gì

Đã bao giờ cố gắng trích xuất một lưới đa góc từ một trường scalar 3D kín đáo? Không ? Vâng, vào năm 1987, hai lập trình viên tại General Electric đã làm – và cuối cùng họ đã phát minh ra thuật toán Marching Cubes. Đó là sức mạnh của một thuật toán. Một số thuật toán là nhanh chóng, một số là thanh lịch, và một số rất kỳ lạ, họ cảm thấy như phép thuật. Whenever you instruct a machine to solve a problem with code, you’re designing a procedure to transform bits into meaning Trong câu chuyện này, chúng ta đang đắm chìm trong mười thuật toán kỳ lạ nhất, rực rỡ nhất từng được phát minh - những thuật toán giúp tìm kiếm hàng tỷ dòng mã trong milliseconds, tạo ra các bản đồ vô hạn từ không có gì, và biến sự kỳ lạ lượng tử thành logic thực tế. Chương 1: Wave Function Collapse Một trong những điều kỳ lạ nhất trong khoa học là thí nghiệm cắt đôi: các hạt cư xử như sóng khi bạn không nhìn, nhưng ngay khi bạn quan sát chúng, chúng vấp ngã vào vị trí như các hạt. Ý tưởng này của một "chức năng sóng sụp đổ" nghe có vẻ trừu tượng, nhưng nó đã được biến thành một thuật toán thực tế đáng ngạc nhiên. Hãy tưởng tượng bạn đang thiết kế một bản đồ trò chơi video cuộn bên. Bạn muốn thế giới cảm thấy được thủ công nhưng cũng sẽ tiếp tục mãi mãi. Lúc đầu, mỗi tấm gạch trên bản đồ giống như một “cơn sóng” – nó chưa có gì cụ thể. Nó đầy khả năng. Nhưng khi người chơi di chuyển về phía trước – quan sát thế giới – thuật toán “sụp đổ” sự không chắc chắn đó. Thế giới trở thành một tấm gạch cụ thể, nhưng nó làm như vậy theo các quy tắc bạn đã thiết lập. Con đường kết nối, sông chảy nơi họ nên, và mọi thứ cảm thấy như nó được thiết kế một cách có chủ ý. Đó là sự ngẫu nhiên với một mục đích, tất cả mà không có một mảnh duy nhất của AI tạo ra. #2 Mô hình phân tán Thật kỳ lạ, thật kỳ lạ. Lấy các mô hình phân tán - công nghệ đằng sau các máy tạo hình ảnh như DALL·E và Stable Diffusion. chúng được dựa trên một ý tưởng từ nhiệt động học: phân tán, nơi các hạt tự nhiên lây lan từ các khu vực có nồng độ cao hơn đến các khu vực có nồng độ thấp hơn. Trong học máy, quá trình đó bị đảo ngược. Thay vì đi từ trật tự sang hỗn loạn, thuật toán bắt đầu với tiếng ồn thuần túy - giống như một hình ảnh của một con mèo - và học cách dần dần tinh chỉnh nó thành một hình ảnh có ý nghĩa. Nhưng bạn cần một mô hình để làm điều này tốt. thuật toán phân tán hoạt động trong hai giai đoạn. Đầu tiên, trong quá trình đào tạo, mô hình chụp hình ảnh thực tế và dần dần thêm tiếng ồn trong quá trình tiến tới cho đến khi chúng trở nên không thể nhận ra. Làm điều này trên hàng triệu hình ảnh được dán nhãn, và bạn có được một mô hình có thể mơ về những hình ảnh mới từ đầu. Mèo trong không gian. La Mã cổ đại theo phong cách Pixar. Ghế bơ siêu thực tế. Bạn đặt tên nó. Nó nặng về máy tính. Nhưng nó không dừng lại ở hình ảnh. Phân tán đã định hình lại cách chúng ta tạo ra âm nhạc, âm thanh, và tiếp theo - video. #3 – Mô phỏng Annealing Một trong những phần gây thất vọng nhất của lập trình là hiếm khi có một giải pháp đúng - chỉ có một biển những thứ tốt đẹp, và một vài thứ tuyệt vời. Simulated annealing mượn tên của nó từ kim loại, nơi kim loại được sưởi ấm và làm mát nhiều lần để loại bỏ các khiếm khuyết. cùng một khái niệm áp dụng cho tối ưu hóa. Bạn đang cố gắng tìm giải pháp tốt nhất trong một cảnh quan hỗn loạn đầy những đỉnh núi và thung lũng địa phương. Hãy tưởng tượng bạn đang tìm kiếm đỉnh cao nhất trong một dãy núi. Một thuật toán leo núi cơ bản sẽ khiến bạn bị mắc kẹt trên cú đấm đầu tiên có vẻ đầy hứa hẹn.Nhưng mô phỏng sương mù thông minh hơn. Nó bắt đầu với một "nhiệt độ" cao, có nghĩa là nó khám phá tự do - đôi khi thậm chí chấp nhận những con đường tồi tệ hơn để thoát khỏi những cái bẫy địa phương. Khi nhiệt độ dần giảm, nó trở nên nhạy cảm hơn, chỉ định cư vào những động tác tốt nhất. Sự thỏa hiệp là thám hiểm so với khai thác. Và nó không chỉ hữu ích trong mã – nó cũng là một ẩn dụ tốt cho việc học mã.Vào đầu, bạn nổi lên giữa các ngôn ngữ, công cụ và khuôn khổ.Nhưng cuối cùng, bạn làm mát, khóa và chuyên môn hóa. #4 Giấc ngủ Bạn không thể nói về các thuật toán mà không đưa ra sự sắp xếp - và có lẽ thông minh vô lý nhất (và hoàn toàn vô dụng) từng được phát minh là . ngủ đen Các thuật toán phân loại truyền thống, như hoặc , sử dụng các chiến lược chia và chinh phục để tái tạo các chuỗi thành subarrays và sắp xếp chúng một cách hiệu quả. nhưng ở đâu đó trên 4chan, một thiên tài điên rồ đã đề xuất một cách tiếp cận hoàn toàn khác. Quicksort MergeNội Đây là cách nó hoạt động: Đối với mỗi số trong mảng, bắt đầu một chủ đề mới. Mỗi chủ đề ngủ trong một số milliseconds bằng giá trị của nó, sau đó in số khi nó thức dậy.Bởi vì các số nhỏ hơn ngủ trong thời gian ngắn hơn, chúng được in sớm hơn - kết quả là một đầu ra được sắp xếp. Phần thông minh? Nó bỏ qua tất cả các logic thông thường và biến lập lịch dây của CPU thành công cụ sắp xếp. Không so sánh. Không tái phát. Chỉ cần ngủ và in. Nhưng nó là vô cùng không thực tế. Nó phá vỡ với số âm, trùng lặp, hoặc giá trị lớn. Nó cũng không hiệu quả, tạo ra một sợi mỗi số. Và nó phụ thuộc vào thời gian ngủ, mà không phải là rất chính xác. Sleep Sort là cả vui vẻ và vô dụng - một ví dụ hoàn hảo về cách thông minh không phải lúc nào cũng có nghĩa là hữu ích. #5 Thượng Đế BogoSort là một thuật toán đùa giỡn: nó ngẫu nhiên lắc một mảng một lần nữa và một lần nữa cho đến khi, bằng may mắn thuần túy, kết quả được sắp xếp. Bây giờ hãy tưởng tượng kết hợp điều này với ý tưởng về cơ học lượng tử và đa vũ trụ.Trong lý thuyết, nếu tất cả các kết quả có thể tồn tại trên vô số vũ trụ song song, thì có vũ trụ nơi mảng của bạn đã được sắp xếp. Một số Công nghệ này chưa có ở đó, nhưng một "Quantum BogoSort" sẽ hoạt động bằng cách tạo ra tất cả những khả năng đó cùng một lúc, và sau đó ngay lập tức sụp đổ vào vũ trụ nơi mảng được sắp xếp - về cơ bản cho phép ngẫu nhiên lượng tử làm việc cho bạn. Tất nhiên, đây là khoa học viễn tưởng, không phải khoa học máy tính.Chúng ta không thể quan sát hoặc sụp đổ đa vũ trụ theo ý muốn.Nhưng đó là một thí nghiệm suy nghĩ vui nhộn về sự ngẫu nhiên của lực lượng thô được đưa đến cực đoan logic (và vô lý). #6 - Đồ chơi Và đây là chương trình yêu thích của tôi. Điều tôi thấy thực sự tuyệt vời về các thuật toán là cách chúng đôi khi có thể phản ánh thiên nhiên.Lấy chương trình Boids của Craig Reynolds từ năm 1986 - đó là một trong những mô phỏng cuộc sống nhân tạo đầu tiên và nó bắt chước cách chim bầy. Sống như vậy Cảm nhận Mỗi con chim (hoặc "chim") chỉ tuân theo ba quy tắc: tránh va chạm với hàng xóm (Tách biệt), phù hợp với hướng đi của chúng (Hướng dẫn), và di chuyển về phía trung tâm của nhóm địa phương (Sự gắn kết). Không ai chịu trách nhiệm.Nhưng khi bạn mô phỏng một loạt các hành vi đơn giản này cùng nhau, bạn có được các mô hình hữu cơ quyến rũ thay đổi và chảy như một đàn thực sự. Vẻ đẹp ở đây không nằm trong mã - nó nằm trong những gì Những động lực nhóm phức tạp này không cần phải được lập trình rõ ràng.Họ chỉ đơn giản là xảy ra.Nó giống như đâm vào mã lừa đảo của thiên nhiên để phối hợp phi tập trung. xuất hiện #7 – Thuật toán của SHOR Ý tưởng cho phép mọi người khóa hộp thư của họ và ký thư của họ với một chữ ký duy nhất dựa trên một khái niệm quan trọng trong mã hóa: sự khó khăn của việc tính toán số lượng lớn. Sự an toàn đằng sau hầu hết các phương pháp mã hóa dựa trên thực tế toán học đơn giản này - nhân số lớn với nhau rất dễ dàng, nhưng tìm ra hai số nguyên gốc đằng sau sản phẩm Một vấn đề được biết đến như Nó cực kỳ khó khăn và tốn thời gian. — prime factorization — Trên thực tế, nó rất khó mà nó có thể mất hàng trăm nghìn tỷ năm để máy tính xách tay của bạn thực hiện một giải pháp - trừ khi, tất nhiên, chúng ta bắt đầu sử dụng máy tính lượng tử. máy tính lượng tử có tiềm năng để giải quyết vấn đề yếu tố hóa số nguyên theo cấp số nhân nhanh hơn bất kỳ thuật toán cổ điển nào, nhờ các thuật toán như thuật toán của Shor. Thuật toán của Shor có thể phá vỡ các số lớn thành các yếu tố chính của chúng nhanh hơn nhiều so với các phương pháp thông thường. tính toán chính là khá đơn giản, nhưng cách thuật toán này hoạt động là nơi mọi thứ trở nên thực sự kỳ lạ. Ở trung tâm của thuật toán Shor là các khái niệm cơ học lượng tử như qubits, siêu vị trí và tắc nghẽn. những điều này cho phép các máy tính lượng tử thực hiện các tính toán lớn song song, điều mà các máy tính cổ điển thậm chí không thể đến gần để làm. Trong khi bản thân thuật toán là hợp pháp, ứng dụng thế giới thực của nó vẫn còn trong giai đoạn đầu của nó. trên thực tế, số lớn nhất từng được tính bằng cách sử dụng máy tính lượng tử chỉ là 21. hệ thống lượng tử hiện đại của IBM, Q System One, không thể tính một số đơn giản như 35. Gần đây, một nhóm Trung Quốc đã quản lý để tính toán một số lớn bằng cách sử dụng một máy tính lượng tử, nhưng họ đã sử dụng một thuật toán không quy mô tốt cho số lớn hơn nhiều, có nghĩa là nó chưa thực tế cho sử dụng chung. Tuy nhiên, nếu máy tính lượng tử trở nên đủ mạnh mẽ và ai đó tìm ra cách mở rộng các thuật toán này cho số lượng thực sự lớn, hãy mong đợi sự gián đoạn nghiêm trọng trong thế giới an ninh mạng. # 8 - Đi bộ Cubes Vào đầu câu chuyện này, chúng tôi đã đề cập đến thuật toán Marching Cubes - nhưng nó đáng để lặn vào, bởi vì nó là một bước ngoặt lớn cho việc hình dung dữ liệu 3D, đặc biệt là trong y học. Hãy tưởng tượng bạn có một quét 3D của cơ thể con người, như từ một MRI. MRI không cung cấp cho bạn một mô hình 3D, nhưng một khối lượng khổng lồ của số - một trường quy mô 3D. Mỗi điểm trong lĩnh vực đó có một giá trị đại diện cho một cái gì đó như mật độ mô hoặc cường độ tín hiệu. dữ liệu này liên tục trong không gian, nhưng chúng ta cần biến nó thành một cái gì đó trực quan - một bề mặt, một hình dạng, một cái gì đó mà một máy tính có thể vẽ. Đây là nơi Marching Cubes đi vào. thuật toán lấy trường 3D này và di chuyển qua nó một khối nhỏ tại một thời điểm. mỗi khối được hình thành bởi tám điểm dữ liệu lân cận trong trường. Bây giờ đây là phần thông minh: mỗi điểm trong số tám điểm đó đều ở trên hoặc dưới ngưỡng (ví dụ, nơi da biến thành xương).Vì vậy, mỗi góc được gán 0 hoặc 1, tùy thuộc vào việc nó nằm bên trong hoặc bên ngoài bề mặt bạn đang cố gắng chiết xuất. Điều đó cung cấp cho bạn một số 8 bit - 256 kết hợp có thể cho mỗi khối nhỏ. Đối với mỗi kết hợp đó, một mô hình cụ thể của các tam giác đã được tính toán trước và lưu trữ trong một bảng tìm kiếm. Những tam giác này được sử dụng để ước lượng bề mặt đi qua khối đó. Vì vậy, thay vì tính toán hình học phức tạp mỗi lần, thuật toán chỉ nhìn nó lên. Bằng cách lặp lại quá trình này - di chuyển qua khối sau khối, kết nối các giá trị, tìm kiếm các hình dạng - thuật toán dần dần xây dựng một lưới 3D đầy đủ. Điều này đã mang tính đột phá vào những năm 1980 bởi vì nó đã biến các mảnh quét MRI hoặc CT phẳng thành các mô hình 3D thực tế mà các bác sĩ có thể xoay, phóng to và phân tích. # 9 - Thực hành Byzantine Fault Tolerance Trong máy tính hiện đại, chúng ta thường làm việc với các hệ thống phân tán - mạng lưới máy tính trải rộng trên đám mây.Điều đó đưa chúng ta đến một trong những vấn đề nổi tiếng nhất trong máy tính phân tán: Vấn đề Tổng thống Byzantine. Hãy tưởng tượng điều này: một số tướng lĩnh từ quân đội Byzantine đang bao vây một thành phố. Họ cần phải phối hợp và tấn công cùng một lúc để giành chiến thắng. Nhưng họ chỉ có thể giao tiếp bằng cách gửi tin nhắn, và một số tướng lĩnh đó có thể là những kẻ phản bội cố gắng phá hoại kế hoạch. Máy tính phải đối mặt với cùng một thách thức.Trong một hệ thống phân tán, một số máy có thể sụp đổ, chậm hoặc thậm chí bị hack.Làm thế nào để phần còn lại của mạng có thể đồng ý về những gì để làm khi họ không thể tin tưởng tất cả mọi người? Đó là nơi mà các thuật toán đồng thuận như PBFT – Practical Byzantine Fault Tolerance – đi vào. PBFT được thiết kế để xử lý các loại thất bại này. Nó hoạt động bằng cách có một nút đề xuất một hành động bằng cách phát một thông điệp “được chuẩn bị sẵn sàng”. Các nút khác đáp ứng với sự thừa nhận. Một khi một số nút nhất định (thường là hai phần ba hoặc nhiều hơn) đồng ý, họ đạt được sự đồng thuận. Cuối cùng, nút ban đầu gửi một thông điệp “ cam kết”, nói với mọi người để thực hiện hành động. Ngay cả khi đến một phần ba nút có lỗi hoặc độc hại, hệ thống vẫn có thể hoạt động đúng cách. Các thuật toán như PBFT là xương sống của các hệ thống blockchain và cơ sở dữ liệu đám mây phân tán, giúp chúng duy trì sự nhất quán và đáng tin cậy - ngay cả khi mọi thứ đi sai. Lời bài hát: Boyer Moore Và cuối cùng, điều đó đưa chúng ta đến một thuật toán trường học cũ mà lặng lẽ cung cấp một số công cụ nhanh nhất chúng ta sử dụng ngày nay - như grep. nó được gọi là tìm kiếm chuỗi Boyer-Moore, và gần đây nó bùng nổ tâm trí của tôi vì nó chống trực giác như thế nào: văn bản càng dài, Nó được nhanh hơn Hầu hết các thuật toán tìm kiếm cơ bản đều đi từ trái sang phải, kiểm tra từng ký tự từng ký tự một. bên trong mẫu tìm kiếm, và nó sử dụng hai thủ thuật thông minh để bỏ qua các mảnh văn bản lớn. “Trong một khối văn bản lớn. right to left “needle 1. Bad character rule: Vì vậy, thay vì kiểm tra nhân vật theo nhân vật, thuật toán nhảy về phía trước bằng 6 vị trí - chiều dài đầy đủ của "khăn" - và tiếp tục. 2. Good suffix rule: Nếu bạn đang tìm kiếm “dle” và bạn vừa kết hợp “dle” ở cuối – nhưng nhân vật tiếp theo phá vỡ trận đấu – thuật toán không bắt đầu lại từ chữ cái tiếp theo. Thay vào đó, nó hỏi: “dle” có xuất hiện sớm hơn trong “needle”? Nếu có, nó thay đổi mô hình để “dle” trước đó xếp hàng lên. Nếu không, nó bỏ qua toàn bộ phần “dle” hoàn toàn. Những chiến lược bỏ qua heuristic này không hoàn hảo, nhưng chúng hiệu quả hơn các phương pháp brute force. cách Kết quả? Khi văn bản trở nên dài hơn, thuật toán có xu hướng bỏ qua nhiều ký tự hơn, làm cho nó nhanh hơn so với kích thước của đầu vào. đó là lý do tại sao các công cụ như grep có thể nhai qua gigabyte nhật ký với tốc độ đáng ngạc nhiên - và tại sao thuật toán hàng thập kỷ này vẫn cảm thấy như ma thuật đen ngày nay. Khi logic gặp trí tưởng tượng: Sức mạnh thực sự của thuật toán Cho dù đó là chuyển sự không chắc chắn lượng tử thành việc tạo ra hình ảnh thực tế, bắt chước hành vi tập hợp sinh học với ba quy tắc đơn giản, hoặc tìm kiếm văn bản trở lại để tìm ra các mô hình nhanh hơn, những cách tiếp cận này cho thấy rằng những ý tưởng không thông thường nhất thường dẫn đến các giải pháp mạnh mẽ nhất. Những gì làm cho các thuật toán này rực rỡ không phải là hiệu quả hoặc sự mới mẻ của họ - đó là sự táo bạo của họ. Họ thách thức các giả định. Họ xoay các vấn đề trên đầu của họ. Họ biến sự ngẫu nhiên thành cấu trúc, hỗn loạn thành trật tự, và lý thuyết trừu tượng thành tác động thế giới thực. Nhiều hơn các công cụ toán học thanh lịch - 10 thuật toán kỳ lạ này . are a testament to human ingenuity Bạn muốn nghe từ tôi thường xuyên hơn? ✔️ ! Connect with me on LinkedIn Liên hệ với tôi trên LinkedIn Chia sẻ những hiểu biết, lời khuyên và cập nhật có thể thực hiện để giúp bạn tránh những sai lầm tốn kém và đi trước trong thế giới AI. hàng ngày Bạn là một chuyên gia công nghệ muốn phát triển khán giả của bạn thông qua việc viết? ✔️ ! Don’t miss my newsletter Đừng bỏ lỡ newsletter của tôi có đầy đủ các chiến lược copywriting và xây dựng khán giả có thể hành động đã giúp hàng trăm chuyên gia nổi bật và tăng tốc độ tăng trưởng của họ. Tech Audience Accelerator