Đến nội dung


Hình ảnh
* * * * * 1 Bình chọn

Bài toán N−Phương Hậu đã chính thức tìm lời giải cho số các vị trí hợp lệ đó là $\left ( 0.143n \right )^{n}$

n-queen problem

  • Please log in to reply
Chủ đề này có 4 trả lời

#1 DOTOANNANG

DOTOANNANG

    Đại úy

  • Điều hành viên Đại học
  • 1538 Bài viết
  • Giới tính:Nam
  • Đến từ:T H P T Ngô Gia Tự ( "bắp nhà chùa" ) , Phú Yên

Đã gửi 12-02-2022 - 14:41

Bài toán N−Phương Hậu đã chính thức tìm lời giải cho số các vị trí hợp lệ đó là $\left ( 0.143n \right )^{n}.$

Nguồn_ https://news.harvard...-chess-problem/, hi vọng sắp tới mình có thể tham gia và làm tốt hơn trong việc quảng bá hay thảo luận các vấn đề liên quan đến Toán Tổ hợp. Hơn nữa, mình mong các thành viên khác ủng hộ hết mình cho ý tưởng mọi người chung tay cải tạo lại Box Toán Tổ hợp của anh Nxb − người anh rất tâm huyết của diễn đàn.


Bài viết đã được chỉnh sửa nội dung bởi DOTOANNANG: 12-02-2022 - 14:53


#2 Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 618 Bài viết
  • Giới tính:Nam

Đã gửi 12-02-2022 - 17:00

Bài toán N−Phương Hậu đã chính thức tìm lời giải cho số các vị trí hợp lệ đó là $\left ( 0.143n \right )^{n}.$

Nguồn_ https://news.harvard...-chess-problem/, hi vọng sắp tới mình có thể tham gia và làm tốt hơn trong việc quảng bá hay thảo luận các vấn đề liên quan đến Toán Tổ hợp. Hơn nữa, mình mong các thành viên khác ủng hộ hết mình cho ý tưởng mọi người chung tay cải tạo lại Box Toán Tổ hợp của anh Nxb − người anh rất tâm huyết của diễn đàn.

Chính xác hơn thì không có bài toán $n$-hậu (a đề nghị dịch thế này vì a thấy không có gì không ổn cả, có thể em chưa quen nên viết vậy) theo nghĩa đếm tất cả lời giải vì thực ra không có công thức tổng quát nào cả. Cái mà Simkin là được chỉ là tìm công thức tiệm cận của số lời giải cho bài toán $n$-hậu. Lời giải hoàn chỉnh của Simkin ở đây https://arxiv.org/abs/2107.13460

Chính xác thì số lời giải là $((1\pm o(1))ne^{-\alpha})^n.$ Ở đây $o(1)$ sẽ tiến tới $0$ khi $n$ tiến ra vô cực.

Mọi người có thể đọc bài viết này để hiểu sơ lược chứng minh https://www.quantama...ueens-20210921/

 

Để đọc bài báo của Simkin thì kiến thức cơ bản không cần nhiều, nhưng sẽ phải dành rất nhiều thời gian thì mới hiểu được và anh không nghĩ đấy là công việc có ích với bất cứ ai trên diễn đàn, nói đúng hơn là không có sức mà làm. Tuy nhiên điều đáng chú ý là cách tiếp cận của Simkin là “thuật toán tham ngẫu nhiên” (random greedy algorithm). Mọi người có thể xem thêm một bài khác của Simkin ở đây https://arxiv.org/pdf/2105.11431.pdf

 

Vậy ta đã gặp thuật toán tham ở đâu? Chính là trong toán olympic! Mình đã nhắn cho một số điều hành viên tìm hiểu và bổ sung phương pháp thuật toán và các ví dụ vào box toán tổ hợp, nhưng mọi người không hào hứng lắm. Trước đó thì Nguyễn Tiến Zung đã nói rất nhiều về vấn đề này trên blog của ông ấy và xem như một lỗ hổng trong lối dạy và học ở Việt Nam, xem một tài liệu ông viết ở đây http://shop.sputnike...oan-như-thế-nào

Mọi người có thể xem ở đây để thấy thuật toán tham xuất hiện trong toán olympic thế nào https://people.bath..../algorithms.pdf

Tuy nhiên cái thầy Zung nói tới có ý nghĩa sâu xa hơn, tức là học sinh cần tự xây dựng thuật toán để giải quyết vấn đề. Vì vậy, chỉ nên coi thuật toán tham là một ví dụ tốt, và cố gắng tìm hiểu sâu thêm các khía cạnh khác của thuật toán và đưa ra thêm nhiều ví dụ áp dụng vào các bài toán phổ thông. 

 

Anh nghĩ nếu em tự tin thì có thể viết và bổ sung phần này vào mục phương pháp của box toán tổ hợp, trước hết là với thuật toán tham. Anh đề nghị cấu trúc sau: Định nghĩa thuật toán tham là gì, sau đó cho một số ví dụ tầm thường, và sau đó cho thêm các ví dụ khác khó hơn. Có thể dựa vào tài liệu này luôn https://people.bath..../algorithms.pdf  

 

Nếu hoàn thành tốt bước đầu này thì anh nghĩ tiếp theo sẽ là một mảnh đất màu mỡ vì có vô số thuật toán có thể khai thác. Anh nghĩ đây là việc cấp bách vì các bài toán olympic đã bão hoà và học sinh có thể tự học và tiếp cận một cách dễ dàng, diễn đàn cần sớm nâng cao kiến thức trong mục này để có thể xuất hiện những thảo luận mới trong box toán tổ hợp, mà như mình thấy đã có dấu hiệu chết từ rất lâu. 


Bài viết đã được chỉnh sửa nội dung bởi Nxb: 12-02-2022 - 17:10


#3 perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản trị
  • 4464 Bài viết
  • Giới tính:Nam
  • Sở thích:Đàn guitar, ngắm người mình yêu, học toán

Đã gửi 13-02-2022 - 16:11

Tài liệu anh kiếm được hay thế :D Phần thuật toán tham lam kia làm em nhớ bên chuyên tin hay học (ngay cả một số ví dụ trong tài liệu của anh, em cũng từng gặp phải khi học tin).

Đúng là chúng ta có thể bắt đầu viết một số bài "introduction" về thuật toán với mẫu bài lấy từ tài liệu kia :)


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D

$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$




I'm still there everywhere.

#4 Nxb

Nxb

    Thiếu úy

  • ĐHV Toán học Hiện đại
  • 618 Bài viết
  • Giới tính:Nam

Đã gửi 15-02-2022 - 22:52

Tài liệu anh kiếm được hay thế :D Phần thuật toán tham lam kia làm em nhớ bên chuyên tin hay học (ngay cả một số ví dụ trong tài liệu của anh, em cũng từng gặp phải khi học tin).

Đúng là chúng ta có thể bắt đầu viết một số bài "introduction" về thuật toán với mẫu bài lấy từ tài liệu kia :)

Bây giờ quan trọng là ai tình nguyện viết. Mặt khác, tài liệu kia chỉ có vai trò tổng hợp thôi, còn anh thấy cái mà thầy Zung viết mới có ý nghĩa lớn. Những cái thuật toán này chỉ là phần chết thôi còn người giải toán mới là phần sống. Chẳng hạn nếu cứ cố bám vào thuật toán tham để giải thích mọi lời giải như trong tài liệu kia thì sẽ thấy rất nhiều thứ khiên cưỡng xuất hiện.


Bài viết đã được chỉnh sửa nội dung bởi Nxb: 15-02-2022 - 22:56


#5 perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản trị
  • 4464 Bài viết
  • Giới tính:Nam
  • Sở thích:Đàn guitar, ngắm người mình yêu, học toán

Đã gửi 16-02-2022 - 04:18

Bây giờ quan trọng là ai tình nguyện viết. Mặt khác, tài liệu kia chỉ có vai trò tổng hợp thôi, còn anh thấy cái mà thầy Zung viết mới có ý nghĩa lớn. Những cái thuật toán này chỉ là phần chết thôi còn người giải toán mới là phần sống. Chẳng hạn nếu cứ cố bám vào thuật toán tham để giải thích mọi lời giải như trong tài liệu kia thì sẽ thấy rất nhiều thứ khiên cưỡng xuất hiện.

Dạ tất nhiên rồi anh. Ý em muốn nói là viết kiểu mời gọi người đọc suy nghĩ, chứ chỉ trình bày thì tài liệu kia đủ rồi :)


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D

$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$




I'm still there everywhere.




1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh