Trình tạo tam giác Sierpinski

Trình tạo Tam giác Sierpinski vẽ fractal nổi tiếng nhất trong khoa học máy tính và toán học giải trí — ở bất kỳ độ sâu nào, từ bất kỳ tam giác bên ngoài nào, sử dụng thuật toán phân chia đệ quy xác định hoặc bước đi ngẫu nhiên của trò chơi hỗn loạn đầy bất ngờ. Chế độ song song vẽ cả hai cùng một lúc để bạn có thể thấy rằng sự ngẫu nhiên và đệ quy hội tụ về chính xác cùng một hình dạng. Công cụ này báo cáo số lượng lá, diện tích còn lại chính xác và chiều Hausdorff (log 3 / log 2 ≈ 1.5849625), đồng thời xuất tệp SVG sắc nét phù hợp cho các bài thuyết trình, trang tính hoặc cắt laser.

Cách xây dựng Tam giác Sierpinski — Từng bước một

Điều gì làm nên sự khác biệt của Trình tạo Sierpinski này

Tam giác Sierpinski là gì?

Tam giác Sierpinski (còn được gọi là đệm hoặc sàng Sierpinski) là một fractal tự đồng dạng được nhà toán học người Ba Lan Wacław Sierpiński mô tả chính thức lần đầu tiên vào năm 1915. Nó được xây dựng bằng cách loại bỏ đệ quy tam giác con đảo ngược ở trung tâm từ mỗi tam giác còn lại, để lại ba bản sao nhỏ hơn của hình gốc ở các góc. Quá trình này được lặp lại vô hạn; tập hợp giới hạn có độ đo bằng không (hoàn toàn không có diện tích) nhưng chứa vô số điểm không đếm được và có số chiều fractal không phải là số nguyên là log 3 / log 2 ≈ 1.5849625 — nghĩa là nó "béo" hơn một đường cong 1 chiều nhưng "gầy" hơn một vùng 2 chiều.

Trò chơi hỗn loạn: Trật tự từ sự ngẫu nhiên

Trò chơi hỗn loạn, được Michael Barnsley phổ biến trong cuốn sách năm 1988 của ông có tên là Fractals Everywhere, là một trong những kết quả nổi bật nhất trong các hệ thống động lực. Chọn bất kỳ điểm bắt đầu nào bên trong tam giác và làm theo quy tắc sau: chọn ngẫu nhiên đồng đều một trong ba đỉnh, nhảy chính xác một nửa khoảng cách từ điểm hiện tại của bạn về phía đỉnh đó và chấm một điểm. Lặp lại hàng ngàn lần. Sau một thời gian ngắn khởi chạy ban đầu, mọi điểm tiếp theo đều nằm trên tam giác Sierpinski với xác suất bằng 1 — fractal là điểm hấp dẫn duy nhất của bước đi ngẫu nhiên này. Phân chia đệ quy xác định và trò chơi hỗn loạn ngẫu nhiên đều là các trường hợp của một Hệ thống hàm lặp (IFS) với cùng ba bản đồ trung điểm; theo định lý ánh xạ co, mọi IFS với các phép co nghiêm ngặt đều có một điểm hấp dẫn compact không rỗng duy nhất mà bất kỳ quỹ đạo ngẫu nhiên nào cũng hội tụ về nó.

Tham chiếu độ sâu đệ quy

Nơi tam giác Sierpinski xuất hiện

• Tam giác Pascal mô-đun 2: tô màu đen cho mỗi ô của tam giác Pascal nếu nó là số lẻ và màu trắng nếu nó là số chẵn. Các ô màu đen tạo thành chính xác tam giác Sierpinski — một cầu nối kinh ngạc giữa tổ hợp và hình học fractal.
• Quy tắc ô tự động 90 (Rule 90): ô tự động một chiều "Rule 90" của Stephen Wolfram, bắt đầu từ một ô màu đen duy nhất, tạo ra tam giác Sierpinski theo từng hàng.
• Ăng-ten fractal: Ăng-ten đơn cực và lưỡng cực Sierpinski khai thác tính tự đồng dạng để đạt được cộng hưởng đa băng tần — một ăng-ten duy nhất có thể bao phủ nhiều dải tần số. Chúng được sử dụng trong điện thoại di động và thiết bị Wi-Fi hiện đại.
• Giảng dạy khoa học máy tính: một ví dụ kinh điển cho đệ quy, chia để trị, IFS và lý thuyết chiều. Nó cũng là một mục tiêu kiểm thử đơn vị (unit-test) tuyệt vời cho các thư viện đồ họa.
• Nghệ thuật và thiết kế tạo sinh (Generative art): dệt may, logo, lót ly khắc laser, áp phích lễ hội âm nhạc — sự kết hợp giữa chiều sâu toán học và sự đơn giản về mặt trực quan của fractal giúp nó có thể được tái phối trộn không giới hạn.
• Đồ thị trạng thái của Tháp Hà Nội: đồ thị trạng thái của trò chơi Tháp Hà Nội với N đĩa chính là đồ thị Sierpinski độ sâu N — cùng một cấu trúc dưới một lớp vỏ khác.

Tam giác Sierpinski so với Tam giác Pascal: Một đồng nhất thức đầy bất ngờ

Viết tam giác Pascal cho nhiều hàng, sau đó tô màu tối cho các ô có hệ số nhị thức lẻ và màu sáng cho các ô có hệ số chẵn. Hình ảnh thu được là một tam giác Sierpinski hoàn hảo. Lý do là định lý Kummer về các hệ số nhị thức theo mô-đun số nguyên tố: C(n, k) mod 2 bằng 1 khi và chỉ khi biểu diễn nhị phân của k nhỏ hơn hoặc bằng từng bit so với biểu diễn nhị phân của n. Một cách đệ quy, điều này tạo ra chính xác quy tắc Sierpinski — ba bản sao ở trên, bản sao ở trung tâm bị thiếu — và hình ảnh giới hạn là fractal. Chuyển trình tạo này sang "Bố cục tam giác Pascal" để xem mối liên hệ theo hướng phù hợp.

Những quan niệm sai lầm phổ biến

• "Tam giác Sierpinski có diện tích bằng không." Đúng — nhưng chỉ trong giới hạn vô hạn. Tại bất kỳ độ sâu N hữu hạn nào, các lá vẫn chiếm (3/4)N diện tích bên ngoài. Ở độ sâu 9, tỷ lệ đó vẫn vào khoảng 7.5%, hoàn toàn có thể nhìn thấy rõ.
• "Bạn cần một tam giác đều để bắt đầu." Sai. Phép đệ quy hoạt động trên mọi tam giác (vuông, tù, suy biến-miễn là không đồng phẳng/thẳng hàng). Hình dạng fractal được bảo toàn bởi mọi phép biến đổi áffin. Hãy chuyển đổi các hình dạng bên ngoài trong công cụ này để tự mình chứng kiến Nus.
• "Trò chơi hỗn loạn đòi hỏi các số ngẫu nhiên đặc biệt." Không — tính ngẫu nhiên số nguyên từ 1 đến 3 đồng đều là đủ. Bất kỳ điểm bắt đầu nào cũng hoạt động (sau một thời gian khởi chạy ngắn để xóa bỏ điểm bắt đầu).
• "Chiều fractal chỉ là một cái tên hoa mỹ cho một số nguyên." Không — chiều của tam giác Sierpinski thực sự nằm giữa 1 và 2. Không có chiều số nguyên nào biểu thị được cách nó thay đổi quy mô.

Các câu hỏi thường gặp