🔙 Quay lại trang tải sách pdf ebook Tạp Chí Epsilon Số 4 Ebooks Nhóm Zalo MA TRẬN NGẪU NHIÊN (TIẾP THEO) Vũ Hà Văn ĐIỀU KIỆN NGOẠI TIẾP CỦA MỘT TỨ GIÁC KHÔNG LỒI & ỨNG DỤNG Đỗ Thanh Sơn VỀ CHỨNG MINH VÀ TIẾN BỘ TRONG TOÁN HỌC William P. Thurston (Nguyễn Dzuy Khánh dịch) XẤP XỈ DIOPHANTINE VÀ LIÊN PHÂN SỐ Lý Ngọc Tuệ VÀ CÁC CHUYÊN MỤC KHÁC Vì chúng ta có trí tuệ nên có thể dễ dàng đoán được nghĩa của một từ lạ thông qua ngữ cảnh. Còn đối với máy tính thì sao? Làm cách nào chúng ta có thể nói với nó rằng hãy dùng ngữ cảnh để học nghĩa của từ? BIỂU DIỄN NGHĨA CỦA TỪ BẰNG VÉC-TƠ Lê Phong MAGAZINE ngày 13 tháng 06 năm 2015 Tạp chí online của cộng đồng những người yêu Toán Số 3Chủ biên: TRẦN NAM DŨNG Biên tập viên: VÕ QUỐC BÁ CẨN TRẦN QUANG HÙNG LÊ PHÚC LỮ NGUYỄN TẤT THU ĐẶNG NGUYỄN ĐỨC TIẾN MỤC LỤC Vũ Hà Văn Ma trận ngẫu nhiên (tiếp theo) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Lý Ngọc Tuệ Xấp xỉ Diophantine và liên phân số . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Lê Phong Biểu diễn nghĩa của từ bằng véc-tơ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Võ Nhật Vinh Mô hình hóa bài toán sắp lịch dạng flowshop bằng đại số MaxPlus . . . . . . . . . . 47 William P. Thurston Về chứng minh và tiến bộ trong toán học . . . . . . . . . . . . . . . . . . . . . . . . . 63 Huỳnh Xuân Tín Ứng dụng của xác suất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 V. Tikhomirov Định lý Fermat-Euler về tổng hai bình phương . . . . . . . . . . . . . . . . . . . . . . 97 Nguyễn Văn Huyện Một bất đẳng thức thú vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Trần Quang Hùng Về hai bài hình trong kỳ thi IMO 2015 . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Nguyễn Văn Linh Mở rộng các bài toán hình học bằng phép quy nạp . . . . . . . . . . . . . . . . . . . 135 Ban biên tập Lời giải và bình luận đề thi IMO 2015 . . . . . . . . . . . . . . . . . . . . . . . . . . 153 3 Tạp chí Epsilon, Số 04, 08/2015 Alon Amit Bài toán hay – Lời giải đẹp: Về bài toán IMO 1988 . . . . . . . . . . . . . . . . . . . 171 Phạm Văn Thuận, Nguyễn Tiến Lâm Đôi nét về kỳ thi APMOPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 Nguyễn Quốc Khánh Nẻo về của toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Ban biên tập Đề thi Toán mô hình Hà Nội 2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 Ban biên tập Bài toán chia đoạn thẳng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Ban biên tập Lời giải các bài toán ở số 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 4 MA TRẬN NGẪU NHIÊN (TIẾP THEO) Vũ Hà Văn (Đại học Yale, Mỹ) 4. Xác suất suy biến: trường hợp đối xứng Hoàn toàn tương tự, một cách tự nhiên ta đánh giá xác suất ma trận ngẫu nhiên đối xứng psym n suy biến. Bài toán này được G.Kalai và N.Linial nhắc đến cho tác giả trong cuộc nó chuyện riêng vào khoảng năm 2004. Thật ngạc nhiên đối với chúng ta, vào thời điểm đó ngay cả một kết quả tương tự với định lý Komlós 1967 cũng chưa được biết đến. Theo Kalai và Linial, giả thuyết dưới đây được đưa ra bởi B.Weiss vào những năm 1980, nhưng hoàn toàn có thể là Komlós đã nghĩ về nó trước đó. Giả thuyết 1. psym n D o.1/. Khó khăn chính liên quan đến Msym n là các dòng không còn độc lập nữa. Chẳng hạn như dòng cuối cùng gần như đã được xác định bởi các dòng trước đó. Như vậy quy trình xếp các dòng được xét đến trong trường hợp không đối xứng không còn áp dụng được nữa. Trong [16], Costello, Tao và Vũ tìm được một phương pháp để vượt qua được tính phụ thuộc. Hóa ra là phương pháp đúng để xây dựng ma trận đối xứng không phải là theo từng dòng (như trường hợp của Msym n ) mà là từ góc đến góc. Trong bước k, ta xét ma trận con bậc k ở góc trên bên trái. Chiến thuật, theo ý tưỡng của Komlós [38] là chứng minh rằng với xác suất cao, đối hạng của ma trận này, khi k tăng sẽ có ứng xử như điểm cuối của một chuyển động ngẫu nhiên lệch trên tập hợp các số nguyên không âm với xu hướng mạnh đi về bên trái khi còn có thể. Điều này dẫn đến sự khẳng định của giả thuyết Weiss. Định lý 4.1. psym n D o.1/. Công cụ kỹ thuật chính trong chứng minh Định lý 4.1 là phiên bản (hai chiều) sau đây của Định lý 2.5. Định lý 4.2. (Littlewood-Offord hai chiều) Giả sử aij là các số thực khác 0 và i, 1 i; j n là các biến ngẫu nhiên Bernoulli độc lập phân bố đều. Giả sử PQ là dạng toàn phương Q WD 1 i;j naij i j :. Khi đó với mọi giá trị a: P.Q D a/ D O.n1=4/: Ta hãy xét bước cuối trong quá trì khi ma trận con bậc .n 1/ .n 1/ đã được xây dựng. Để thu được Msym n1, ta bổ sung dòng ngẫu nhiên X D . 1; : : : ; n/ và chuyển vị của nó. Với điều kiện trên Msym n , định thức của ma trận n n thu được là X 1 i;j n1 aij i j C det Mn1; 5 Tạp chí Epsilon, Số 04, 08/2015 Trong đó aij (đúng đến dấu) là các thừa số của Mn1. Nếu Msym n là suy biến, thì định thực của nó bằng 0, suy ra Q WD X 1 i;j n1 aij i j D det Mn1; cho ta cơ sở để áp dụng định lý 4.2. Được thúc đẩy bởi trường hợp không đối xứng, một cách tự nhiên ta đưa ra giả thuyết: Giả thuyết 2. psym n D .1=2 C o.1//n: Cận trên từ [16] là n1=8 và có thể dễ dàng cải thiện thành n1=4. Costello [13] cải thiện được cận trên thành n1=2C và Nguyen [52] đẩy xa hơn thành n!.1/. Cận trên tốt nhất cho đến thời điểm này là exp.nc/, với hằng số nhỏ c > 0 nào đó, thuộc về Vershynin [76]. Phép chứng minh ba kết quả cuối cùng, bên cạnh các chứng minh khác, làm cho việc sử dụng các kết quả kiểu định lý ngược Littlewood-Offord trở nên tinh vi; xem [53] cho một khảo sát của vấn đề này. 5. Hạng và đối hạng Xác suất suy biến chính là xác suất để ma trận ngẫu nhiên có đối hạng ít nhất là 1. Thế đối hạng lớn hơn 1 thì sao? Giả sử pn;k ký hiệu xác suất để Mn có đối hạng ít nhất là k. Dễ dàng chứng minh được rằng pn;k .12C o.1//kn: (1.1) Điều này dẫn đến giả thuyết rằng đánh giá này là chặt cho hằng số k. Trong [37], Kalin, Komlós và Szemerédi chứng minh được rằng Định lý 5.1. Tồn tại hàm số .k/ dần đến 0 cùng với k sao cho pn;k n: Trong Bourgain và các tác giả khác [9], các tác giả xem xét trường hợp của Mn trong đó l dòng đầu cố định và n–l dòng tiếp theo ngẫu nhiên. Gọi L là ma trận con xác định bởi l dòng đầu và ký hiệu mô hình này bởi Mn.L/. Rõ ràng corankMn.L/ corankL. Các tác giả của [9] chứng minh được rằng ([9], Định lý 1.4). Định lý 5.2. Tồn tại hằng số dương c sao cho P.corankMn.L/ > corankL/ .1 c/n: Chúng ta hãy quay trở lại với mô hình đối xứng Msym n và nhìn nó dưới góc nhìn mới này, khai thác mối liên hệ với đồ thị ngẫu nhiên Erdos-Rényi ¨ G.n; 1=2/. Ta có thể thấy rằng Msym n D 2A.n; 1=2/ Jn; trong đó Jn là ma trận bậc n gồm toàn 1 (ở đây ta cho phép G.n; 1=2/ có khuyên, do đó các thành phần trên đường chéo của A.n; 1=2/ có thể là 1. Nếu ta cố định mọi thành phần đường 6 Tạp chí Epsilon, Số 04, 08/2015 chéo bằng 0, phân tích không thay đổi gì đáng kể).) Vì Jn có hạng bằng 1, từ 4.1 suy ra rằng với xác suất 1 o.1/, A.n; 1=2/ có đối hạng ít nhất là 1. Ta có thể đưa đối hạng về 0 bởi một lý luận kỹ thuật hơn một chút. Xét Msym nC1thay vì Msym n và chuẩn hóa sao cho các dòng và cột đầu tiên đều là -1. Cộng ma trận này với JnC1, ta được ma trận có dạng 0 0 0 Msym n C Jn Như vậy ta có thể kết luận Hệ quả 5.3. Với xác suất 1 o.1/, corankA.n; 1=2/ D 0. Từ góc nhìn đồ thị ngẫu nhiên, một cách tự nhiên ta đặt câu hỏi là mệnh đề này có còn đúng cho các mật độ p khác. Rõ ràng câu trả lời sẽ là phủ định với p rất nhỏ. Thật vậy, nếu p < .1 /log n=n thì G.n; p/ có, với xác suất cao, những đỉnh cô lập (xem [6, 35]) có nghĩa là ma trận kề của nó sẽ có những dòng toàn 0 và do đó suy biến. Costello và Vũ [14] chứng minh được rằng log n=n là điểm chia đúng. Định lý 5.4. Với mọi hằng số > 0, with probability 1 o.1/, corankA.n; .1 C /log n=n/ D 0: Với p < log n=n, đối hạng của A.n; p/ không còn bằng 0 như ở trên. Ứng xử của biến ngẫu nhiên này chưa được hiểu một cách hoàn toàn. Trong trường hợp khi p D c log n=n với hằng số 0 < c < 1, Costello và các tác giả khác. [15] đã chứng minh được rằng với xác suất 1 o.1/, đối hạng được xác định bởi các đồ thị con nhỏ, điều này tương thích với Hiện tượng I. Ví dụ, Định lý 5.5. Với mọi hằng số > 0 và .1=2 C /log n=n < p < .1 /log n=n, với xác suất 1 o.1/, corankA.n; .1 C p/ bằng số các đỉnh cô lập trong G.n; p/. Với các phạm vi khác của p, ta cần chú ý đến số các sơ-ri (sơ-ri là cặp các đỉnh bậc 1 có cùng kề với 1 đỉnh) và số các đồ thị con nhỏ khác. Kết quả chính của [15] cho công thức chính xác của đối hạng thông qua các tham số này. Khi p D c=n; c > 1, G.n; p/ bao gồm một thành phần lớn và rất nhiều các thành phần nhỏ. Có lý khi ta tập trung vào thành phần lớn mà ta sẽ ký hiệu là Giant .n; p/. Vì Giant .n; p/ chứa những sơ-ri, ma trận kề của Giant .n; p/ là suy biến (với xác suất cao). Tuy nhiên, nếu ta nhìn vào klõi (kcore) của Giant .n; p/, với k 3, thì có vẻ có lý rằng đồ thị con này sẽ có hạng đầy đủ. Bordenave, Lelarge và Salez [8] đã chứng minh được kết quả liên quan dưới đây Giả thuyết 3. Cho k là số nguyên cố định không nhỏ hơn 3. Với xác suất 1 o.1/, ma trận kề của k-lõi của Giant .n; p/ không suy biến. Định lý 5.6. Xét G.n; c=n/ với hằng số c > 0 nào đó. Khi đó với xác suất .1 o.1//n, rank.A.n; c=n// D .2 q ecq cqecq C o.1//n; Trong đó 0 < q < 1 là nghiệm nhỏ nhất của phương trình q D exp.c exp cq/. Để kết thúc mục này, ta hãy xét đồ thị ngẫu nhiên Gn;d . Với d D 2, Gn;d bản chất là hợp của các vòng tròn rời nhau. Không khó khăn để chứng minh rằng với xác suất 1 o.1/, một trong các vòng tròn này sẽ có độ dài chia hết cho 4 và vì thế ma trận kề của nó không suy biến (thực sự, đối hạng sẽ là ‚.n/ khi số các vòng tròn có độ dài chia hết cho 4 có bậc như thế). Thật bối rối nhưng giả thuyết sau vẫn hoàn toàn mở Giả thuyết 4. Với mọi 3 d n=2, xác suất 1 o.1/ An;d không suy biến. 7 Tạp chí Epsilon, Số 04, 08/2015 6. Định thức và vĩnh thức Ta hãy bắt đầu từ câu hỏi cơ bản Định thức của Mn lớn như thế nào? Đây là động cơ thực sự của các nghiên cứu nguyên thủy của Komlos, như tiêu đề của các bài báo [38, 39] đã cho thấy. Tuy nhiên, các kết quả của ông (và các định lý khác trong Mục 2) không cho ta một đánh giá không tầm thường nào cho j det Mnj, chờ đợi rằng j det Mnj > 0 với xác suất lớn. Khi tất cả các hàng của Mn có chiều dài pn, từ bất đẳng thức Hadamard suy ra rằng j det Mnj nn=2 Một giả thuyết được đưa ra là với xác suất gần bằng 1, j det Mnj gần với cận trên này. Giả thuyết 5. Gần như chắc chắn rằng j det Mnj D n.1=2o.1//n. Giả thuyết này được hỗ trợ bởi nhận xét quen thuộc sau đây của Turan. Tính chất 6.1. E..det Mn/2/ D nŠ: Để kiểm tra điều này, chú ý rằng .det Mn/2 DX ; 2Sn .1/ sign C sign Yn iD1 i .i/ i .i/: Theo tính tuyến tính của suy biến và sự kiện E. i/ D 0, ta có E.det Mn/2 DX 2Sn 1 D nŠ: Từ đây theo bất đẳng thức Markov ta suy ra rằng với mọi hàm số !.n/ dần đến vô cùng cùng với n, ta có với xác suất dần đến 1. j det Mnj !.n/pnŠ; pMột khẳng định của Girko (kết quả chính của [31, 30]) suy ra rằng j det Mnj thường là gần với nŠ.Tuy nhiên, chứng minh của tác giả này có thể chứa một số khoảng trống chưa xử lý được (xem [54] để biết chi tiết). Trong [66], Tao và Vũ đã xác lập được cận dưới tương ứng, qua đó khẳng định Giả thuyết 5. Định lý 6.1. Với xác suất 1 o.1/, j det Mnj pnŠ exp.29pn log n/: Ta phác họa ngắn gọn phép chứng minh thông qua một bổ đề hữu ích. Trước hết ta coi j det Mnj như thể tích của khối lăng trụ căng trên n véc-tơ ngẫu nhiên f1; 1g. Thể tích này là tích của các khoảng cách từ véc tơ thứ .d C 1/ đến không gian con sinh bởi d véc-tơ đầu, trong đó d chạy từ 0 đến n – 1. Ta có thể có được một sự kiểm soát chặt chẽ về khoảng cách này (như một biến ngẫu nhiên) nhờ vào bổ đề dưới đây, được chứng minh bằng cách sử dụng bất đẳng thức của Talagrand [66, 79]. 8 Tạp chí Epsilon, Số 04, 08/2015 Bổ đề 6.2. Cho W là một không gian con cố định chiều 1 d n 4 và X là một véc tơ ngẫu nhiên ˙1. Khi đó với mọi t > 0 P.jdist.X; W / pn dj t C 1/ 4 exp.t2=16/: (1.2) Tuy nhiên bổ để không áp dụng được khi d rất gần với n. Trong trường hợp này, ta cần sử dụng tính ngẫu nhiên của W, trong một góc nhìn tương tự như chứng minh ở Mục 3. Bổ đề 6.2 xuất hiện trong nhiều nghiên cứu khác và có thể sử dụng để chứng minh nhiều bất đẳng thức tập trung (concentration inequalities) khác (ví dụ như bất đẳng thức dạng Hanson-Wright cho sự tập trung của dạng toàn phương ngẫu nhiên); xem chi tiết ở [79]. Một cách tự nhiên khác để đánh giá j det Mnj là nhìn nó như tích của các giá trị suy biến của Mn. Theo luật Marcheko-Pastur [5], ta biết (một cách tiệm cận) hầu hết các giá trị suy biến. Trở ngại chính là những giá trị ít ỏi còn lại có thể rất nhỏ. Như vậy, bài toán về cơ bản đưa về việc đánh giá chặn dưới cho giá trị suy biến nhỏ nhất. Vấn đề này đã được nêu ra đầu tiên bởi Goldstine và von Neumann vào những năm 1940 [33] và đã được nghiên cứu trong [20, 55, 57, 67, 73] (xem [46, 59] và tài liệu tham khảo ở đó liên quan đến ma trận chữ nhật). Đặc biệt, Rudelson và Vershynin [57] chứng minh được Định lý 6.3. Tồn tại các hằng số C C; > 0 sao cho P.pn min.Mn/ t / Ct với mọi t .1 /n, trong đó min là giá trị suy biến nhỏ nhất. Định lý 6.3 có thể coi như một sự làm mạnh của định lý 2.2; xem [56, 53] để biết thảo luận chi tiết. Đánh giá này là chặt tính đến hằng số C. Trong [73] phân bố giới hạn của pn min.Mn/được xác định, từ đó suy ra giá trị chính xác của C trong phạm vi t nhỏ và giải quyết được giả thuyết của và một phần giả thuyết của Spielman và Teng [[61], Giả thuyết 2]. Bây giờ ta xem xét mô hình đối xứng Msym j det Msym n . Một lần nữa, theo bất đẳng thức Hadamard n j nn=2. Giả thuyết 6. Với xác suất 1 o.1/ j det Msym nj D n.1=2o.1//n: Đồng nhất thức Turan không còn đúng nữa bởi sự tương quan bị phá vỡ do tính đối xứng. Tuy nhiên, ta vẫn có thể chứng minh được E.det Msym n/2 D n.1Co.1//n: Mặt khác, chứng minh chặn dưới cho j det Mnj khó khăn hơn nhiều. Bài toán tìm chặn dưới cho giá trị suy biến nhỏ nhất được giải quyết mới đây bởi Nguyễn [51] và Vershynin [76], mặc dù, không giống như trong trường hợp không đối xứng, chúng ta vẫn không biết sự phân bố giới hạn của tham số này. Các kết quả của Nguyễn và Vershynin, kết hợp với luật nửa vòng tròn Wigner, xác nhận Giả thuyết 6. Định lý 6.4. Vỡi xác suất 1 o.1/ j det Msym nj D n.1=2o.1//n: 9 Tạp chí Epsilon, Số 04, 08/2015 Bây giờ ta chuyển sang khái niệm liên quan: vĩnh thức. Nhắc lại định nghĩa hình thực của định thức của ma trận M (với các hệ số mij ; 1 i; j n) det M WD X 2Sn .1/ sign Yn iD1 mi .i/: Vĩnh thức của ma trận M được định nghĩa là PerM WD X 2Sn Yn iD1 mi .i/: (1.3) Dễ thấy rằng đồng nhất thức Turan vẫn đúng, cụ thể là E. PerMn/2 D nŠ: Điều này gợi ý là j PerMnj sẽ bằng n.1=2o.1//n. Tuy nhiên, điều này sẽ khó chứng minh hơn nhiều. Giả thuyết dưới đây, được coi như phiên bản vĩnh thức của kết quả kinh điển của Komlos pn D o.1/, vẫn còn là mở cho đến gần đây Giả thuyết 7. P. PerMn D 0/ D o.1/. Nguyên nhân của mọi khó khăn ở đây là vĩnh thức, không giống như định thức, không có một sự giải thích hình học tốt (giống như thể tích trong trường hợp định thức). Năm 2007, Tao và Vũ đã tìm được một cách tiếp cận hoàn toàn tổ hợp để tấn công bài toán vĩnh thức [69], dựa vào định nghĩa hình thức (1.3) và sử dụng kỹ thuật martingale từ lý thuyết tổ hợp xác suất. Họ đã chứng minh Định lý 6.5. Với xác suất 1 o.1/ j PerMnj D n.1=2o.1//n: Mảnh ghép còn thiếu cuối cùng là định lý tương tự định lý 6.5 cho trường hợp đối xứng. Giả thuyết 8. Với xác suất 1 o.1/ j PerMsym nj D n.1=2o.1//n: Được thúc đẩy bởi bài toán suy biến, ta cũng quan tâm đến việc tìm một đánh giá tốt cho xác suất để vĩnh thức bằng 0. Các đánh giá hiện nay mới chỉ ở bậc đa thức theo n. Có một số nghiên cứu khác liên quan đến sự phân bố của log j det Mnj và log j det Msym n j xem [31, 30, 54, 63] và các tài liệu tham khảo trong đó. 10 6 4. The singular probability: symmetric case As an analogue, it is natural to estimate psym matrix Msym nsingular. n, the probability that the symmetric This problem was mentioned to the author by G. Kalai and N. Linial (personal conversations) around 2004. To our surprise, at that point, even the analogue of Kom´los’ 1967 result was not known. According to Kalai and Linial, the following conjecture was circulated by B. Weiss in the 1980s, although it is quite possible that Koml´os had thought about it earlier. Conjecture 4.1. psym n = o(1). The main difficulty concerning Msym nis that its rows are no longer independent. In particular, the last row is almost determined by the previous ones. Thus, the row exposing procedure considered in the non-symmetric case is no longer useful. In [16], Costello, Tao and Vu found a way to circumvent the dependency. It turns out that the right way to build the symmetric matrix Msym nis not row by row (as for Mn), but corner to corner. In step k, one considers the top left sub matrix of size k. The strategy, following an idea of Koml´os [38] is to show that with high probability, the co-rank of this matrix, as k increases, behaves like the end point of a bias random walk on non-negative integers which has a strong tendency to go to the left whenever possible. This leads to a confirmation of Weiss’ conjecture. Theorem 4.2. psym n = o(1). The key technical tool in the proof of Theorem 4.2 is the following (quadratic) variant of Theorem 2.5. Theorem 4.3. (Quadratic Littlewood-Offord) Let aij be non-zero real numbers and ξi, 1 ≤ i, j ≤ n be i.i.d Bernoulli random variables. Let Q be the quadratic form Q := P1≤i,j≤naij ξiξj .. Then for any value a P(Q = a) = O(n−1/4). Let us consider the last step in the process when the (n − 1) × (n − 1) submatrix Msym n−1has been built. To obtain Msym n, we add a random row X = (ξ1, . . . , ξn) and its transpose. Conditioning on Msym matrix isX 1≤i,j≤n−1 n−1, the determinant of the resulting n × n aij ξiξj + det Mn−1, where aij (up to the signs) are the cofactors of Mn−1. If Msym nis singular, then 7 its determinant is 0, which implies Q := X 1≤i,j≤n−1 aij ξiξj = − det Mn−1, which gives ground for an application of Theorem 4.3. Motivated by the non-symmetric case, it is natural to conjecture Conjecture 4.4. psym n = (1/2 + o(1))n. The concrete bound from [16] is n−1/8, which can be easily improved to n−1/4. Costello [13] improved the bound to n−1/2+ and Nguyen [52] pushed it further to n−ω(1). The best current bound is exp(−nc), for some small constant c > 0, due to Vershynin [76]. The proofs of the last three results, among others, made sophisticated use of Inverse Littlewood-Offord type results; see [53] for a survey. 5. Ranks and co-ranks The singular probability is the probability that the random matrix has co-rank at least one. What about larger co-ranks ? Let us use pn,k to denote the probability that Mn has co-rank at least k. It is easy to show that pn,k ≥ (12+ o(1))kn. (2) It is tempting to conjecture that this bound is sharp for constants k. In [37], Kahn, Koml´os and Szemer´edi showed Theorem 5.1. There is a function (k) tending to zero with k such that pn,k ≤ n. In Bourgain et. al. [9], the authors consider a variant of Mn where the first l rows are fixed and the next n−l are random. Let L be the submatrix defined by the first l row and denote the model by Mn(L). It is clear that corankMn(L) ≥ corankL. The authors of [9] showed ([9, Theorem 1.4]) Theorem 5.2. There is a positive constant c such that P(corankMn(L) > corankL) ≤ (1 − c)n. 8 Let us go back to the symmetric model Msym nand view it from this new angle, exploiting a connection to Erd¨os-R´enyi random graph G(n, 1/2). One can see that Msym n = 2A(n, 1/2) − Jn, where Jn is the all-one matrix of size n. (Here we allow G(n, 1/2) to have loops, so the diagonal entries of A(n, 1/2) can be one. If we fix all diagonal entries to be zero, the analysis does not change essentially.) Since Jn has rank one, it follows from Theorem 4.2 that with probablity 1−o(1), A(n, 1/2) has corank at most one. One can reduce the co-rank to zero by a slightly trickier argument. Consider Msym instead of Msym n+1 nand normalize so that its first row and column are all- negative one. Adding this matrix with Jn+1, we obtain a matrix of the form Thus we conclude 0 0 0 Msym n + Jn Corollary 5.3. With probability 1 − o(1), corankA(n, 1/2) = 0. From the random graph point of view, it is natural to ask if this statement holds for a different density p. It is clear that answer is negative if p is very small. Indeed, if p < (1 − ) log n/n, then G(n, p) has, with high probability, isolated vertices (see [6, 35]) which means that its adjacency matrix has all zero rows and so is singular. Costello and Vu [14] proved that log n/n is the right threshold. Theorem 5.4. For any constant > 0, with probability 1 − o(1), corankA(n,(1 + ) log n/n) = 0. For p < log n/n, the co-rank of A(n, p) is no longer zero as mentioned above. The behavior of this random variable is not entirely understood. For the case when p = c log n/n for some constant 0 < c < 1, Costello et. al. [15] showed that with probability 1 − o(1), the co-rank is determined by small subgraphs, which is consistent with Phenomenon I. For example, Theorem 5.5. For any constant > 0 and (1/2+ ) log n/n < p < (1− ) log n/n, with probability 1 − o(1), corankA(n,(1 + p) equals the number of isolated vertices in G(n, p). For other ranges of p, one needs to take into account the number of cherries ( a cherry is a pair of vertices of degree one with a common neighbor) and the numbers of other small subgraphs. The main result of [15] gives a precise formula for the co-rank interim of these parameters. 9 When p = c/n, c > 1, G(n, p) consists of a giant component and many small com ponents. It makes sense to focus on the giant one which we denote by Giant(n, p). Since Giant(n, p) has cherries , the adjacency matrix of Giant(n, p) is singular (with high probability). However, if we look at the k-core of Giant(n, p), for k ≥ 3, it seems plausible that this subgraph has full rank. Conjecture 5.6. Let k be a fixed integer at least 3. With probability 1 − o(1), the adjacency matrix of the k-core of Giant(n, p) is non-singular. Bordenave, Lelarge and Salez [8] proved the following related result Theorem 5.7. Consider G(n, c/n) for some constant c > 0. Then with probability (1 − o(1))n, rank(A(n, c/n)) = (2 − q − e−cq − cqe−cq + o(1))n, where 0 < q < 1 is the smallest solution of q = exp(−c exp −cq). To conclude this section, let us consider the random regular graph Gn,d. For d = 2, Gn,d is just union of disjoint circles. It is not hard to show that with probability 1−o(1), one of these circles has length divisible by 4, and thus its adjacency matrix is non-singular (in fact, the corank will by Θ(n) as the number of circles of length divisible by 4 is of this order). Somewhat embarrassingly, the following conjecture is totally open Conjecture 5.8. For any 3 ≤ d ≤ n/2, with probability 1 − o(1) An,d is non singular. 6. Determinant and Permanent Let us start with a basic question How big is the determinant of Mn? This was actually the real motivation of Koml´os’ original study, as the titles of [38, 39] suggest. However, his results (and other theorems in Section 2) do not give any non-trivial estimate on | det Mn|, expect that | det Mn| > 0 with high probability. As all rows of Mn has length √n. Hadamard’s inequality implies that | det Mn| ≤ nn/2. It has been conjectured that with probability close to 1, | det Mn| is close to this upper bound. 10 Conjecture 6.1. Almost surely | det Mn| = n(1/2−o(1))n. This conjecture is supported by a well-known observation of Tur´an. Fact 6.1. E((det Mn)2) = n!. To verify this, notice that (det Mn)2 =X π,σ∈Sn (−1) signπ+ signσ Yn i=1 ξiπ(i)ξiσ(i). By linearity of singularity and the fact that E(ξi) = 0, we have E(det Mn)2 =X π∈Sn 1 = n!. It follows immediately by Markov’s bound that for any function ω(n) tending to infinity with n, with probability tending to 1. | det Mn| ≤ ω(n)√n!, A statement of Girko (the main result of [31, 30]) implies that | det Mn| is typically close to √n!. However, his proof appears to contain some gaps (see [54] for details). In [66], Tao and Vu established the matching lower bound, confirming Conjecture 6.1. Theorem 6.2. With probability 1 − o(1), | det Mn| ≥ √n! exp(−29pn log n). We sketch the proof very briefly as it contains a useful lemma. First view | det Mn| as the volume of the parallelepiped spanned by n random {−1, 1} vectors. This volume is the product of the distances from the (d + 1)st vector to the subspace spanned by the first d vectors, where d runs from 0 to n−1. We are able to obtain a very tight control on this distance (as a random variable), thanks to the following lemma, which can be proved using a powerful concentration inequality by Talagrand [66, 79]. Lemma 6.3. Let W be a fixed subspace of dimension 1 ≤ d ≤ n − 4 and X a random ±1 vector. For any t > 0 P(|dist(X, W) −√n − d| ≥ t + 1) ≤ 4 exp(−t2/16). (3) 11 The lemma, however, is not applicable when d is very close to n. In this case, we need to make use of the fact that W is random, in a fashion similar to the proof in Section 3. Lemma 6.3 appears handy in many other studies and can be used to derive other concentration inequalities (such as Hanson-Wright type inequalities for concentra tion of random quadratic form); see [79] for more details. Another natural way to estimate | det Mn| is to view it as the product of the singular values of Mn. By Marcheko-Pastur law [5], one knows (asymptotically) most singular values. The main obstacle is that the last few can be very small. Thus, the problem basically boils down to bounding the least singular value from below. This problem was first raised by Goldstine and von Neumann in the 1940s [33] and has been investigated in [20, 55, 57, 67, 73] (see also [46, 59] and the references therein for other works concerning rectangular matrices). In particular, Rudelson and Vershynin [57] proved Theorem 6.4. There are constants C, > 0 such that P(√nσmin(Mn) ≤ t) ≤ Ct for all t ≤ (1 − )n, where σmin denotes the least singular value. Theorem 6.4 can be seen as a strengthening of Theorem 2.2; see [56, 53] for more discussion. The bound is sharp, up to the constant C. In [73] the limiting distri bution of √nσmin(Mn) was determined, yielding the exact value of C in a smaller range of t and settling a conjecture of Edelman and partially a conjecture by Spielman and Teng [61, Conjecutre 2]. Now we turn to the symmetric model Msym | det Msym n| ≤ nn/2. n. Again, by Hadamard’s inequality Conjecture 6.5. With probability 1 − o(1) | det Msym n| = n(1/2−o(1))n. Tur´an’s identity no longer holds because of a correlation caused by symmetry. However, one can still show E(det Msym n)2 = n(1+o(1))n. On the other hand, proving a lower bound for | det Mn| was more difficult. The problem of bounding the least singular value from below was solved only recently by Nguyen [51] and Vershynin [76], although, unlike the non-symmetric case, we still do not know the limiting distribution of this parameter. The results by Nguyen and Vershynin, combining with Wigner semi-circle law, confirm Conjecture 6.5 12 Theorem 6.6. With probability 1 − o(1) | det Msym n| = n(1/2−o(1))n. Let us now turn to the related notation of permanent. Recall the formal definition of the determinant of a matrix M (with entries mij , 1 ≤ i, j ≤ n) det M := X π∈Sn The permanent of M is defined as (−1) signπ Yn i=1 miπ(i). PerM := X π∈Sn Yn i=1 miπ(i). (4) It is easy to see that Tur´an’s identity still holds, namely E( PerMn)2 = n!. It suggested that | PerMn| is typically n(1/2−o(1))n. However, this was much harder to prove. The following conjecture, which can be seen as the permanent variant of Koml´os classical result pn = o(1), was open for quite some time Conjecture 6.7. P( PerMn = 0) = o(1). The source of difficulties here is that permanent, unlike determinant, does not admit any good geometric of linear algebraic interpretation. In 2007, Tao and Vu found an entirely combinatorial approach to treat the per manent problem [69], relying on the formal definition (4) and making heavy use of martingale techniques from probabilistic combinatorics. They proved Theorem 6.8. With probability 1 − o(1) | PerMn| = n(1/2−o(1))n. The still missing (final) piece of the picture is the symmetric counterpart of The orem 6.8. Conjecture 6.9. With probability 1 − o(1) | PerMsym n| = n(1/2−o(1))n. 13 Motivated by the singularity problem, it is also interesting to find a strong esti mate for the probability that the permanent is zero. The current bound is only polynomial in n. There are further studies concerning the distributions of log | det Mn| and log | det Msym see [31, 30, 54, 63] and the references therein. 7. Graph expansion and the second eigenvalue Let G be a connected graph on n points and A its adjacency matrix with eigenvalues λ1 ≥ λ2 ≥ · · · ≥ λn. If G is d-regular then λ1 = d and by Perron-Frobenius theorem no eigenvalue has larger absolute. A parameter if fundamental interest is λ(G) := max |λi| 0, tồn tại vô số số hữu tỉ p q2 Q sao cho:ˇˇˇˇx pqˇˇˇˇ< ": Vậy ta có thể lượng hóa được độ dày đặc của tập số hữu tỉ trong tập số thực không? Để làm được như vậy, ta cần phải có cách đo độ phức tạp của các số hữu tỉ, và ước lượng mức độ dày đặc của tập số hữu tỉ theo độ phức tạp ấy. Lưu ý rằng vì ta đo độ dày đặc, nên với mỗi số hữu tỉ pq, độ lớn của mẫu số q đóng vai trò quan trọng hơn là tử số p. Vì thế một trong những cách đơn giản nhất để đo độ phức tạp của phân số pqlà giá trị tuyệt đối jqj của mẫu số. Để cho đơn giản, ta sẽ giả sử là phân số pqcó mẫu số dương q > 0. Vì hai phân số có mẫu số bằng q liên tiếp cách nhau đúng bằng 1q, ta có được: Quan sát 1.3. Với mọi số vô tỉ x 2 R X Q, tồn tại vô số số hữu tỉ pq2 Q với q > 0 sao cho: ˇˇˇˇx pqˇˇˇˇ<12q: Câu hỏi tiếp theo được đặt ra là: hàm số 12q trong Quan sát 1.3 đã là tối ưu chưa? Hay nói một cách khác, ta có thể xấp xỉ số vô tỉ tốt hơn Quan sát 1.3 được không? Nhà toán học vĩ đại Leonhard Euler đã trả lời câu hỏi này vào năm 1748 khi ông phát triển lý thuyết về liên phân số với định lý sau đây: Định lý 1.4 (Euler 1748 [3]). Với mọi số vô tỉ x 2 R X Q, tồn tại vô số số hữu tỉ pq2 Q với q > 0 sao cho:ˇˇˇˇx pqˇˇˇˇ<1q2: (1.1) 25 Tạp chí Epsilon, Số 04, 08/2015 Lưu ý 1.5. Định lý 1.4 thường được gọi là Định lý Dirichlet theo tên của nhà toán học Peter Gustav Lejeune Dirichlet mặc dù ông chứng minh lại kết quả này gần 100 năm sau Euler. Tuy nhiên cách chứng minh của Dirichlet vừa đơn giản hơn, vừa giúp mở rộng Định lý 1.4 ra các không gian khác. Chúng ta sẽ quay trở lại với phương pháp của Dirichlet sau. Trong các phần tiếp theo, chúng ta sẽ giới thiệu về liên phân số, một trong những công cụ mạnh nhất của lý thuyết xấp xỉ Diophantine trên tập số thực R, và chứng minh Định lý 1.4. Liên phân số đã được đề cập đến trong số đầu tiên của Epsilon bởi Nguyễn Hùng Sơn [8]. Một số tài liệu tham khảo khác của phần này: Davenport [1, Chương IV], Hardy & Wright [4, Chương X], Khintchine [6], Niven & Zuckerman [9, Chương 7], và Schmidt [10, Chương I]. 2. Liên phân số đơn hữu hạn và số hữu tỉ Một liên phân số hữu hạn có độ dài .n C 1/ là một biểu thức có dạng: Œa0I a1; :::; an WD a0 C1 : a1 C1 a2 C1 ::: C1an với một dãy số thực hữu hạn a0 2 R, a1; a2; :::; an 2 R X f0g. Khi a0 2 Z, a1; :::; an 2 N, ta gọi biểu thức dạng như trên là một liên phân số đơn hữu hạn. Tuy trông có vẻ phức tạp, nhưng thật ra liên phân số đơn hữu hạn bắt nguồn từ thuật toán chia số nguyên Euclid như sau: Xét phân số pqở dạng tối giản, đặt u0 D p, u1 D p và áp dụng thuật toán Euclid, ta có được: u0 D u1a0 C u2 ;1 u2 < u1 u1 D u2a1 C u3 ;1 u3 < u2 ::: un1 D unan1 C unC1 ;1 unC1 < un un D unC1an Với 0 i n, đặt i Dui uiC1, ta có được mối quan hệ sau đây: i D ai C1 iC1với 0 i n 1; và n D an: Thay thế lần lượt vào phân số ban đầu, ta sẽ có: qD 0 D a0 C1 1D a0 C1 a1 C1 2D D a0 C1 p a1 C1 a2 C1 ::: C1an D Œa0I a1; :::; an: Lưu ý 2.1. Định nghĩa trên của itương đương với i D ŒaiI aiC1; :::; an. 26 Tạp chí Epsilon, Số 04, 08/2015 Bài tập 2.2. Áp dụng phép chia Dirichlet để viết các phân số 355 113 và 113 số đơn hữu hạn. 355 thành các liên phân Bài tập 2.3. Cho a0 là một số thực, a1; :::; an, và c là các số thực > 0. So sánh Œa0I a1; :::; an C c với Œa0I a1; :::; an. Bổ đề 2.4. Một số tính chất của liên phân số hữu hạn: (i) Với mọi 1 m n: Œa0I a1; :::; an D Œa0I a1; :::; am1; ŒamI amC1; :::; an. (ii) Trong liên phân số đơn Œa0I a1; :::; an, nếu như an > 1 thì: Œa0I a1; :::; an D Œa0I a1; :::; an 1; 1: Như vậy, (hiển nhiên) mỗi liên phân số đơn hữu hạn cho ta một số hữu tỉ, và theo chiều ngược lại, mỗi số hữu tỉ ngoài 0 và 1 cho ta ít nhất 2 liên phân số. Và thực chất đấy là 2 cách duy nhất để biểu diễn một số hữu tỉ dưới dạng liên phân số đơn hữu hạn: Định lý 2.5. Cho 2 liên phân số đơn hữu hạn bất kỳ Œa0I a1; :::; an và Œb0I b1; :::; bm sao cho an > 1 và bm > 1. Nếu như Œa0I a1; :::; an D Œb0I b1; :::; bm thì n D m và ai D bi với mọi i D 0; 1; :::; n. Chứng minh. Với 0 i n và 0 j m, đặt: i D ŒaiI aiC1; :::; an và j D Œbj I bjC1; :::; bm: Khi ấy, giả thuyết Œa0I a1; :::; an D Œb0I b1; :::; bm có thể được viết lại thành 0 D 0. Vì i D ai C 1 iC1với 0 i n 1, và n D an: iC1 > 1 và ai D b ic với mọi 0 i n 1: Tương tự: iC1 > 1 và bi D bic với mọi 0 i m 1: Giả sử với một 0 i < min fn; mg bất kỳ sao cho i D i, ta có được: ai D b ic D bic D bi và1 iC1D i ai D i bi D1iC1: Điều đó dẫn đến: iC1 D iC1 và aiC1 D biC1. Theo quy nạp, ta có được i D i và ai D bi với mọi 0 i min fn; mg. Giả sử như n > m. Khi đấy m D am C1 mC1> am D bm D m trái với điều ta vừa chứng minh. Vậy n D m và ai D bi với mọi 0 i n. Áp dụng định lý trên, ta có được mối tương quan giữa số hữu tỉ và liên phân số đơn hữu hạn như sau: Định lý 2.6. Mỗi liên phân số đơn hữu hạn đại diện cho 1 số hữu tỉ, và ngược lại, mỗi số hữu tỉ khác 0 và 1 có thể được biểu diễn bằng đúng 2 liên phân số đơn hữu hạn. 27 Tạp chí Epsilon, Số 04, 08/2015 3. Liên phân số đơn vô hạn và số vô tỉ Cho một dãy a0; a1; a2; ::: với a0 2 Z, ai 2 N với mọi i 1. Để định nghĩa được liên phân số đơn vô hạn, đầu tiên ta phải chứng minh rằng dãy các liên phân số đơn hữu hạn tạo bởi n phần tử đầu tiên hội tụ. Với mọi n 0, liên phân số đơn hữu hạn Œa0I a1; :::; an được gọi là phân số hội tụ thứ n . Tử số và mẫu số của phân số hội tụ thứ n có thể được tính theo công thức quy hồi như sau:p2 D 0; p1 D 1; pi D aipi1 C pi2 ; với i 0 q2 D 1; q1 D 0; qi D aipi1 C pi2 ; với i 0(3.1) Bổ đề 3.1. Với mọi n 0,pn qnD Œa0I a1; :::; an: Chứng minh. Ta sẽ chứng minh bổ đề bằng quy nạp theo độ dài n. Dễ dàng có thể kiểm tra được điều kiện ban đầu cho n D 0 và n D 1. Giả sử bổ đề đúng cho mọi liên phân số đơn hữu hạn với độ dài n D k. Gọi pn; qn có được từ công thức (3.1) với dãy a0; a1; ::: và p0n; q0ndựa theo dãy a1; a2; :::. Bài tập 3.2. Chứng minh rằng với mọi n 1, pn D a0p0n1 C q0n1và qn D p0n1: Bài tập 3.3. Áp dụng Bài tập 3.2 để chứng minh Bổ đề 3.1. Bài tập 3.4. Tìm tất cả các phân số hội tụ của 4313 . Bổ đề 3.5. (i) Với mọi n 0: qnD.1/n pn pnC1qn pnqnC1 D .1/nvàpnC1 qnC1 (ii) Với mọi n 0: qnqnC1: pnC2qn pnqnC2 D .1/nan vàpnC2 qnD.1/nan qnqnC2: Bài tập 3.6. Chứng minh bổ đề 2.6. qnC2 pn Một số hệ quả đơn giản nhưng quan trọng của Bổ đề 3.5 như sau: Hệ quả 3.7. (i) Với mọi n 0, pn và qn nguyên tố cùng nhau, hay nói cách khác, phân số pn tối giản. (ii) Dãy các phân số hội tụ thỏa mãn tính chất sau: p0 q0 1 và anC1 D b nC1c 1 với mọi n 0: Áp dụng đẳng thức: n D an C 1 nC1, ta có được: D Œa0I a1; :::; an; nC1 với mọi n 0: Áp dụng bài tập 2.3, khi n là một số chẵn, < a0I a1; :::; an C1 nC1 D Œa0I a1; :::; an; nC1 < Œa0I a1; :::; an; anC1 : 29 Tạp chí Epsilon, Số 04, 08/2015 và tương tự với n lẻ: Œa0I a1; :::; an > > Œa0I a1; :::; anC1: Theo định lý kẹp của giới hạn, D lim n!1Œa0I a1; :::; an D Œa0I a1; a2; :::: Bài tập 3.11. Với ký hiệu như trong Bổ đề 3.10, chứng minh rằng với mọi n 0: D nC1pn C pn1 nC1qn C qn1: Bổ đề 3.12. Với mọi dãy số a0; a1; ::: với a0 2 Z, an 2 N, n 1, Œa0I a1; ::: là một số vô tỉ. Chứng minh. Giả sử như Œa0I a1; ::: Dpqlà một số hữu tỉ, p; q 2 Z. Khi đấy theo phần (ii) của Hệ quả 3.7 vả Bổ đề 3.5, với mọi n 0: 0 < ˇˇˇˇpqpn qn ˇˇˇˇ<ˇˇˇˇpnC1 qnC1 pn qn ˇˇˇˇ D1 qnqnC1: Điều đó dẫn đến: 0 < jqnp pnqj a1 1, a0 < < a0 C 1, ta có được: a0 D b c. Tương tự với liên phân số Œb0I b1; :::: b0 D b c và D b0 C1 Œb1I b2; :::: Kết hợp lại, ta có được: a0 D b0 và Œa1I a2; ::: D Œb1I b2; :::: Áp dụng quy nạp, an D bn với mọi n 0. 30 Tạp chí Epsilon, Số 04, 08/2015 Sử dụng mối tương quan giữa liên phân số đơn và tập số thực, ta có thể chứng minh Định lý 1.4: Theorem 1.4 Với mọi số vô tỉ x 2 R X Q, tồn tại vô số số hữu tỉ pq2 Q với q > 0 sao cho: ˇˇˇˇx pqˇˇˇˇ<1q2: Chứng minh. Theo Định lý 3.9, số vô tỉ x có thể được biểu diễn bằng duy nhất một liên phân số đơn vô hạn: x D Œa0I a1; :::: Gọi pn qnlà phân số hội tụ thứ n của x. Theo Định lý 3.8 và phần (ii) của Hệ quả 3.7, ˇˇˇˇx pn qn ˇˇˇˇ<ˇˇˇˇpn qn D1 pnC1 qnC1 ˇˇˇˇ qnqnC1.theo phần (i) của Bổ đề 3.5/ <1q2n.theo (3.1)/: Theo phần (i) của Hệ của 3.7, tất cả các phân số hội tụ pn phân số thỏa mãn Định lý 1.4. 4. Phân số xấp xỉ tốt nhất qnđều khác nhau, và ta có được vô số Gọi x 2 R X Q là một số vô tỉ bất kì. Các phân số hội tụ của x không hội tụ về x một cách ngẫu nhiên, mà lần lượt tiến gần x hơn: Bổ đề 4.1.ˇˇˇˇx p0 q0 ˇˇˇˇ>ˇˇˇˇx p1 q1 ˇˇˇˇ>ˇˇˇˇx p2 q2 ˇˇˇˇ> ::: Chứng minh. Giả sử x có mở rộng liên phân số đơn x D Œa0I a1; a2; :::, và pn hội tụ của x. Đặt xn D ŒanI anC1; anC2; ::: như trong Bổ đề 3.10, ta có được: qnlà các phân số ˇˇˇˇx pn qn ˇˇˇˇ DˇˇˇˇxnC1pn C pn1 xnC1qn C qn1 D1 pn qn ˇˇˇˇ.Bài tập 3.11/ qn .xnC1qn C qn1/.Bổ đề 3.5/ >1 qn ..anC1 C 1/ qn C qn1/.xnC1 < anC1 C 1/ D1 qn .qnC1 C qn/(3.1) 1 qn .anC1qnC1 C qn/.an 1/ D1 qnqnC2>1 qnC1qnC2> ˇˇˇˇx pnC1 qnC1 31 ˇˇˇˇ: Tạp chí Epsilon, Số 04, 08/2015 Phân số pq(q > 0) được gọi là phân số xấp xỉ tốt nhất của x nếu như với mọi phân số rs(s > 0): ˇˇˇx rsˇˇˇ<ˇˇˇˇx pqˇˇˇˇH) s > q: Định lý 4.2. Phân số hội tụ pn qncủa x là phân số xấp xỉ tốt nhất của x. Để chứng minh Định lý 4.2, ta sẽ dùng bổ đề sau: Bổ đề 4.3. Nếu như hai số nguyên p; q với q > 0 thỏa mãn: jxq pj < jxqn pnj ; thì q qnC1. Lời giải. Ta sẽ chứng minh bằng phản chứng. Giả sử như q < qnC1. Xét ma trận với hệ số nguyên: pn pnC1 qn qnC1 : Theo Bổ đề 3.5, định thức của ma trận này là ˙1. Vì thế hệ phương trình tuyến tính: pn pnC1 qn qnC1 y z D p q có nghiệm nguyên .y; z/ ¤ .0; 0/. Hơn nữa, z ¤ 0 vì pq ¤pn q D zqnC1 qnC1 trái với giả thuyết q < qnC1. Vậy y ¤ 0. qn. Mặt khác, nếu y D 0 thì Vì q D yqn C zqnC1 < qnC1, y và z trái dấu với nhau. Theo phần (ii) của Hệ quả 3.7, y .xqn pn/ và z .xqnC1 pnC1/ có cùng dấu, và ta có được: jxq pj D jx .yqn C zqnC1/ .ypn C zpnC1/j D jy .xqn pn/ C z .xqnC1 pnC1/j D jy .xqn pn/j C jz .xqnC1 pnC1/j > jxqn pnj trái với giả thuyết. Vậy q qnC1. Chứng minh Định lý 4.2. Vì x là số vô tỉ, nên không tồn tại một số hữu tỉ pq ¤pn ˇˇˇˇx pqˇˇˇˇ Dˇˇˇˇx pn ˇˇˇˇ: qn Giả sử như tồn tại pq(q > 0) sao cho: qnvới: ˇˇˇˇx pqˇˇˇˇ<ˇˇˇˇx pn qn Nhân cả hai bất phương trình trên dân đến: ˇˇˇˇvà q qn: jxq pj < jxqn pnj : Theo Bổ đề 4.3, q qnC1 > qn trái với giả thuyết. Vậy pn qnlà phân số xấp xỉ tốt nhất của x. 32 Tạp chí Epsilon, Số 04, 08/2015 Theo chiều ngược lại, Định lý sau chỉ ra rằng khi một phân số xấp xỉ x ‘đủ gần’ thì phân số đó phải là một phân số hội tụ của x: Định lý 4.4. Nếu như số hữu tỉ pq(q > 0) thỏa mãn: ˇˇˇˇx pqˇˇˇˇ<12q2; thì tồn tại một phân số hội tụ pn qnDpq. Lời giải. Giả sử mọi phân số hội tụ của x đều không bằng pq. Gọi n là số nguyên dương sao cho qn b < qnC1. Theo Bổ đề 4.3: jxqn pnj jxq pj <12q: Từ đó ta suy ra: 1 qqn jqpn pqnj qqnD ˇˇˇˇpn qn p q ˇˇˇˇ ˇˇˇˇx pn qn ˇˇˇˇCˇˇˇˇx pn ˇˇˇˇ qn 2qqnC12q2 <1 Điều này dẫn đến q < qn, trái với giả thuyết. Vậy pq Dpn qnvới n 0 nào đó. 5. Số mũ Dirichlet tối ưu và Số xấp xỉ kém Trở lại về tính tối ưu của Định lý 1.4, ta có thể đặt câu hỏi cụ thể hơn như sau: Liệu hàm số q2 trong Định lý 1.4 có thể được thay thế bởi một hàm số theo q khác tiến về 0 nhanh hơn khi q tiến ra vô cùng hay không? Câu trả lời cho câu hỏi trên là không, hay nói cách khác, số mũ 2 trong Định lý 1.4 là tối ưu. Chúng ta sẽ chứng minh điều này bằng sự tồn tại của các số xấp xỉ kém được định nghĩa như sau: Số vô tỉ x 2 R X Q được gọi là một số xấp xỉ kém nếu như tồn tại một hằng số c > 0 (có thể phụ thuộc vào x) sao cho với mọi phân số pq: ˇˇˇˇx pqˇˇˇˇ>cq2: (5.1) Định lý 5.1. Tồn tại vô số số xấp xỉ kém. Định lý 5.1 có thể được suy ra bởi mối liên hệ giữa số xấp xỉ kém và liên phân số đơn như sau: Định lý 5.2. Số vô tỉ x 2 R X Q là một số xấp xỉ kém khi và chỉ khi mở rộng liên phân số đơn của x bị chặn. Nói cách khác, tồn tại M > 0 sao cho an < M với mọi n 0 với x D Œa0I a1; a2; :::. 33 Tạp chí Epsilon, Số 04, 08/2015 Ta sẽ dùng Bổ đề sau để chứng minh Định lý 5.2: Bổ đề 5.3. Với mọi n 0: 1 q2n.anC1 C 2/< ˇˇˇˇx pn qn ˇˇˇˇ<1 q2nanC1: Lời giải. Theo như tính toán như trong phần chứng minh của Bổ đề 4.1: ˇˇˇˇx pn ˇˇˇˇ D1 qn .xnC1qn C qn1/D1 q2nxnC1 1 <1 q2nanC1: qn q2n Mặt khác, xnC1 Cqn1 qn ˇˇˇˇx pn ˇˇˇˇ>1 qn Œ.anC1 C 1/ qn C qn1D1 >1 qn q2n anC1 C 1 Cqn1 qn q2n.anC1 C 2/: Chứng minh Định lý 5.2. Giả sử như x D Œa0I a1; a2; ::: là một số xấp xỉ kém, với mọi n 0, ta có được: c q2n< ˇˇˇˇx pn qn ˇˇˇˇ<1 q2nanC1: Từ đó dẫn đến mở rộng liên phân số của x bị chặn: a0;1c : sup n 0 an max Theo chiều ngược lại, giả sử như x không phải là một số xấp xỉ kém. Điều đấy tương đương với tồn tại các dãy số ci > 0; risisao cho: i!1ci D 0 và lim ˇˇˇˇx risiˇˇˇˇ ci q2i: Không mất tính tổng quát, ta có thể đặt giả thiết là ci <12. Theo Định lý 4.4,risiDpn phân số hội tụ của x. Vì vậy: 1 q2n.anC1 C 2/< ˇˇˇˇx pn qn qnlà một ˇˇˇˇ ci q2n: Từ đó suy ra: anC1 >1ci 2: Vế phải ! 1 khi i ! 1, hay nói cách khác, dãy an không bị chặn. Ta có được điều phải chứng minh. Hệ quả 5.4. Tập các số xấp xỉ kém là không đếm được . Ví dụ cụ thể và gần gũi nhất về các số xấp xỉ kém là các số đại số bậc 2 như p2; 1Cp5 2; :::: Định lý 5.5 (Lagrange 1770 [7]). Số vô tỉ x là số đại số bậc 2 khi và chỉ khi mở rộng liên phân số của x là vô hạn tuần hoàn . Lưu ý 5.6. Mệnh đề đủ trong Định lý 5.5 đã được chứng minh trước đấy bởi Euler [2]. Chiều khó hơn là mệnh đề cần được Lagrange chứng minh trong [7]. 34 Tạp chí Epsilon, Số 04, 08/2015 6. Hàm số Dirichlet tối ưu Trong phần trước, chúng ta đã chứng minh rằng phần q2trong Định lý 1.4 là không thể cải thiện được. Tuy nhiên, hằng số 1 có thể được thay thế bằng một hằng số khác nhỏ hơn với kết quả sau của Hurwitz: Định lý 6.1 (Hurwitz 1891 [5]). Với mọi số vô tỉ x 2 R X Q, tồn tại vô số số hữu tỉ pq2 Q với q > 0 sao cho:ˇˇˇˇx pqˇˇˇˇ<1 p5q2: (6.1) p51 Lưu ý 6.2. Định lý 6.1 thật sự là tối ưu vì với x D 2, và với mọi hằng số 0 < C < p15, chỉ tồn tại hữu hạn số hữu tỉ pq2 Q, q > 0 thỏa mãn bất phương trình: ˇˇˇˇx pqˇˇˇˇ qn1 qn> qn2 2: p5 1 2: p5 1 qn1 qn1<2 p5 1 2D 1 (vô lý): Vậy với mọi n 2, ít nhất 1 trong 3 phân số hội tụ pn2 qn2;pn1 qn1;pn qnthỏa mãn bất đẳng thức (6.1). Tài liệu tham khảo [1] Davenport, H., The higher arithmetic, 7th ed., Cambridge University Press (1999). [2] Euler, L., De fractionibus continuis, Commentarii Acad. Sci. Imperiali Petropolitanae 9 (1737). [3] Euler, L., Introductio in analysin infinitorum I, (1748). [4] Hardy, G., Wright, E. M., An introduction to the theory of numbers, 5th ed., Clarendon Press (1979). [5] Hurwitz, A., Uber die angen ¨ aherte Darstellung der Irrationalzahlen durch rationale ¨ Bruche ¨ , Math. Ann. 39, pp 279–284. [6] Khintchine, A., Continued fractions, (1964). [7] Lagrange, J. L., Additions au mémoire sur la résolution des équations numériques, Mém. Berl. 24 (1770). [8] Nguyễn Hùng Sơn, Thuật toán phục hồi số hữu tỉ, Epsilon 1, (2015). [9] Niven, I., Zuckerman, H. S., An introduction to the theory of number, 4th ed., John Wiley & Sons (1980). [10] Schmidt, W. M., Diophantine approximation, Lectures Notes in Mathematics 785, Springer (1980). 36 BIỂU DIỄN NGHĨA CỦA TỪ BẰNG VÉC-TƠ Lê Phong (Đại học Amsterdam, Hà Lan) Tuy rằng thời điểm chúng ta có thể tạo ra những cỗ máy có trí tuệ như người chắc chắn sẽ không đến trong nay mai, việc làm cho máy tính hiểu được những gì chúng ta nói đã đạt được một số đột phá nhất định. Bài viết này sẽ giới thiệu một hướng nghiên cứu mà trong đó ngữ nghĩa của từ được biểu diễn bằng véc-tơ, từ đó tạo nền tảng cho việc xây dụng một hệ thống hoàn chỉnh có thể tự động giao tiếp với con người. 1. Máy hiểu Tiếng người 01 Con người đã chế tạo được những cỗ máy thám hiểm Sao Hoả, lặn xuống nơi sâu nhất đại dương, hay có khả năng tính toán siêu việt. Thế nhưng việc xây dựng trí tuệ nhân tạo thông minh như con người vẫn chỉ mới tồn tại trên phim ảnh, tiểu thuyết. Nói như thế không có nghĩa là điều đó không thể: máy tính chúng ta chế tạo ngày càng mạnh mẽ hơn, thông minh hơn. Một số nhà tương lai học, nổi bật là Ray Kurzweil, tin rằng thời điểm ra đời của trí tuệ nhân tạo đang đến rất gần [5]. Tuy nhiên, làm thế nào để biết được một cỗ máy có trí tuệ như chúng ta? Đây là một câu hỏi mang tính triết học hơn là khoa học kỹ thuật. Alan Turing, cha đẻ của ngành khoa học máy tính, đã đề xuất một bài kiểm tra [9] (vì thế mang tên là Turing test) dựa trên trò chơi “bắt chước” (imitation game)1. Bài kiểm tra này có thể mô tả nôm na như sau: có một máy tính A và hai người B, C. Người C không nhìn thấy và không biết A, B. Người C có thể giao tiếp với A và B thông qua gõ bàn phím. Sau khi giao tiếp xong mà C không thể phân biệt được đâu là máy tính, đâu là người thì máy tính A có thể coi là có trí tuệ như người. Điều lẽ dĩ nhiên là có nhiều người không đồng tình với bài kiểm tra này. Một trong những lý do là tâm lý con người có thể bị đánh lừa bằng những mánh khoé hết sức đơn giản như là cố tình đưa ra những từ sai chính tả. Điều đáng nói ở đây là, nếu nhìn theo khía cạnh khoa học, một cỗ máy có trí tuệ nhân tạo thì phải hiểu được con người nói gì và sinh ra được lời đối đáp thích hợp. Chế tạo được cỗ máy như vậy là một trong những mục đích tối thượng của ngành Xử lý ngôn ngữ tự nhiên (Natural language processing). Một ngôn ngữ (viết) là một tập hợp các chuỗi ký hiệu, cấu thành bằng việc kết nối các từ trong một tập từ vựng thông qua một bộ các nguyên tắc ghép từ, được gọi là ngữ pháp. Do đó, để có thể làm cho máy tính hiểu được ngôn ngữ, điều đầu tiên chúng ta có thể nghĩ đến là làm sao cho máy tính hiểu được nghĩa của các từ. Ví dụ như làm sao nó có thể hiểu được rằng “chó” và “mèo” là tên của hai loài động vật có bốn chân, có những hành vi tương đồng như ăn, ngủ, chạy, nhảy. Về mặt lý thuyết, chúng ta có thể mô tả nghĩa của từ cho máy tính hiểu bằng việc liệt kê 1“Imitation game” cũng là tên của một bộ phim kể về cuộc đời của Alan Turing. Ông đã giúp quân Đồng Minh giải mã những thông điệp của quân Đức trong Thế chiến thứ hai. Nhờ vậy mà chiến tranh đã được kết thúc sớm, giúp cứu sống rất nhiều sinh mệnh. 37 Tạp chí Epsilon, Số 04, 08/2015 các đặc tính được kể ở trên. Về mặt thức tế, công việc như vậy đòi hỏi phải có những chuyên gia về ngôn ngữ học, khiến cho tốn rất nhiều thời gian và tiền bạc. Một trong những hướng giải quyết thông dụng bây giờ là tận dụng một lượng đồ sộ các văn bản có sẵn trên Internet để tự động xây dựng nghĩa cho các từ. Bài viết này sẽ giới thiệu một hướng nghiên cứu như vậy, được gọi là Distributional semantics2. Bạn đọc sẽ thấy rằng, chỉ với một vài công cụ toán hết sức đơn giản, một lý thuyết về ngữ nghĩa học hợp lý, và một lượng lớn văn bản, chúng ta có thể làm được những thứ hết sức hữu dụng. 2. Distributional semantics Câu hỏi trước tiên cần phải giải đáp chính là: cái gì quyết định nghĩa của từ? John Rupert Firth năm 1957 đề xuất một quan điểm mà bây giờ trở thành “phương châm” để giải quyết vấn đề tự động học nghĩa của từ: You shall know a word by the company it keeps [4] nghĩa là: nghĩa của một từ có thể được nhận biết bằng các từ đi kèm với nó. Để có thể hiểu được ý của Firth, chúng ta có thể hình dung một tình huống như sau: giả sử như chúng ta đang đọc một cuốn sách bằng tiếng Anh và gặp một từ rất lạ “bardiwac” lặp đi lặp lại nhiều lần: He handed her her glass of bardiwac. Beef dishes are made to complement the bardiwac. Nigel staggered to his feet, face flushed from too much bardiwac. Malbec, one of the lesser-known bardiwac grapes, responds well to Australia’s sunshine. I dined off bread and cheese and this excellent bardiwac. The drinks were delicious: blood-red bardiwac as well as light, sweet Rhenish. Điều đáng nói ở đây là chúng ta hoàn toàn có thể đoán được nghĩa của từ này bằng cách suy đoán dựa trên ngữ cảnh của nó. Từ câu đầu tiên, chúng ta có thể đoán rằng “bardiwac” là một thứ chất lỏng. Câu thứ hai gợi ý rằng từ này chỉ một thứ được dùng kèm khi ăn thịt bò. Với câu thứ ba, từ này dường như có nghĩa là một thứ khiến ta có thể say, vân vân... Và khi tổng hợp lại, chúng ta có thể đoán rất chính xác rằng “bardiwac” là một loại rượu đỏ được làm từ nho. Tất nhiên, vì chúng ta có trí tuệ nên có thể dễ dàng đoán được nghĩa của một từ lạ thông qua ngữ cảnh. Còn đối với máy tính thì sao? Làm cách nào chúng ta có thể nói với nó rằng hãy dùng ngữ cảnh để học nghĩa của từ? Trong hai mục tiếp theo sau, hai phương pháp thông dụng là Đếm và Đoán sẽ được trình bày. 2Có thể dịnh là “Ngữ nghĩa có tính phân bố”. 38 Tạp chí Epsilon, Số 04, 08/2015 Hình 3.1: Xây dựng véc-tơ nghĩa của từ “bathtub” bằng phương pháp đếm (hình lấy từ [3]). 3. Phương pháp 1: Đếm Trước tiên, chúng ta cần phải làm rõ khái niệm “ngữ cảnh” cho máy tính hiểu. Nôm na mà nói, ngữ cảnh là tất cả những gì xuất hiện xung quanh đối tượng cần quan tâm. Ở đây, chúng ta sẽ giới hạn “ngữ cảnh” là tập hợp những từ nằm trong cùng một câu với đối tượng, hoặc là những từ nằm trước đối tượng và nằm sau đối tượng không quá k vị trí. Gọi V là tập từ vựng. Cách đơn giản, và cũng rất cổ điển, là thống kê các từ u 2 V xuất hiện kèm theo từ w 2 V mà ta quan tâm. Điều này tương đương với việc ước lượng phân bố xác suất có điệu kiện P .U D ujW D w/ thể hiện khả năng từ u thuộc ngữ cảnh của từ w. Để làm được như vậy, với mỗi từ u, ta đếm xem u xuất hiện bao nhiêu lần kèm theo từ w (vì thế phương pháp này có tên gọi là co-occurrence count3). Ví dụ minh họa được cho trong Hình 3.1. Có ba bước để biểu diễn nghĩa của từ w bằng véc-to. Trước hết, chúng ta thu thập các câu có chứa từ w. Sau đó, với mỗi từ u ta đếm xem nó thuộc về ngữ cảnh của từ w bao nhiêu lần. Và cuối cùng, chúng ta trích ra véc-tơ cho từ w. Ước lượng xác suất trở nên đơn giản là P .U D ujW D w/ Dsố lần u thuộc về ngữ cảnh của w số lần w xuất hiện trong toàn bộ dữ liệu (3.1) Tuy nhiên, để thu được các véc-tơ tốt, có nhiều điều chúng ta cần phải xem xét. Thứ nhất, u nên là những từ như thế nào. Rõ ràng là những từ chức năng (functional words) (như “a”, “an”, “the”, “how”, “whom”) (trong tiếng Việt thì có “ai”, “rằng”, “thì”, “là”, “mà”) có tần suất xuất 3Có thể dịch là “đếm từ đồng xuất hiện” 39 Tạp chí Epsilon, Số 04, 08/2015 hiện rất cao nhưng lại mang thông tin cú pháp hơn là ngữ nghĩa. Vì thế, u không nên là một trong những từ đó. Kế tiếp, với cách đếm này, chúng ta xem các từ u có vai trò bình đẳng. Thực tế thì ngược lại vì có những từ mặc dù xuất hiện rất ít nhưng mang thông tin rất quan trọng (ví dụ như động từ thường quan trọng hơn trợ động từ). Để khắc phục điểm này, thông thường người ta áp dụng thêm một bước nữa gọi là đánh trọng số (weighting scheme). Một trong những cách đánh trọng số phổ biến là Pointwise mutual information PMI.u; w/ DP .U D ujW D w/ P .V D u/ (3.2) trong đó P .V D u/ là xác suất xuất hiện của từ u trong toàn bộ dữ liệu. Nói nôm na là các từ hiếm u nên được tăng trọng số lên. Điều này khá là hợp lý bởi vì một từ với tần suất xuất hiện thấp có khả năng gây nhiễu cực thấp. Vì thế khả năng nó mang thông tin để mô tả từ cần quan tâm là lớn. Thực tế là các véc-tơ thu được có số chiều lớn (2000 hoặc hơn) và thưa (vì chúng ta mong muốn dùng những từ hiếm u để tăng thêm thông tin ngữ nghĩa). Vì vậy, một phương pháp giảm số chiều (tương tự như PCA) sẽ được áp dụng sau cuối. 4. Phương pháp 2: Đoán Ý tưởng của phương pháp Đoán thật ra rất giống như chúng ta trả lời câu hỏi chọn từ điền vào chỗ trống trong các bài thi TOEFL hay IELTS: ______ is the study of numbers, equations, functions, and geometric shapes and their relationships. a. physics b. mathematics c. geography d. theology Nếu chúng ta đạt kết quả tốt trong bài kiểm tra thế này (tức là tỉ lệ phần trăm đúng cao hơn rất nhiều so với chọn ngẫu nhiên 25%), người kiểm tra sẽ cho rằng chúng ta hiểu được nghĩa của cả những từ cần được chọn lẫn những từ có mặt trong ngữ cảnh. Tương tự, với phương pháp Đoán, nếu các véc-tơ của các từ có thể giúp chúng ta làm tốt các câu hỏi như trên, các véc-tơ này được cho là thể hiện được nghĩa của các từ mà chúng biểu diễn. Bây giờ chúng ta giả sử rằng mỗi từ v 2 V được biểu diễn bởi một véc-tơ d-chiều v, và chúng ta có một cách nào đó để tính xác suất P .W D wjU D .u1; u2; :::; ul// thể hiện khả năng từ w xuất hiện trong ngữ cảnh .u1; u2; :::; ul/. Điều chúng ta cần làm là đi tìm véc-tơ v cho mỗi từ v sao cho xác suất ở trên là cao nhất với mọi từ w và ngữ cảnh của nó .u1; u2; :::; ul/. Có nhiều phương pháp được đề xuất để tính P .W jU/, ở đây, phương pháp của [2]4sẽ được trình bày. Trước tiên, chúng ta kết hợp véc-tơ của các từ u1; :::; ulthuộc ngữ cảnh vào một véc-tơ x như sau: x D tanh.b C V1u1 C ::: C Vlul/ (4.1) 4Phương pháp này liên quan tới mạng nơ-ron nhân tạo. Để tránh phải giới thiệu thêm khái niệm mới, chỉ có dạng công thức toán được trình bày. 40 Tạp chí Epsilon, Số 04, 08/2015 trong đó mỗi Vilà một ma-trận n d và b là một véc-tơ n-chiều; hàm hyperbolic tanh được áp dụng cho mỗi phần tử của véc-tơ đối số tanh 0 BB@y1 y2 ::: yn 1 CCA D 0 [email protected]/ tanh.y2/ ::: tanh.yn/ 1 CCA(4.2) Tiếp theo, chúng ta chiếu x lên một không gian véc-tơ có số chiều bằng đúng jVj, số lượng từ có trong tập từ vựng: a D c C Wx (4.3) Cuối cùng, dùng hàm sof tmax, chúng ta tính xác suất để wk, từ thứ k trong tập từ vựng V, xuất hiện trong ngữ cảnh .u1; :::; ul/ P .W D wkjU D .u1; u2; :::; ul// D sof tmax.k; a/ Deak iD1eai(4.4) PjVj Bây giờ, gọi D hw1; :::; wjVj; V1; :::; Vl; b; W; ci. Bởi vì mục đích cuối cùng là dự đoán đúng từ khi biết ngữ cảnh, chúng ta đi tìm sao cho có được log-likelihood (log của độ tương đồng) lớn nhất L. / DX w;.c1;:::;cl / logP .W D wjU D .u1; :::; ul// (4.5) trong đó tổng được tính trên tất cả các ngữ cảnh và từ xuất hiện trong ngữ cảnh đó có thể tìm được trong văn bản dữ liệu. Đến đây chúng ta có bài toán tìm cực trị hàm đa biến quen thuộc. 5. Tính chất và Ứng dụng Liệu rằng khi nhìn vào các véc-tơ này, máy tính có thể biết được rằng “chó” và “mèo” đều có bốn chân, “chó” sủa gâu gâu còn “mèo” kêu meo meo? Câu trả lời có lẽ là “Không!”, hoặc là rất khó để biết được. Tuy nhiên, điều đó không có nghĩa véc-tơ từ là vô dụng. Ngược lại, người ta nhận thấy rằng, các véc-tơ này cho chúng ta biết một thông tin hết sức quan trọng gọi là “mức độ tương đồng về nghĩa” (semantic similarity). Điều này xuất phát từ Giả thuyết phân bố (Distributional Hypothesis) [6] sau đây: Độ tương đồng về nghĩa giữa hai biểu thức ngôn ngữ A và B là một hàm của độ tương đồng của ngữ cảnh ngôn ngữ mà A và B xuất hiện trong đó. Về mặt lý thuyết, chúng ta có thể sử dụng bất kỳ độ đo khoảng cách giữa hai véc-tơ nào. Trong thực tế, người ta thấy rằng cosine thường cho kết quả tốt nhất (xem Hình 3.2). Khi chiếu các véc-tơ nghĩa của từ lên mặt phẳng 2D dùng phương pháp giảm số chiều (như là PCA), thường chúng ta sẽ thấy các từ có nghĩa tuơng đồng sẽ được gom cụm gần nhau (như Hình 3.3). Do đó, mặc dù máy tính sẽ không biết là chó có bốn chân, mèo kêu meo meo, nhưng mà nó sẽ biết được rằng chó và mèo nằm trong nhóm các động vật có tính chất tương đồng như bò, cọp, heo. Gần đây, [7] dùng một phương pháp tuơng tự như Đoán, đã cho ra bộ véc-tơ mà trong đó một số mối quan hệ về nghĩa có thể được thể hiện thông qua phép tính véc-tơ, nổi bật nhất là: ! ki ng ! queen ! man ! woman (5.1) 41 Tạp chí Epsilon, Số 04, 08/2015 Hình 3.2: Dùng hàm cosine để đo góc giữa hai véc-tơ. Kết quả thu được thể hiện sự tương đồng nghĩa giữa các từ (hình lấy từ [3]). Hình 3.3: Các từ có nghĩa tương đồng thường nằm co cụm gần nhau. 42 Tạp chí Epsilon, Số 04, 08/2015 5.0.0.1 Ứng dụng Distributional semantics có nhiều ứng dụng chủ yếu xuất phát từ tính chất kể trên. Một số được liệt kê dưới đây: xây dựng từ điển đồng nghĩa một cách tự động (điều này đặc biệt có ý nghĩa đối với những ngôn ngữ chưa được nghiên cứu kỹ, như là ngôn ngữ của các dân tộc thiểu số), mở rộng từ khóa tìm kiếm (ví dụ như Google bên cạnh tìm kiếm chính xác từ khóa người dùng nhập vào, sẽ mở rộng tìm kiếm bằng cách thay từ khóa đó bằng những từ gần nghĩa), Đặc biệt, với xu thế ngày càng mở rộng của của deep learning5(dùng các mạng nơ-ron nhân tạo có nhiều lớp), việc dùng véc-tơ nghĩa của từ như xuất phát điểm trở nên vô cùng quan trọng trong rất nhiều ứng dụng như là phân tích cú pháp (syntactic parsing), phân loại văn bản (document classification), phân tích cảm nghĩ (sentiment analysis), dịch máy (machine translation). 6. Bàn luận Ở phần trên đã trình bày hai phương pháp là Đếm và Đoán. Một sự nhẩm tính bình thường cũng có thể thấy rằng Đếm đơn giản hơn rất nhiều so với Đoán. Vì thế mà Đoán mãi gần đây, khi sức mạnh của máy tính tăng lên đáng kể, mới trở nên phổ biến. Đoán thường cho ra véc-tơ với số chiều ít hơn (khoảng 25-500), trong khi Đếm là khoảng 2000 hoặc hơn. Về chất lượng của véc-tơ, [1] đưa ra một số bằng chứng thực nghiệm cho thấy Đoán cho ra véc-tơ tốt hơn Đếm. Tuy nhiên, ngay sau đó, [8] chỉ ra rằng Đếm kết hợp với một phương pháp đánh trọng số thông minh và giảm số chiều hợp lý sẽ cho ra véc-tơ tốt hơn. Bài viết này chỉ trình bày những điều hết sức cơ bản về Distributional semantics. Độc giả có “mắt đại bàng” sẽ thấy rằng còn nhiều thứ có thể mở rộng và còn nhiều việc phải làm để tiếp cận một hệ ngữ nghĩa hoàn chỉnh. Thứ nhất, chúng ta đề cập đến nghĩa của từ dưới một sự ngầm hiểu rằng mỗi từ chỉ có một nghĩa (được biểu diễn bởi một véc-tơ). Tuy nhiên, trong thực tế ta thường bắt gặp những từ có nhiều nghĩa. Các nghĩa này có thể rất khác nhau (đồng âm khác nghĩa), hoặc có thể hơi tương đồng (đồng âm gần nghĩa). Việc có thể xây dựng các véc-tơ khác nhau cho các nghĩa khác nhau một cách tự động gọi là Word sense induction. Thứ hai, khái niệm tương đồng nghĩa nên được hiểu là tương đồng nghĩa trong ngữ cảnh sử dụng. Nhìn vào Hình 3.3 chúng ta có thể thấy rằng những từ trái nghĩa lại rất gần nhau (như là “more” / “less”, “high” / “low”). Điều này là bởi các từ trái nghĩa thường được đặt trong các ngữ cảnh rất giống nhau. Những từ ám chỉ cùng một sự vật như là “water” và “H20” sẽ có véc-tơ rất khác nhau, bởi vì “water” thường được sử dụng trong ngữ cảnh đời thường, trong khi “H20” dùng trong ngữ cảnh khoa học. Thứ ba, mặc dù distributional semantics về mặt lý thuyết có thể mở rộng cho bất kỳ đối tượng ngôn ngữ nào (như là cụm từ, câu), nhưng trong thực tế thì không thể áp dụng cho các cụm từ lớn hoặc câu (xem ví dụ ở Hình 3.4). Để giải quyết vấn đề về nghĩa cho cụm từ và câu, hoặc lớn hơn là đoạn văn bản, người ta thường phải dựa vào Nguyên lý Kết hợp (principle of compositionality). Và việc tìm hàm kết hợp (composition function) là nhiệm vụ của hướng nghiên cứu Distributional Composition semantics. 5Xem giới thiệu về deep learning tại https://en.wikipedia.org/wiki/Deep_learning, và deep learning cho xử lý ngôn ngữ tự nhiên tại http://nlp.stanford.edu/courses/NAACL2013/ NAACL2013-Socher-Manning-DeepLearning.pdf 43 Tạp chí Epsilon, Số 04, 08/2015 Hình 3.4: Với những cụm từ lớn hoặc cả câu, chúng ta không có đủ ngữ cảnh để xây dựng véc-tơ. Ngay cả với kho dữ liệu khổng lồ lớn nhất hiện tại của Google, câu “Bún bò Huế là món ăn Việt Nam” chỉ có duy nhất một ngữ cảnh được tìm thấy. Lời cảm ơn Tác giả chân thành cảm ơn TS. Nguyễn Thị Hồng Nhung (Manchester) đã sửa lỗi và góp ý cho bản thảo. Tài liệu tham khảo [1] Baroni, M., Dinu, G., and Kruszewski, G. (2014). Don’t count, predict! a systematic com parison of context-counting vs. context-predicting semantic vectors. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, volume 1, pages 238–247. [2] Bengio, Y., Ducharme, R., Vincent, P., and Janvin, C. (2003). A neural probabilistic lan guage model. The Journal of Machine Learning Research, 3:1137–1155. [3] Erk, K. (2012). Vector space models of word meaning and phrase meaning: A survey. Language and Linguistics Compass, 6(10):635–653. [4] Firth, J. R. (1957). Papers in Linguistics. Oxford Univeristy Press. [5] Kurzweil, R. (2005). The singularity is near: When humans transcend biology. Penguin. [6] Lenci, A. (2008). Distributional semantics in linguistic and cognitive research. From con text to meaning: Distributional models of the lexicon in linguistics and cognitive science, special issue of the Italian Journal of Linguistics, 20(1):1–31. [7] Mikolov, T., Yih, W.-t., and Zweig, G. (2013). Linguistic regularities in continuous space word representations. In HLT-NAACL, pages 746–751. 44 Tạp chí Epsilon, Số 04, 08/2015 [8] Pennington, J., Socher, R., and Manning, C. D. (2014). Glove: Global vectors for word representation. Proceedings of the Empiricial Methods in Natural Language Processing (EMNLP 2014), 12:1532–1543. [9] Turing, A. M. (1950). Computing machinery and intelligence. Mind, pages 433–460. 45 Tạp chí Epsilon, Số 04, 08/2015 46 MÔ HÌNH HÓA BÀI TOÁN SẮP LỊCH DẠNG FLOWSHOP BẰNG ĐẠI SỐ MAXPLUS Võ Nhật Vinh (Đại học Fran¸cois-Rabelais, Tours, Pháp) Chuyện kể rằng ở một vương quốc nọ, nhà vua có rất nhiều cung tần mỹ nữ và họ đều để tóc dài. Để chăm sóc cho mái tóc dài của các người đẹp, nhà vua ra lệnh cho một xưởng sản xuất dầu gội tin cậy sản xuất các loại sản phẩm khác nhau để đáp ứng nhu cầu của các mỹ nữ này. Hiện tại, nhu cầu của các người đẹp là bốn loại dầu gội mang hương bưởi, hương sen, hương lài và hương chanh. Trong xưởng sản xuất, ba giai đoạn cần được lưu ý theo thứ tự là tách mùi hương, pha trộn mùi và đóng chai. Mỗi loại dầu gội có thời gian đặc trưng để tách mùi hương, để pha trộn mùi và để đóng chai khác nhau. Có thời điểm, xưởng sản xuất quan tâm đến thứ tự các loại dầu gội cần được sản xuất để có thể hoàn thành tất cả các đơn hàng của các người đẹp trong thời gian sớm nhất. Có thời điểm, xưởng sản xuất cân nhắc thứ tự các loại dầu gội để tổng thời gian chờ đợi của các quý bà là ít nhất. Cũng có lúc, xưởng sản xuất phải lưu ý đến vai trò khác nhau của các nhóm người đẹp. Vì vậy, xưởng sản xuất phải suy nghĩ tìm lời giải tối ưu cho từng trường hợp. Trong bài toán miêu tả phía trên, ta có bốn công việc cần hoàn thành (sản xuất bốn loại dầu gội) trên một dây chuyền gồm ba máy (ba bước sản xuất). Nhiệm vụ của xưởng sản xuất là sắp xếp thứ tự các sản phẩm để thời gian hoàn thành cuối cùng là nhanh nhất, hoăc để tổng thời gian hoàn thành tất cả sản phẩm là ngắn nhấn. Khi các nhóm người đẹp có vai trò khác nhau thì các sản phẩm yêu thích của các nhóm sẽ có trọng số khác nhau. 1. Giới thiệu chung Câu hỏi về mối liên hệ giữa các ngành Toán Học, Tin Học và Kinh Doanh đã thúc đẩy tôi nghiên cứu sâu hơn về lý thuyết sắp lịch (scheduling theory). Thực tế, bài toán sắp lịch được nghiên cứu trong các khoa Tin Học bởi vì nó cần các kỹ thuật Tin Học cũng như các tài nguyên máy tính để tìm ra các kết quả số. Tuy vậy, các bài toán sắp lịch lại là những trường hợp cụ thể của các bài toán tối ưu hóa tổ hợp (Combinatorial Optimisation) mang đầy bản chất Toán Học. Vì thế mà lý thuyết sắp lịch cũng được nghiên cứu trong các đơn vị nghiên cứu Toán Học. Ngoài ra, sắp lịch nói riêng và vận trù học (Operations Research) nói chung được giảng dạy và nghiên cứu trong các trường về kinh doanh tại Anh và Bắc Mỹ. Thực vậy, trong bài viết của mình Shah, tác giả đã kết luận rằng sắp lịch quan trọng bởi hai lý do chính. Lý do thứ nhất liên quan đến các rủi ro kinh tế quan trọng (ví dụ sự bồi thường do chậm trễ tiến độ) nếu như một lịch trình tồi tệ được thực hiện. Lý do thứ hai liên quan đến sự nắm bắt các cơ hội (trong kinh doanh) nếu như chúng ta có một kỹ thuật sắp lịch hiệu quả. Vì lẽ đó, ta có thể nói rằng sắp lịch có mối quan hệ mật thiết với lĩnh vực kinh doanh, thương mại. Nói một cách khác, sắp lịch không chỉ đơn thuần là một ngành khoa học lý thuyết (Toán Học) mà còn là một ngành khoa học ứng dụng (Kinh Doanh). Trong khuôn khổ bài viết này, chúng ta sẽ quan tâm đến một dạng bài toán cụ thể trong 47 Tạp chí Epsilon, Số 04, 08/2015 lý thuyết sắp lịch và có liên quan mật thiết với sản xuất theo dây chuyền: Bài toán sắp lịch dạng flowshop. Từ những năm 1950; các bài toán dạng flowshop đã không ngừng tiến triển và thu hút ngày càng nhiều sự quan tâm của các nhà nghiên cứu bởi cả những lợi ích cũng như độ khó của chúng. Thực tế, các bài toán dạng flowshop không chỉ đa dạng về các loại điều kiện ràng buộc mà còn về các mục tiêu tối ưu. Chính sự đa dạng này khiến các bài toán dạng flowshop rất gần với các bài toán thực tế. Dù vậy, ta quan tâm trong bài viết này một phương pháp tiếp cận có thể áp dụng được cho một lớp bài toán thay vì từng bài toán riêng lẻ. Trong luận án của mình, Lenté đã giới thiệu đại số MaxPlus để mô hình hóa một số bài toán sắp lịch dạng flowshop. Phương pháp tiếp cận này đã được sử dụng để làm xuất hiện các quan hệ tuyến tính trong các bài toán 2 máy (bài toán cơ bản, bài toán với ràng buộc độ trễ cố định cùng thời gian chuẩn bị và tháo dỡ, bài toán không có độ trễ) cũng như trong các bài toán m máy với ràng buộc độ trễ cố định cùng thời gian chuẩn bị và tháo dỡ. Lợi ích của MaxPlus là đơn giản hóa các ký hiệu để dễ dàng làm nổi bật tính chất của các phép tính. Ngoài ra, MaxPlus còn cho phép ta biến đổi bài toán dạng flowshop thành bài toán ma trận. Nói một cách khác, chúng ta có thể thực hiện các phép tính và biến đổi trên ma trận. Trong bài viết này, chúng ta sẽ mô hình hóa một lớp bài toán sắp lịch bằng cách sử dụng đại số MaxPlus. Thật ra, chúng ta nhận thấy rằng độ trễ giữa các tác vụ (operations) thường được xét đến trong các bài toán dạng flowshop. Các độ trễ này có thể được gây nên bởi thời gian sấy khô, thời gian làm nguội hoặc thời gian bình ổn ... Một cách ẩn ý, chúng cũng có thể liên quan đến các loại ràng buộc khác như thời gian chuẩn bị hoặc thời điểm nhàn rỗi. Vì vậy, chúng ta hy vọng có thể mô hình hóa một lớp bài toán dạng flowshop với các điều kiện ràng buộc liên quan đến độ trễ. Sau phần giới thiệu chung này, chúng ta sẽ nhắc lại định nghĩa và các quy ước của bài toán dạng flowshop, ký hiệu và các loại ràng buộc được nghiên cứu đến trong bài viết. Tiếp theo, sơ lược và các tính chất của đại số MaxPlus sẽ được trình bày. Cuối cùng, với mỗi bài toán cụ thể, ma trận công việc (job associated matrix) sẽ được thiết lập và từ đó, một bài toán trọng tâm (hàm chứa nhiều bài toán khác) sẽ được chỉ ra. 2. Bài toán dạng flowshop 2.1. Định nghĩa và quy ước Một bài toán dạng flowshop m máy là một bài toán sắp xếp thứ tự cho n-công việc (job) khi chúng lần lượt được xử lý trên m máy (machine). Mỗi công việc bao gồm m tác vụ (operation) theo thứ tự định trước và hoàn toàn xác định: Tác vụ j của công việc i được xử lý bởi máy j trong khoảng thời gian pij . Thứ tự các tác vụ của mỗi công việc là giống nhau. Mọi công việc được quy ước là luôn ở trạng thái sẵn sàng để được xử lý cho đến khi chúng được xử lý xong hoàn toàn. Tại mỗi thời điểm bất kỳ, mỗi máy chỉ xử lý một công việc và một công việc chỉ được xử lý bởi duy nhất một máy. Trong phạm vi bài này, khi được xử lý, mỗi tác vụ sẽ được xử lý liên tục cho đến khi hoàn tất. Ngoài ra, chúng ta xem xét bài toán với thứ tự các công việc được xử lý trên mỗi máy là như nhau. Hình dưới đây thể hiện một bài toán dạng flowshop có 2 máy và 3 công việc. 48 Tạp chí Epsilon, Số 04, 08/2015 Hình 4.1: Bài toán dạng flowshop 2 máy. 2.2. Ký hiệu Ở đây ta sử dụng loại ký hiệu được đề xuất bởi Graham và các đồng tác giả để mô tả một bài toán sắp lịch: ˛ jˇj : Trong loại ký hiệu này, ˛ thể hiện dạng bài toán, ˇ thể hiện tập hợp các điều kiện ràng buộc và thể hiện tiêu chí cần tối ưu. Bài viết này đề cập đến các bài toán dạng flowshop nên trường ˛ chứa ký hiệu Fm; trong đó m thể hiện số lượng máy của hệ thống và trường có thể là bất cứ mục tiêu nào. Ngoài ra, các ký hiệu dưới đây sẽ được sử dụng trong các phần kế tiếp. n W Số lượng công việc cần sắp lịch. J D fJ1; J2; : : : ; Jng W Tập hợp các công việc cần sắp lịch. M D fM1; M2; : : : ; Mmg W Tập hợp các máy để xử lý các công việc (quy ước các máy được sắp theo thứ tự của quy trình sản xuất). JiW Công việc i .i D 1; : : : ; n/ được đánh số ngẫu nhiên (trừ khi có quy ước khác). Mj W Máy j .j D 1; : : : ; m/ được đánh số theo thứ tự của quy trình sản xuất. Oij W Tác vụ j của công việc Ji: pij W Thời gian xử lý của tác vụ Oij : ıj W Thời điểm nhàn rỗi của máy Mj : Eı D fı1; ı2; : : : ; ımg W Véc-tơ các thời điểm nhàn rỗi của các máy. W Tập hợp có thứ tự các công việc . .1/; .2/; : : : ; .n// trong đó .i / là công việc ở vị trí thứ i của tập hợp. Cij . / W Thời điểm hoàn thành tác vụ Oij : Ci. / W Thời điểm hoàn thành công việc Jitrên máy Mm: C .i/ W Thời điểm hoàn thành công việc thứ i của tập có thứ tự (trên máy cuối cùng). Vì vậy, C .n/ hay C. / hay Cmax. / còn được gọi là makespan. CEi D fCi1; Ci2; : : : ; Cimg W Véc-tơ các thời điểm hoàn thành của công việc Jitrên các máy. Sij W Thời gian chuẩn bị cần thiết trước khi xử lý tác vụ Oij : 49 Tạp chí Epsilon, Số 04, 08/2015 Rij W Thời gian tháo dỡ cần thiết sau khi xử lý tác vụ Oij : ˛ij W Độ trễ tối thiểu giữa hai tác vụ liên tiếp Oi.j1/ và Oij : ˇij W Độ trễ tối đa giữa hai tác vụ liên tiếp Oi.j1/ và Oij : Dij . / W Thời điểm giải phóng máy Mj khỏi công việc Ji: DiW Thời điểm giải phóng máy Mm khỏi công việc Ji: D .i/ W Thời điểm giải phóng máy Mm khỏi công việc thứ i của tập có thứ tự : DEi D fDi1; Di2; : : : ; Dimg W Véc-tơ các thời điểm giải phóng các máy khỏi công việc Ji: 2.3. Các loại ràng buộc Những phần trình bày dưới đây sẽ giới hạn những loại ràng buộc như sau: perm được sử dụng trong bài toán dạng flowshop và thể hiện thứ tự (một hoán vị) các công việc giống nhau trên tất cả các máy. no wait xác định rằng không có bất kỳ độ trễ nào giữa thời điểm kết thúc và thời điểm bắt đầu của hai tác vụ liên tiếp nhau của cùng một công việc. min delay (max delay hay min max / delay): xác định rằng có một độ trễ tối thiểu (tối đa hay cả tối thiểu lẫn tối đa) giữa thời điểm kết thúc và thời điểm bắt đầu của hai tác vụ liên tiếp nhau của cùng một công việc. Snsd thể hiện rằng mỗi một tác vụ cần có một khoảng thời gian chuẩn bị trước khi được xử lý và hoàn toàn không bị chi phối bởi thứ tự của công việc. Rnsd thể hiện rằng mỗi một tác vụ cần có một khoảng thời gian tháo dỡ sau khi được xử lý xong và hoàn toàn không bị chi phối bởi thứ tự của công việc. 3. Đại số MaxPlus 3.1. Tổng quát Phần này sẽ giới thiệu sơ lược về đại số MaxPlus, chi tiết có thể được tham khảo trong các tài liệu Gaubert 1992 và Gunawardena 1998: Đại số MaxPlus được xây dựng dựa trên tập hợp E D R [ f1g được trang bị hai luật trong ký hiệu là ˚ và ˝: Trong đại số này, toán tử cộng ˚ biểu diễn phép so sánh lớn nhất và toán tử nhân ˝ biểu diễn phép cộng thông thường. Toán tử ˚ có tính lũy đẳng, giao hoán, kết hợp và có phần tử trung hòa ký hiệu là 0k (tương ứng với 1/: Toán tử ˝ có tính kết hợp, phân phối đối toán tử ˚; có phần tử trung hòa ký hiệu là 1k (tương ứng với 0) và nhận 0k làm phần tử hấp thu. Bổ đề 3.1. Với mọi a 2 Rmax và a ¤ 0k ; tồn tại nghịch đảo của phần tử a được ký hiệu là a1 hoặc 1kasao cho: a ˝ a1 D a1 ˝ a D 1k (ta có thể lưu ý rằng với ký hiệu thông thường, phần tử nghịch đảo này chính là phần tử đối của a). 50 Tạp chí Epsilon, Số 04, 08/2015 Tồn tại một mối liên hệ giữa toán tử quan hệ thứ tự của các số thực với toán tử ˚ W Với mọi a; b 2 Rmax; a b , a ˚ b D a: Chúng ta cũng có thể viết trong bài này theo cách: a ˝ b D a b D ab: 3.2. Phép tính ma trận Trong đại số MaxPlus, ta có thể định nghĩa tổng và tích của các ma trận. Định nghĩa 1. Cho A là một ma trận kích cỡ m n; cho B là một ma trận kích cỡ m n; ký hiệu Œ:`; c là phần tử trên dòng thứ ` và cột thứ c: Ta định nghĩa A ˚ B bằng: ŒA ˚ B`;c D ŒA`;c ˚ ŒB`;c .1 6 ` 6 m; 1 6 c 6 n/: Dưới đây là một ví dụ về tính tổng của hai ma trận: 2 3 4 5 ˚ 2 6 2 3 D 2 ˚ 2 3 ˚ 6 4 ˚ 2 5 ˚ 3 ! D 2 6 4 5 : Định nghĩa 2. Cho A là một ma trận kích thước m p; cho B là một ma trận kích thước p n; ký hiệu Œ:`;c là phần tử trên dòng ` và cột c: Ta định nghĩa A ˝ B bằng: ŒA ˝ B`;c DMp kD1 ŒA`;k ˝ ŒBk;c .1 ` m; 1 c n/: Tích của hai ma trận được minh họa bằng ví dụ đưới đây: 2 3 4 5 ˝ 2 6 2 3 D .2 ˝ 2/ ˚ .3 ˝ 2/ .2 ˝ 6/ ˚ .3 ˝ 3/ .4 ˝ 2/ ˚ .5 ˝ 2/ .4 ˝ 6/ ˚ .5 ˝ 3/ D 4 ˚ 5 8 ˚ 6 6 ˚ 7 10 ˚ 8 D 5 8 7 10 : Theo định nghĩa 2; hai bổ đề dưới đây được phát biểu như sau: Bổ đề 3.2. Với mọi j 2 f1; : : : ; ng; thì ŒA ˝ B1j ŒA11 ˝ ŒB1j : Theo như ví dụ bên trên, ta kết luận rằng: ŒA ˝ B11 D 5 2 ˝ 2 D ŒA11 ˝ ŒB11.D 4/; ŒA ˝ B12 D 8 2 ˝ 6 D ŒA11 ˝ ŒB12.D 8/: Bổ đề 3.3. Với mọi f`; j g 2 f1; : : : ; ng; thì ŒA ˝ B1j ŒA1` ˝ ŒB`j ; ŒA ˝ B`j ŒA`` ˝ ŒB`j : 51 Tạp chí Epsilon, Số 04, 08/2015 Vẫn theo ví dụ phía trên, ta có: ŒA ˝ B11 D 5 3 ˝ 2 D ŒA12 ˝ ŒB21 .D 5/; ŒA ˝ B12 D 8 3 ˝ 3 D ŒA12 ˝ ŒB22 .D 6/; ŒA ˝ B21 D 7 4 ˝ 2 D ŒA21 ˝ ŒB11 .D 6/; ŒA ˝ B21 D 7 5 ˝ 2 D ŒA22 ˝ ŒB21 .D 7/; ŒA ˝ B22 D 10 4 ˝ 6 D ŒA21 ˝ ŒB12 .D 10/; ŒA ˝ B22 D 10 5 ˝ 3 D ŒA22 ˝ ŒB22 .D 8/: 3.3. Toán tử ngôi sao Định nghĩa 3. Với mọi a 2 Rmax; toán tử ngôi sao được định nghĩa: a D lim q!1. 1k ˚ a ˚ a2 ˚ ˚ aq/: Đây là một ví dụ về toán tử ngôi sao trong Rmax W 2 D 1k ˚ 2 ˚ 4 ˚ 6 ˚ D 1: Định nghĩa 4. Cho A là một ma trận kích thước m m, toán tử ngôi sao được định nghĩa như sau: A D lim q!1. 1k ˚ A ˚ A2 ˚ ˚ Aq/: Bổ đề 3.4. Với mọi a; b 2 Rmax; ba là nghiệm nhỏ nhất của bất phương trình x b ˚ xa và a b là nghiệm nhỏ nhất của bất phương trình x b ˚ ax: Ngoài ra, các nghiệm này làm thỏa mãn dấu đẳng thức, ba vì vậy cũng là nghiệm nhỏ nhất của phương trình x D b ˚ xa và a b là nghiệm nhỏ nhất của phương trình của phương trình x D b ˚ ax: Kết quả này cũng được áp dụng vào các phép tính ma trận (X B ˚ AX /: Đối với số thực, ví dụ sau thỏa mãn Bổ đề 4 W .2/ D 1k ˚ .2/ ˚ .4/ ˚ .6/ ˚ D 1k : Vì vậy, nghiệm nhỏ nhất của phương trình x D b ˚ .2/x là x D .2/ b D 1k b D b: Đối với các ma trận gồm các thành phần trong Rmax; ta có thể nhận được nghiệm nhỏ nhất của phương trình X D B ˚ AX W x1 x2 D 12 15 ˚ 0k 2 2 0k x1 x2 : Bằng cách viết lại dưới dạng X D B ˚ AX W x1;1 x1;2 x2;1 x2;2 D 12 0k 15 0k ˚ 0k 2 2 0k 52 12 0k 15 0k x1;1 x1;2 x2;1 x2;2 ; Tạp chí Epsilon, Số 04, 08/2015 nghiệm nhỏ nhất là X D A B: Ta có A2 D 1k 0k 0k 1k : Thế nên X D 1k 2 2 1k 12 0k 15 0k D 13 0k 15 0k ; và nghiệm nhỏ nhất của phương trình ban đầu là X D 13 15 : 3.4. Ứng dụng của đại số MaxPlus trong bài toán sắp lịch Đại số MaxPlus được dùng trong các hệ thống điều khiển, nhất là các hệ thống có liên hệ với mạng Petri nhưng rất hiếm khi được sử dụng trong lý thuyết sắp lịch. Tuy nhiên, chúng ta cũng có thể tham khảo một vài nghiên cứu có liên quan của Giffler đối với bài toán sắp lịch dự án, của Hanen và Munier đối với các bài toán máy song song có chu kỳ, của Gaubert và Mairesses, và của Cohen cùng các đồng tác giả. Cohen đối với bài toán dạng flowshop có chu kỳ, của Gaubert và của Houssin đối với các bài toán dạng jobshop có chu kỳ. Trong luận án của mình, Lenté đã chứng minh rằng các bài toán dạng flowshop m máy với ràng buộc hoán vị .perm/ có thể được mô hình hóa bằng đại số MaxPlus. Cụ thể hơn, mỗi công việc Ji có thể được đặc trưng hoàn toàn bằng một ma trận Titương ứng. Ma trận Ti này hoàn toàn đặc trưng được các ràng buộc của bài toán. Cũng trong nghiên cứu này, tác giả đã chứng minh được rằng đại số MaxPlus cho phép ta biểu diễn một tập có thứ tự các công việc dưới dạng tích của các ma trận. Trong Bouquard and Lenté, các tác giả cũng sử dụng đại số MaxPlus để mô hình hóa bài toán dạng flowshop 2 máy với độ trễ tối đa và tối thiểu .F2 j permI min max /delay jCmax/; sau đó đã chỉ ra các chặn dưới và chặn trên bằng cách giảm nhẹ các ma trận MaxPlus. Kết quả này sau đó được mở rộng ra cho trường hợp m máy trong Augusto et al 2006: Trong Vo and Lenté 2013; đại số này lại một lần nữa cho phép ta chứng minh sự tương đương giữa hai bài toán: Bài toán với ràng buộc độ trễ (tối đa và tối thiểu) Fm j permI min max /delay j và bài toán với ràng buộc gồm độ trễ (tối đa và tối thiểu) và thời gian chuẩn bị và tháo dỡ Fm j permI min max /delayI Snsd I Rnsd j ; cũng như làm xuất hiện bài toán trọng tâm. Ngoài ra, trong Voo et al 2014; bằng cách sử dụng các ma trận MaxPlus, các tác giả đã tìm ra được các chặn dưới cho tổng các thời điểm hoàn thành (Fm j permI ˇ jPCi/ từ các chặn dưới của mỗi thời điểm hoàn thành của từng công việc. Một kết quả tương tự cũng đã được tìm ra với tổng trọng số các thời điểm hoàn thành (Fm j permI ˇ jPwiCi/ nhờ vào đại số MaxPlus trong Vo and Lenté 2014. Những chi tiết về ứng dụng của đại số MaxPlus trong bài toán dạng flowshop cũng như các kết quả trên đây được trình bày cụ thể trong Vo and Lenté 2015: 53 Tạp chí Epsilon, Số 04, 08/2015 4. Mô hình hóa bằng đại số MaxPlus Phần này sẽ tập trung trình bày việc sử dụng đại số MaxPlus để mô hình hóa bài toán dạng flowshop, cụ thể là giới thiệu các ma trận MaxPlus tương ứng với mỗi công việc. Các kết quả chính sẽ được giới thiệu, các phép tính chi tiết có thể được tham khảo trong Vo and Lenté 2015: 4.1. Nguyên tắc chung Các mô hình đã được thực hiện cho đến lúc này Lenté 2011 đều đưa đến một kết luận: Với mỗi công việc Ji; tồn tại một ma trận MaxPlus tương ứng Ti kích thước m m được định nghĩa hoàn toàn bởi các dữ liệu của công việc Ji và các điều kiện ràng buộc của bài toán. Ma trận này biểu diễn mối quan hệ tuyến tính MaxPlus kết nối các thời điểm nhàn rỗi của các máy trước và sau khi thực thi một công việc. Các kết quả này, đã được chứng minh trong các nghiên cứu cho đến lúc này, được tóm tắt bởi mệnh đề sau đây. Mệnh đề 4.1. Cho một công việc Ji; tồn tại một ma trận MaxPlus Ti kích thước m m sao cho DEi D Eı ˝ Ti; (4.1) trong đó Eı là véc-tơ các thời điểm nhàn rỗi của các máy trước khi thực thi công việc Ji và DEi là véc-tơ các ngày nhàn rỗi của các máy sau khi thực thi. Tất cả hệ số của ma trận Ti được tính trực tiếp từ công việc Ji và các điều kiện ràng buộc của bài toán, và ngược lại, ma trận này hoàn toàn đặc trưng cho công việc Ji cũng như các điều kiện ràng buộc của bài toán flowshop. Các hệ số của ma trận Ti được ký hiệu ti`c: 1 0 BB@t111 t112 t11m CCA: Ti D t121 t122 t12m t1m1 t1m2 t1mm Cần lưu ý rằng các thời điểm các máy được giải phóng sau khi thực hiện một công việc không nhất thiết trùng với thời điểm kết thúc các tác vụ. Điều này có thể vì nhiều lý do, ví dụ như thời gian tháo dỡ (xem hình dưới) hoặc các điều kiện ràng buộc về sự tắc nghẽn. Ngay khi ta thiết lập được các ma trận Ti, ta cũng có thể định nghĩa các ma trận tương ứng với các tập có thứ tự các công việc. Định nghĩa 5. (Ma trận tương ứng với tập có thứ tự các công việc) Cho là một tập có thứ tự của -công việc: Ma trận tương ứng của nó T được định nghĩa bởi T DO iD1 T .i/: Giống như các ma trận Ti; các ma trận T định nghĩa quan hệ tuyến tính MaxPlus giữa các thời điểm nhàn rỗi của các máy trước và sau khi thực hiện tập có thứ tự các công việc. Mệnh đề 4.2. Cho DE là véc-tơ các thời điểm các máy được giải phóng bởi tập có thứ tự các công việc ; ta có quan hệ sau: DE D Eı ˝ T : 54 Tạp chí Epsilon, Số 04, 08/2015 Hình 4.2: Bài toán flowshop với ràng buộc độ trễ, thời gian thiết lập, tháo dỡ. 4.2. Ma trận tương ứng với mỗi công việc 4.2.1. Bài toán cơ bản Ta gọi bài toán cơ bản dạng flowshop là một bài toán dạng flowshop hoán vị và không có thêm điều kiện ràng buộc khác. Bài toán này được ký hiệu Fm j perm j trong đó là một tiêu chí bất kỳ. Mệnh đề sau đã được thiết lập trong Lenté 2001: Mệnh đề 4.3. Với mọi công việc Ji; ma trận Tithể hiện mối liên hệ giữa các thời điểm nhàn rỗi và kết thúc sớm nhất của một công việc được định nghĩa bởi: Ti D 0 BB@pi1 pi1pi2 pi1pi2 pim 0k pi2 pi2pi3 pim 0k 0k pim 1 CCA(4.2) Lời giải. Với mọi công việc Ji; các thời điểm kết thúc của m tác vụ trên m máy được thể hiện bởi các bất phương trình sau: Ci1 ı1 C pi1 (4.3) Ci2 maxfCi1 C pi2; ı2 C pi2g (4.4) Cij maxfCi.j1/ C pij ; ıj C pij g .2 < j m/ (4.5) Bằng ký hiệu MaxPlus ta có Ci1 ı1pi1 (4.6) Ci2 Ci1pi2 ˚ ı2pi2 (4.7) Cij Ci.j1/pij ˚ ıjpij .2 < j m/ (4.8) Vì vậy, viết lại hệ bất phương trình trên dưới dạng ma trận, ta có CEi EıTitrong đó ma trận Ti được định nghĩa trong đẳng thức (4.2). Nghiệm nhỏ nhất của bất phương trình này tương ứng với dấu đẳng thức CEi D EıTi: Mối quan hệ này thể hiện sự liên hệ giữa các thời điểm nhàn rỗi và kết thúc sớm nhất của công việc Ji: Chi tiết có thể xem thêm trong Lenté 2001: Lưu ý là trong trường hợp này, các thời điểm kết thúc của các tác vụ cũng chính là các thời điểm giải phóng các máy khỏi các tác vụ đó. Vì vậy, nghiệm trên có thể được viết lại là DEi D EıTi: 55 Tạp chí Epsilon, Số 04, 08/2015 4.2.2. Bài toán với ràng buộc độ trễ tối thiểu Với bài toán với ràng buộc độ trễ tối thiểu .Fm j perm; min delay j trong đó là một tiêu chí bất kỳ), cùng một cách thức, ta có thể có ma trận tương ứng với công việc Ji Lenté 2001: Ti D 0 BB@pi1 pi1˛i2pi2 pi1˛i2pi2 ˛impim 0k pi2 pi2˛i3pi3 ˛impim 0k 0k pim 1 CCA(4.9) và ta có thể thấy trong trường hợp này thì DEi D CEi D EıTi. 4.2.3. Bài toán với ràng buộc độ trễ tối thiểu và tối đa Một bài toán dạng flowshop với ràng buộc độ trễ là một bài toán dạng flowshop với sự có mặt của các độ trễ giữa hai tác vụ liên tiếp nhau của cùng một công việc. Mỗi một độ trễ phải bị chặn bởi một giới hạn dưới (độ trễ tối thiểu) và một giới hạn trên (độ trễ tối đa). Loại bài toán này được ký hiệu Fm j perm; min max /delay j trong đó là một tiêu chí bất kỳ. Mệnh đề dưới đây giới thiệu ma trận tương ứng với mỗi công việc trong dạng bài toán flowshop này. Kết quả này đã được trình bày trong Bouquard and Lenté 2006 cho trường hợp 2 máy và trong Augusto et al 2006 cho trường hợp 3 máy. Phần dưới đây sẽ chứng minh kết quả này cho trường hợp tổng quát m máy. Mệnh đề 4.4. Ma trận Titương ứng với công việc Ji được định nghĩa bởi: 8ˆˆˆˆˆˆˆˆˆˆ< pi` Oc kD`C1 pik˛ik si ` < c ŒTi`;c D pi` si ` D c `1 (4.10) ˆˆˆˆˆˆˆˆˆˆ: 1k ˇi` 1k O kDcC1 1k pikˇiksi c < ` 1 ˇi`si c D ` 1 Trong trường hợp cụ thể 3-máy, ma trận này được biểu diễn như sau: 0 BBBB@pi1 pi1˛i2pi2 pi1˛i2pi2˛i3pi3 1k 1 CCCCA(4.11) Ti D ˇi2pi2 pi2˛i3pi3 1k ˇi2pi2ˇi3 1k ˇi3pi3 Lời giải. Phần chứng minh được thực hiện theo hai bước: Đầu tiên, ta sẽ thiết lập một công thức ma trận để định nghĩa Ti và sau đó, ta sẽ tính toán các hệ số. Bước thứ nhất: Công thức tính Ti: Các mối liên hệ giữa các thời điểm nhàn rỗi của các máy, các độ trễ, các thời gian xử lý tác vụ và các thời điểm giải phóng các máy được minh họa bằng hình dưới đây. Chúng được thể hiện cụ thể hơn trong các bất phương trình sau. Lưu ý rằng trong trường hợp này, các thời điểm giải phóng các máy cũng là các thời điểm hoàn thành các tác vụ 56 Tạp chí Epsilon, Số 04, 08/2015 Hình 4.3: Mối liên hệ giữa các thời điểm giải phóng khỏi các tác vụ trên ba máy liên tiếp. Dik Di.k1/˛ikpik .2 k m/; (4.12) Dik Di.kC1/1k pi.kC1/ˇi.kC1/.1 k m 1/; (4.13) Dik ıkpik .1 k m/: (4.14) Nhắc lại rằng mối quan hệ tuyến tính mà chúng ta đang kỳ vọng sẽ được viết dưới dạng: DEi D EıTi; (4.15) trong đó Tilà ma trận tương ứng với công việc Ji: Bằng cách đặt các ma trận Ai và Bi như dưới đây, ta có thể thiết lập công thức của Ti (xem Mệnh đề 4.5). Định nghĩa 6. aik D ˛i.kC1/pi.kC1/ .1 k m 1/ bik D1k ˇikpik.2 k m/ Pi D 0 BB@pi1 0k 0k 0k pi2 0k 1 CCA 0 0k 0k pim 1 Ai D BBBB@0k ai1 0k 0k bi2 0k ai2 0k bi3 0k ai.m1/ 0k 0k bim 0k CCCCA Mệnh đề 4.5. Ma trận Titương ứng với công việc Ji được định nghĩa bởi: Ti D PiAi (4.16) 57 Tạp chí Epsilon, Số 04, 08/2015 trong đó q!1.1 ˚ Ai ˚ A2i ˚ : : : ˚ Aqi/ (4.17) A i D lim Lời giải. (của Mệnh đề 4.5) Các bất phương trình (4.12), (4.13) và (4.14) được viết lại dưới dạng ma trận như sau: DEi DEiAi ˚ EıPi (4.18) Sử dụng Bổ đề ?? (trang ??), véc-tơ nhỏ nhất DEithỏa mãn bất phương trình (4.18) được xác định bởi: DEi D EıPiAi (4.19) So sánh kết quả này với mối quan hệ tuyến tính được kỳ vọng trong đẳng thức (4.15), ta rút ra được: Ti D PiAi , và đây là kết quả chứng minh của Mệnh đề 4.5. Giai đoạn 2 : ta sẽ tiếp tục tính các hệ số của ma trận A irồi đến các hệ số của ma trận Ti. Chi tiết của phần này được trình bày trong [14]. Các hệ số của ma trận A iđược xác định bởi: A i `;c D 8ˆˆˆˆˆˆˆ< Oc1 kD` aik si ` < c 1 si ` D c ˆˆˆˆˆˆˆ: (4.20) O` kDcC1 bik si c < ` Từ đó, ta có thể tính được Ti nhờ mối liên hệ Ti D PiAi (xem Mệnh đề 4.5): 8ˆˆˆˆˆˆˆˆˆˆ< pi` Oc kD`C1 pik˛ik si ` < c ŒTi`;c D pi` si ` D c `1 ˆˆˆˆˆˆˆˆˆˆ: 1 ˇi` 1 O kDcC1 1 pikˇiksi c < ` 1 ˇi`si c D ` 1 Điều này kết thúc phần chứng minh của Mệnh đề 4.4. 4.2.4. Bài toán với ràng buộc độ trễ tối đa và tối thiểu cùng thời gian chuẩn bị và tháo dỡ Chúng ta trở lại với bài toán ngay phía trên nhưng lần này có xem xét đến cả ràng buộc về thời gian chuẩn bị và tháo dỡ. Hình 4.4 dưới đây minh họa cho các ràng buộc về độ trễ và thời gian chuẩn bị, thời gian tháo dỡ liên quan đến tác vụ thứ k của công việc Ji. Những ràng buộc này được liên kết lại trong phương trình thể hiện bởi các công thức (4.21), (4.22) và (4.23). Chúng sẽ phục vụ cho việc xác định mối quan hệ tuyến tính MaxPlus giữa các thời điểm nhàn rỗi của các máy (ık) và các thời điểm các máy được giải phóng (Dik). 58 Tạp chí Epsilon, Số 04, 08/2015 Hình 4.4: Mối liên hệ giữa các thời điểm giải phóng các máy khỏi các tác vụ trên ba máy liên tiếp. Dik Di.k1/˛ikpikRik Ri.k1/.2 k m/ (4.21) Dik Di.kC1/1 pi.kC1/ˇi.kC1/ Rik Ri.kC1/.1 k m 1/ (4.22) Dik ıkSikpikRik .1 k m/ (4.23) Cùng một cách thức như ở bài toán phía trên, ta có Mệnh đề sau. Mệnh đề 4.6. Ma trận Titương ứng với công việc Ji được xác định như sau: 8ˆˆˆˆˆˆˆˆˆˆ< Si`pi`Ric Oc kD`C1 pik˛ik if ` < c ŒTi`;c D Si`pi`Ric if ` D c `1 (4.24) ˆˆˆˆˆˆˆˆˆˆ: Si`Ric ˇi` Si`Ric O kDcC1 1 pikˇikif c < ` 1 ˇi`if c D ` 1 Lời giải. Phần chứng minh này được thực hiện tương tự như trường hợp bài toán chỉ có ràng buộc về độ trễ tối đa và tối thiểu. 4.3. Bài toán trọng tâm Những định nghĩa về các ràng buộc liên quan đến độ trễ mang đến cho chúng ta những sự liên hệ giữa chúng: Chỉ có ràng buộc độ trễ tối thiểu: độ trễ tối đa được xem như vô cùng. Chỉ có ràng buộc độ trễ tối đa: độ trễ tối thiểu được xem như bị triệt tiêu. Chỉ có ràng buộc độ trễ cố định: độ trễ tối thiểu và độ trễ tối đa được ấn định giá trị như nhau. 59 Tạp chí Epsilon, Số 04, 08/2015 Nói cách khác, ta có thể quy các bài toán dạng flowshop với ràng buộc độ trễ về một bài toán duy nhất với ràng buộc bao gồm cả độ trễ tối thiểu và độ trễ tối đa. Sau đây, ta sẽ xem xét bài toán với ràng buộc độ trễ tối thiểu và tối đa cùng với thời gian chuẩn bị và tháo dỡ (FmjpermI mi n max delayI Snsd I Rnsd j). Ma trận tương ứng với mỗi công việc Ji đã được xác định như sau: Ti D 1 0 Si1pi1Ri1 Si1pi1˛i2pi2Ri2 : : : Si1pi1˛i2pi2 : : : ˛impimRim Si2Ri1 CCCCCCCCA BBBBBBBB@ ˇi2Si2pi2Ri2 : : : Si2pi2˛i3pi3 : : : ˛impimRim :::::::::::: ˇi2pi2 : : : ˇi.m1/pi.m1/ˇim: : :SimRi.m1/ SimRi1 ˇimSimpimRim Bằng cách sử dụng các ký hiệu mới pik, ˛ik và ˇik như sau: 8ˆˆˆˆˆ< (4.25) ˆˆˆˆˆ: ma trận Titrở thành: pik D SikpikRik .1 k m/ ˇik Dˇik SikRi.k1/.2 k m/ ˛ik D˛ik SikRi.k1/.2 k m/ Ti D 0 1 pi1 pi1˛i2pi2 : : : pi1˛i2pi2 : : : ˛impim 1 BBBBBBBB@ CCCCCCCCA ˇi2pi2 : : : pi2˛i3pi3 : : : ˛impim :::::::::::: ˇi2pi2 : : : ˇi.m1/pi.m1/ˇim: : :1 1 ˇimpim Ma trận này cũng là ma trận tương ứng với mỗi công việc trong bài toán dạng flowshop với ràng buộc độ trễ tối thiểu và tối đa. Trong trường hợp này, ta vừa làm xuất hiện một bài toán trọng tâm. Tóm lại, từ tập hợp các bài toán với các ràng buộc liên quan đến độ trễ, thời gian chuẩn bị và thời gian tháo dỡ, ta có thể quy về một bài toán duy nhất với ràng buộc độ trễ tối thiểu và độ trễ tối đa. Bài toán trọng tâm này giúp ta tập trung toàn bộ thời gian để giải quyết một bài toán duy nhất, thay vì giải quyết nhiều bài toán riêng lẻ. 5. Kết luận Bài viết này giới thiệu việc sử dụng đại số MaxPlus để mô hình hóa bài toán dạng flowshop. Ta có thể xây dựng các ma trận hoàn toàn đặc trưng các công việc. Các kết quả thu được đã xác nhận mối quan hệ tuyến tính MaxPlus giữa các thời điểm nhàn rỗi của các máy trước và sau khi thực hiện công việc. Ưu điểm của đại số MaxPlus là cho phép ta đơn giản hóa các ký hiệu tính toán. Các kết quả này cũng giúp ta thực hiện việc nghiên cứu các bài toán ma trận thay vì nghiên cứu trực tiếp trên các bài toán dạng flowshop. Điều này cho phép ta có thể xây dựng các chặn dưới của các tiêu chí nhờ vào các phép tính trên ma trận. Ngoài ra, chúng ta đã tìm ra được một bài toán trọng tâm với ràng buộc độ trễ tối thiểu và tối đa. Bài toán này cho phép ta tránh việc trùng lặp các nghiên cứu trên các bài toán dạng flowshop với các ràng buộc khác nhau. Bài toán trọng tâm này cho phép thay thế các bài toàn có ràng buộc liên quan độ trễ và thời gian chuẩn bị, tháo dỡ. 60 Tạp chí Epsilon, Số 04, 08/2015 Tài liệu tham khảo [1] Augusto, V., Lenté, C., and Bouquard, J.-L. (2006). Résolution d’un flowshop avec delais minimaux et maximaux. In MOSIM. [2] Bouquard, J.-L. and Lenté, C. (2006). Two-machine flow shop scheduling problems with minimal and maximal delays. 4or, 4(1):15–28. [3] Cohen, G., Dubois, D., Quadrat, J.-P., and Viot, M. (1985). A linear system-theoretic view of discret-event processes and its use for performance evaluation in manufacturing. IEEE Trans. Automatic Control, 30:210–220. [4] Gaubert, S. (1992). Théorie des systèmes linéaires dans les dio¨ıdes. PhD thesis. [5] Gaubert, S. and Mairesse, J. (1999). Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans. Automatic Control, 44(4):683–698. [6] Giffler, B. (1963). Schedule algebras and their use in formulating general systems simula tions. In Industrial scheduling. Prentice Hall, New Jersey. [7] Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5(2):287–326. [8] Gunawardena, J. (1998). Idempotency. Publications of the Newton Institute. [9] Hanen, C. and Munier, A. (1995). Cyclic scheduling on parallel processors: an overview. John Wiley. [10] Houssin, L. (2011). Cyclic Jobshop Problem and (max, Plus) Algebra. In Sergio, B., editor, World IFAC Congres, number Ifac, pages 2717–2721. [11] Lenté, C. (2001). Analyse Max-Plus de problèmes d’ordonnancement de type Flowshop. PhD thesis, Université Franc¸ois Rabelais de Tours. [12] Lenté, C. (2011). Mathématiques, Ordonnancement et Santé. Habilitation à diriger des recherches, Université Franc¸ois Rabelais de Tours. [13] Shah, N. (1996). Mathematical programming techniques for crude oil scheduling. Com puters & Chemical Engineering, 20(96):S1227–S1232. [14] Vo, N. V. (2015). Approche algébrique de problèmes d’ordonnancement de type flowshop avec contraintes de délais. PhD thesis, Université Franc¸ois Rabelais de Tours. [15] Vo, N. V., Fouillet, P., and Lenté, C. (2014). General lower bounds for the total completion time in a flowshop scheduling problem - MaxPlus approach. In Proceedings of the 3rd International Conference on Operations Research and Enterprise Systems, Angers, France. SciTePress - Science and Technology Publications. [16] Vo, N. V. and Lenté, C. (2013). Equivalence between Two Flowshop Problems - MaxPlus Approach. In Proceedings of the 2nd International Conference on Operations Research and Enterprise Systems, pages 174–177, Barcelona. SciTePress - Science and Technology Publications. 61 Tạp chí Epsilon, Số 04, 08/2015 [17] Vo, N. V. and Lenté, C. (2014). From MaxPlus algebra to general lower bounds for the total weighted completion time in flowshop scheduling problems. Lecture Notes in Management Science, 6:128–137. 62 VỀ CHỨNG MINH VÀ TIẾN BỘ TRONG TOÁN HỌC William P. Thurston (Dịch bởi Nguyễn Dzuy Khánh) Tóm tắt Bài viết này trình bày về bản chất của phép chứng minh và tiến bộ trong toán học, được khuyến khích bởi bài báo của Jaffe và Quinn, “Theoretical Mathematics: Toward a cultural synthesis of mathematics and theoretical physics” (Toán học lý thuyết: Hướng tới sự tổng hợp mang tính văn hóa của toán học và vật lý lý thuyết). Bài báo của họ nêu lên nhiều vấn đề thú vị mà các nhà toán học cần quan tâm tới nhiều hơn, nhưng nó cũng duy trì một số niềm tin và thái độ cần bị nghi ngờ và cần được kiểm chứng. Bài báo có một đoạn miêu tả vài phần trong công trình của tôi theo một cách chệch đi với kinh nghiệm của tôi, và nó cũng chệch khỏi những quan sát của mọi người trong lĩnh vực mà tôi đã từng thảo luận cùng về nó như một phép thử thực tế. Sau một hồi suy nghĩ, tôi thấy có vẻ như những gì Jaffe và Quinn viết là một ví dụ cho hiện tượng rằng mọi người thấy cái mà họ được định hướng để thấy. Sự mô tả của Jaffe và Quinn thu được qua việc chiếu tính xã hội học của toán học lên một thang kích thước một chiều (ức đoán và chặt chẽ), bỏ qua rất nhiều hiện tượng cơ bản. Nhiều phản hồi tới bài báo của Jaffe và Quinn đã được gửi đi bởi rất nhiều những nhà toán học, và tôi kỳ vọng rằng nó nhận được nhiều phân tích và phản biện cụ thể từ những người khác. Bởi vậy, trong bài viết này, tôi sẽ tập trung vào khía cạnh tích cực thay vì khía cạnh phản phủ định. Tôi sẽ trình bày quan điểm của mình về tiến trình của toán học, chỉ đôi khi nhắc đến bài báo của Jaffe và Quinn qua việc so sánh. Để thử lột bỏ các lớp của các giả thiết, điều quan trọng là phải thử bắt đầu với những câu hỏi đúng: 1. Các nhà toán học đạt được thành quả gì Có nhiều vấn đề bị che khuất trong câu hỏi này, mà tôi đã cố gắng để diễn đạt lại theo cách không giả định trước bản chất của câu trả lời. Chẳng hạn, quả thực không tốt nếu ta bắt đầu với câu hỏi Các nhà toán học chứng minh các định lý như thế nào? Câu hỏi này dẫn đến một chủ đề thú vị, nhưng để bắt đầu với nó ta phải đánh giá hai giả định ẩn giấu: .1/ Rằng tồn tại lý thuyết và thực tiễn khách quan, bất biến và được kiểm chứng chắc chắn của phép chứng minh toán học. .2/ Rằng tiến bộ được tạo ra bởi các nhà toán học bao gồm việc chứng minh những định lý. Những giả thuyết này đáng để ta kiểm chứng, thay vì chấp nhận chúng như là những điều hiển nhiên và tiếp tục tiến lên từ chúng. Thậm chí, câu hỏi cũng không phải là Các nhà toán học đã tạo ra những tiến bộ trong toán học như thế nào ? Thay vì đó dạng câu hỏi cụ thể (và quan trọng) mà tôi ưa thích là 63 Tạp chí Epsilon, Số 04, 08/2015 Làm thế nào mà các nhà toán học làm thúc đẩy hiểu biết của con người về toán học ? Câu hỏi này đem đến một điều căn bản và có tính lan tỏa: việc mà chúng ta đang làm là tìm những cách giúp con người hiểu và tư duy về toán học. Sự phát triển đột phá của máy vi tính đã giúp làm nổi bật luận điểm này, bởi vì các máy tính và con người rất khác nhau. Chẳng hạn, khi Appel và Haken hoàn tất phép chứng minh cho định lý 4 màu, sử dụng một khối lượng tính toán tự động khổng lồ, nó đã gây ra rất nhiều tranh cãi. Tôi hiểu rằng sự tranh cãi này không mấy liên quan đến tính xác thực của định lý hay sự chính xác của phép chứng minh mà người ta hoài nghi. Thay vì đó, nó phản ánh một niềm mong mỏi liên tục cho hiểu biết của con người về một phép chứng minh, ngoài việc biết rằng định lý là đúng. Ở một mức độ bình dị hơn, thường thì người ta nỗ lực sử dụng các máy tính để thực hiện những tính toán ở thang kích thước lớn cho những thứ mà họ đã hoàn thành ở thang nhỏ hơn bằng tay. Họ có thể in ra một bảng gồm 10000 số nguyên tố đầu tiên, rồi chỉ để thấy rằng, sau cùng thứ mà họ in ra chẳng phải là thứ mà họ đã mong mỏi. Qua những việc như thế, họ khám phá ra rằng thứ mà họ thực sự muốn thường không phải là một tập hợp của “các đáp án” – thứ họ muốn là sự thấu hiểu. Có vẻ như luẩn quẩn khi nói rằng điều mà các nhà toán học đang hoàn thành tốt là thúc đẩy hiểu biết của con người về toán học. Tôi sẽ không thử giải quyết vấn đề này bằng việc thảo luận toán học là gì, bởi vì nó sẽ đưa chúng ta đi lạc đề. Các nhà toán học thường cảm thấy rằng họ biết toán học là gì, nhưng cũng thấy rằng thật khó để trực tiếp đưa ra một định nghĩa tốt. Thực sự sẽ rất thú vị khi thử đặt vấn đề như vậy. Với tôi, câu trả lời “lý thuyết của những quy luật hình thức” là sát nhất, nhưng để thảo luận về nó thì lại phải cần thêm một bài viết khác mất. Liệu rằng, khi nhấn mạnh rằng toán học có một đặc tính đệ quy căn bản thì sự khó khăn trong việc trực tiếp đưa ra một định nghĩa tốt là một vấn đề mang tính bản chất? Cùng với những quan điểm này, chúng ta có thể nói rằng toán học là một ngành tối giản nhất thỏa mãn những điều kiện sau: Toán học bao gồm các số tự nhiên, hình học Euclid trong mặt phẳng và không gian. Toán học là ngành mà các nhà toán học nghiên cứu. Các nhà toán học là những người thúc đẩy tiến bộ của nhân loại trong hiểu biết về toán học. Nói cách khác, khi toán học tiến bộ, chúng ta thu nạp nó vào tư duy của mình. Khi tiến trình tư duy của chúng ta trở nên phức tạp hơn, chúng ta tạo ra thêm những khái niệm và cấu trúc toán học mới: Chủ đề của toán học thay đổi để phản ánh cách chúng ta suy nghĩ. Nếu những gì chúng ta đang làm là xây dựng các cách tư duy mới hơn, thì chiều tâm lý và xã hội là căn bản cho một mô hình tốt cho tiến bộ của toán học. Những chiều này không xuất hiện trong mô hình phổ biến. Nói một cách châm biếm, mô hình thường thấy bao gồm D. Các nhà toán học bắt đầu từ những cấu trúc toán học cơ bản và một tập hợp các tiên đề “cho trước” về những cấu trúc ấy mà T. có nhiều câu hỏi quan trọng cần được trả lời về những cấu trúc mà có thể được phát biểu như là những định lý toán học hình thức, và 64 Tạp chí Epsilon, Số 04, 08/2015 P. nhiệm vụ của các nhà toán học là tìm ra một cách suy diễn từ những tiên đề tới các định lý hay đưa ra sự phủ định. Chúng ta có thể gọi đây là mô hình định nghĩa - định lý - chứng minh (DTP) của toán học. Một khó khăn rõ ràng với mô hình DTP đó là nó không thể giải thích nguồn gốc của các câu hỏi. Jaffe và Quinn đã thảo luận về một ức đoán (mà họ đã dán cho một cái nhãn không mấy thích hợp đó là “toán học lý thuyết”) như là những thành phần bổ sung quan trọng. Ức đoán này bao gồm việc thiết lập các giả thuyết, đặt ra những câu hỏi và đưa ra những phỏng đoán thông minh cũng như các lập luận mang tính khám phá về điều có thể đúng. Mô hình DTP của Jaffe và Quinn vẫn không thành công trong việc chỉ ra một số vấn đề căn bản. Chúng ta không cố gắng đạt được một mức trừu tượng nhất định cho các định nghĩa, định lý, và chứng minh. Thước đo cho thành công của chúng ta đó là chúng ta có giúp được con người hiểu và tư duy về toán học một cách sáng sủa và hiệu quả hơn hay không. Bởi vậy, chúng ta cần phải tự hỏi mình: 2. Con người hiểu về toán học như thế nào Đây là một câu hỏi cực hóc búa. Hiểu biết là một vấn đề cá nhân và mang tính nội tại mà khó có thể hoàn toàn nhận biết, thấu hiểu và thường là khó có thể trao đổi với nhau được. Ở đây, chỉ có thể đề cập sơ sơ tới nó mà thôi. Con người thường có nhiều cách hiểu khác nhau về những khái niệm toán học. Để minh họa điều này, tốt hơn hết là dẫn ra một ví dụ mà các nhà toán học có kinh nghiệm hiểu theo nhiều cách khác nhau, nhưng chúng ta lại thấy các sinh viên thì khốn đốn với nó. Đạo hàm của một hàm số là một ví dụ hoàn toàn thích hợp. Đạo hàm có thể được hiểu như: .1/ Tính vô cùng bé: Tỉ số giữa sự thay đổi vô cùng nhỏ trong giá trị của một hàm số với sự thay đổi vô cùng nhỏ của hàm số. .2/ Tính ký hiệu: Đạo hàm của xnlà nxn1; đạo hàm của sin.x/ là cos.x/; đạo hàm của f g là f0 g g0; : : : .3/ Một cách logic: f0.x/ D d nếu và chỉ nếu với mỗi tồn tại ı sao cho khi 0 < jxj < ı; ˇˇˇˇf .x C x/ f .x/ x d ˇˇˇˇ< ı: .4/ Một cách hình học: Đạo hàm là hệ số góc của một tiếp tuyến với đồ thị hàm số, nếu đồ thị có tiếp tuyến. .5/ Tốc độ thay đổi: Tốc độ tức thời của f .t /; với t là thời gian. .6/ Xấp xỉ: Đạo hàm của một hàm số là xấp xỉ tuyến tính tốt nhất của hàm số ở lân cận của một điểm. .7/ Vi mô: Đạo hàm của một hàm số là giới hạn bạn thu được qua việc quan sát nó bằng một kính hiển vi với độ phóng đại ngày càng tăng. 65 Tạp chí Epsilon, Số 04, 08/2015 Đây là một danh sách các cách suy nghĩ hay tiếp nhận khác nhau về khái niệm đạo hàm, thay vì một danh sách các định nghĩa mang tính lô-gic. Nếu không có những nỗ lực to lớn để bảo toàn phong thái và đặc trưng của nhận thức nguyên thủy của con người, sự khác biệt sẽ bắt đầu tan biến ngay khi những khái niệm tư duy được dịch sang những định nghĩa chính xác, mang tính hình thức và cụ thể. Tôi nhớ rằng mình đã tiếp thu mỗi một trong những khái niệm trên như điều gì đó mới mẻ và thú vị, dành nhiều thời gian, nỗ lực để suy nghĩ cẩn thận và thực hành cùng với mỗi một trong chúng, rồi đồng nhất chúng với nhau. Tôi cũng không quên sau đó quay trở lại để xem xét những khái niệm khác nhau này với những ý nghĩa và hiểu biết bổ sung. Danh sách còn tiếp tục, không có lý do gì để nó phải ngừng lại cả. Một mục xa hơn bên dưới danh sách có thể giúp ích cho việc minh họa cho điều này. Chúng ta có thể nghĩ rằng ta đã biết tất cả mọi điều để nói về một chủ đề nhất định, nhưng những vẫn luôn có những góc nhìn mới ở đâu đó. Hơn thế nữa, một hình ảnh rõ ràng trong sáng của người này lại là nỗi ám ảnh với người khác: 37: Đạo hàm của một hàm số thực f trong một miền D là thành phần Lagrange của phân thớ đối tiếp xúc T .D/ mà đưa ra dạng liên thông cho liên thông dẹt trên R phân thớ tầm thường D R mà ở đó đồ thị của f là song song. Những khác biệt này không phải chỉ là sự tò mò. Suy nghĩ của con người và tri thức không vận hành trên một đường đơn lẻ, giống như chiếc máy vi tính với duy nhất một bộ vi xử lý. Não bộ và tâm trí chúng ta có vẻ như được tổ chức trong một mớ những thành phần riêng biệt đầy sức mạnh. Những thành phần này vận hành cùng nhau một cách lỏng lẻo, “truyền đạt” cho nhau ở mức tổ chức cao thay vì ở mức tổ chức thấp. Dưới đây là một cách phân loại chính, có vai trò quan trọng trong việc tư duy toán học .1/ Ngôn ngữ của con người. Chúng ta có những phương tiện có mục tiêu đặc trưng và đầy sức mạnh cho việc nói và hiểu về ngôn ngữ của con người, những thứ cũng gắn với việc đọc và viết. Phương tiện ngôn ngữ của chúng ta là một công cụ quan trọng cho việc tư duy, chứ không chỉ riêng cho việc giao tiếp. Một ví dụ thô đó là công thức nghiệm của phương trình bậc hai một ẩn, mà nhiều người có thể vẫn còn nhớ qua câu hát ngắn, "ex equals minus bee plus or minus the square root of bee squared minus four ay see over two ay" .x bằng với trừ b cộng trừ căn bậc hai của b bình phương trừ bốn ac trên hai a/: Ngôn ngữ toán học của các ký hiệu được gắn kết chặt chẽ với phương tiện ngôn ngữ của con người. Giữa những ký hiệu toán học phân mảnh, thứ có ý nghĩa với hầu hết sinh viên học giải tích chỉ là một động từ, D : Đây là lý do vì sao các sinh viên lại sử dụng nó khi họ thấy cần một động từ. Hầu hết những ai đã dạy lý thuyết vi phân và tích phân ở Mỹ đều đã từng thấy các sinh viên viết một cách bản năng kiểu như x3 D 3x2 hay đại loại tương tự như vậy. .2/ Tầm nhìn, cảm quan không gian, cảm quan vận động. Con người có những phương tiện mạnh để thu nạp thông tin một cách trực quan hay theo cảm quan vận động, và tư duy với cảm quan không gian của họ. Mặt khác, họ không có một có một công cụ sẵn có thực sự tốt để đảo ngược góc nhìn, tức là chuyển một hiểu biết nội tại về không gian thành một bức ảnh hai chiều. Hệ quả là, các nhà toán học thường có ít hình vẽ hơn hoặc có hình vẽ xấu hơn trong các bài báo hay những cuốn sách của họ so với trong đầu họ. 66 Tạp chí Epsilon, Số 04, 08/2015 Một hiện tượng thú vị trong việc tư duy về không gian đó là kích thước tạo nên khác biệt lớn. Chúng ta có thể nghĩ về những vật thể nhỏ bé trong bàn tay mình, hay những cấu trúc to lớn hơn như cỡ cơ thể người mà chúng ta quét, hay về các cấu trúc không gian bao quanh chúng ta mà ta chuyển động quanh bên trong. Chúng ta có khuynh hướng tư duy một cách hiệu quả hơn với hình ảnh về không gian trên một thang kích thước lớn hơn: như là nếu não bộ của chúng ta tiếp nhận những thứ to lớn hơn một cách chặt chẽ hơn và có thể dành cho chúng nhiều năng lượng hơn. .3/ Lô-gic và diễn dịch. Chúng ta có một số cách thức sẵn có để suy luận và sắp xếp mọi thứ cùng nhau liên quan với cách mà chúng ta đưa ra các suy luận lô-gic: Nguyên nhân và kết quả (liên quan với những gì ẩn dấu), phản chứng hay phủ định, .. Có vẻ như các nhà toán học không hoàn toàn dựa trên những quy tắc hình thức của suy luận như là họ nghĩ. Thay vì vậy, họ giữ một lượng rất ít cấu trúc lô-gic của một phép chứng minh trong tâm trí họ, phân các phép chứng minh thành những kết quả trung gian mà nhờ đó họ không phải giữ quá nhiều lô-gic cùng một lúc. Thực tế, thường thấy rằng nhiều nhà toán học xuất chúng còn không biết đến cách dùng các lượng từ thế nào cho chuẩn(với mọi hay tồn tại,) nhưng tất cả các nhà toán học đều thực hiện được những suy luận mà họ đã mã hóa. Thật thú vị là mặc dù "hoặc", "và" hay "suy ra" có những cách sử dụng hình thức như nhau, chúng ta lại nghĩ về "hoặc" hay "và" như là liên từ, còn "suy ra" là một động từ. .4/ Trực giác, liên hệ, ẩn dụ. Con người có những công cụ tuyệt vời để cảm nhận về nhiều thứ mà họ không cần biết nó đến từ đâu (trực giác), để cảm nhận về những hiện tượng hay tình cảnh hay đối tượng nào đó giống thứ gì khác (liên hệ), và để xây dựng hay kiểm tra những liên kết và so sánh, mang trong tâm trí hai thứ cùng một lúc (ẩn dụ). Những công cụ này là khá quan trọng với toán học. Với riêng tôi, tôi đã dành nhiều nỗ lực để "lắng nghe" trực giác và tư duy liên hệ của mình, rồi xây dựng chúng thành những ẩn dụ và liên kết. Việc này bao hàm một kiểu tập trung và giữ tâm trí bình lặng một cách đồng thời. Ngôn từ, logic và những bức tranh chi tiết rầm rập chạy quanh có thể ngăn chặn trực giác và tư duy liên hệ. .5/ Kích thích-phản ứng. Điểm này thường được nhấn mạnh ở trong các trường học; chẳng hạn, nếu bạn thấy 3927 253; bạn viết số này lên trên số kia và vẽ một đường thẳng bên dưới, v.v. Đây cũng là một điều quan trọng trong nghiên cứu toán học: nhìn thấy hình vẽ của một nút, tôi sẽ viết ra một biểu diễn cho nhóm cơ bản của phần bù của nó bằng một quy trình tương tự với thuật toán nhân. .6/ Tiến trình và thời gian. Chúng ta có một công cụ để nghĩ về những quá trình hay một chuỗi những hành động có thể thường được dùng để thu được hiệu quả tốt trong suy luận toán học. Một cách hiểu về hàm số: đấy là một tác động, một quá trình, đi từ miền xác định tới miền giá trị. Suy nghĩ này thực sự có giá trị khi lấy hợp thành của các hàm số. Một ứng dụng khác của công cụ này đó là ghi nhớ những phép chứng minh: người ta thường ghi nhớ một phép chứng minh như một quá trình bao gồm một vài bước. Trong tôpô, khái niệm đồng luân thường hay được hiểu nhất là như một quá trình theo thời gian. Xét về mặt toán học, thời gian cũng không khác gì với việc thêm vào một trục tọa độ không gian, nhưng bởi vì con người tương tác với nó theo một cách tương đối khác, nên nó lại rất khác về mặt tâm lý. 67 Tạp chí Epsilon, Số 04, 08/2015 3. Hiểu biết toán học được truyền đạt nhứ thế nào Việc truyền đạt hiểu biết từ người này sang người khác là không tự động. Nó khó khăn và mẹo mực. Bởi vậy, để phân tích hiểu biết của con người về toán học, việc quan trọng là phải biết ai hiểu, hiểu gì, và khi nào thì hiểu. Các nhà toán học đã phát triển những thói quen giao tiếp, thường hơi ... bất bình thường. Bất cứ ở đâu những nhà tổ chức hội thảo cũng động viên người trình bày giải thích nội dung bằng những thuật ngữ cơ bản. Tuy nhiên, hầu như thính giả ở hội thảo cỡ trung bình nhận được ít giá trị từ nó. Có lẽ họ đã mất dấu sau năm phút đầu tiên, và ngồi im lặng trong 55 phút còn lại. Hay có lẽ họ nhanh chóng mất hứng thú bởi vì người báo cáo đi quá sâu vào chi tiết mà không đưa ra bất kỳ suy luận nào để đánh giá chúng. Ở cuối buổi báo cáo, chỉ một số ít các nhà toán học làm gần với lĩnh vực của báo cáo viên đặt một hay hai câu hỏi để tránh khỏi phải xấu hổ. Quy luật này cũng tương tự với những gì thường xảy ra trong lớp học, khi chúng ta nói về thực trạng rằng chúng ta nghĩ các sinh viên "phải" học, trong khi các sinh viên lại cố gắng nắm lấy những vấn đề cơ bản hơn trong việc học ngôn ngữ của chúng ta và dự đoán mô hình tư duy của chúng ta. Các cuốn sách bù đắp cho việc này bằng cách đưa ra cách giải tất cả các dạng bài tập về nhà. Các giáo sư bù đắp lại bằng cách đưa ra các bài tập về nhà và bài kiểm tra thường là dễ hơn những gì được "phủ" trong khóa học, và sau đó cho điểm bài tập về nhà và bài kiểm tra theo một thang điểm đòi hỏi rất ít sự thấu hiểu. Chúng ta cho rằng vấn đề nằm ở các sinh viên chứ không phải ở cách truyền đạt: Rằng các sinh viên hoặc không đủ khả năng để nắm bắt, hoặc là chẳng thèm quan tâm. Những người ngoại đạo thấy ngạc nhiên với hiện tượng này, nhưng bên trong cộng đồng toán học, chúng ta gạt bỏ nó bằng những cái nhún vai. Khó khăn lớn nhất nằm ở ngôn ngữ và văn hóa toán học, những thứ được chia thành các ngành hẹp. Những khái niệm cơ bản được sử dụng hàng ngày trong một ngành hẹp này có thể là ngoại ngữ với ngành hẹp khác. Các nhà toán học từ bỏ việc cố gắng hiểu những khái niệm căn bản thậm chí là của ngành hẹp lân cận, trừ phi họ phải hướng dẫn học viên sau đại học. Ngược lại, sự trao đổi diễn ra rất tốt bên trong những ngành hẹp của toán học. Trong một ngành hẹp, người ta xây dựng một cây tri thức chung và những kỹ thuật đã biết. Bằng giao tiếp không hình thức, người ta học cách hiểu và sao chép những cách suy nghĩ của nhau, do vậy những ý tưởng có thể được giải thích một cách sáng sủa và dễ dàng. Tri thức toán học có thể được truyền giao nhanh một cách đáng ngạc nhiên bên trong một ngành hẹp. Khi một định lý đáng chú ý được chứng minh, thường (nhưng không phải luôn luôn) xảy ra chuyện lời giải có thể được trao đổi trong vài phút từ người này sang người khác trong cùng một ngành đó. Chứng minh tương tự có thể được trao đổi và hiểu một cách tổng quan sau bài giảng kéo dài khoảng một giờ cho những thành viên trong ngành. Nó có thể là chủ đề của một bài báo 15 đến 20 trang, mà có thể được đọc và hiểu chỉ sau vài giờ hay có thể là vài ngày đối với thành viên của ngành hẹp. Tại sao lại có một sự phát triển lớn từ những thảo luận không chính thức tới bài báo cáo rồi tới bài báo? Một cách trực tiếp, người ta sử dụng những kênh trao đổi rộng rãi, đi xa hơn ngôn ngữ toán học hình thức. Họ sử dụng cử chỉ, họ vẽ các hình vẽ và lược đồ, họ tạo ra hiệu ứng âm thanh và sử dụng ngôn ngữ cơ thể. Sự trao đổi có vẻ tựa như là theo hai hướng, do vậy người ta có thể tập trung vào những gì mà họ cần chú ý hơn. Với những kênh thông tin này, họ có được 68 Tạp chí Epsilon, Số 04, 08/2015 vị thế tốt hơn nhiều để tuyền tải những gì đang diễn ra, không chỉ bằng những công cụ lô-gic và ngôn ngữ của họ mà bằng cả những công cụ tinh thần nữa. Khi báo cáo, người ta bị hạn chế hơn và cũng hình thức hơn. Các thính giả toán học thường không giỏi đặt các câu hỏi hay xuất hiện trong tâm trí con người, còn người báo cáo lại thường có bản đề cương soạn sẵn không thực tế ngăn cản họ nghĩ về các câu hỏi hay thậm chí là khi họ bị hỏi. Trong bài báo, người ta còn hình thức hơn. Những người viết bài dịch các ý tưởng của họ thành ký hiệu và suy luận lô-gic, còn người đọc thì lại cố gắng dịch ngược lại. Tại sao lại có sự không nhất quán giữa trao đổi trong một ngành hẹp với những trao đổi bên ngoài những ngành hẹp đó, nếu không muốn nói đến trao đổi bên ngoài toán học ? Theo một nghĩa nào đó thì Toán học có một ngôn ngữ chung: Ngôn ngữ của các ký hiệu, những định lý, tính toán mang tính kỹ thuật, và lô-gic. Ngôn ngữ này truyền tải hiệu quả một số, nhưng không phải tất cả, các trạng thái tư duy toán học. Các nhà toán học học từ việc dịch gần như vô thức một số thứ nhất định từ một trạng thái tinh thần này tới trạng thái khác, do vậy các mệnh đề nhanh chóng trở nên rõ ràng. Những nhà toán học khác nhau nghiên cứu các bài báo theo những cách khác nhau, nhưng khi tôi đọc một bài báo trong một lĩnh vực mà tôi thành thạo, thì tôi tập trung vào những suy nghĩ giữa các dòng kiến thức. Tôi có thể nhìn vào một vài đoạn hay chuỗi các phương trình và tự nhủ rằng “À phải rồi, họ đã đưa vào đủ những lời dẫn phức tạp để bước theo những ý tưởng như thế này.” Khi ý tưởng là rõ ràng, cách thiết lập hình thức lại thường là không cần thiết và rườm rà – tôi thường cảm thấy rằng tôi có thể tự viết nó ra một cách dễ dàng hơn so với việc khám phá xem các tác giả thực sự viết gì. Nó cũng giống như một thợ làm bánh tập sự thử với một tờ hướng dẫn dài 16 trang vậy. Nếu bạn hiểu các người thợ làm bánh và bạn gặp một người thợ làm bánh tập sự, bạn sẽ thấy anh ta đưa nguyên liệu vào và xem nó có phù hợp hay không thay vì trước tiên phải đọc tất cả những chi tiết trong sách hướng dẫn. Những người quen với các phương thức làm việc khác nhau trong một ngành hẹp nhận biết những quy luật đa dạng của các mệnh đề hay công thức như là thành ngữ hay lối diễn đạt cho một số khái niệm hay hình ảnh trí tuệ nào đó. Nhưng với nhiều người không quen với những gì đang diễn ra, cùng những quy luật như thế lại không mấy sáng tỏ; thậm chí chúng còn thường gây nhầm lẫn. Ngôn ngữ không còn tồn tại ngoại trừ với người đang sử dụng nó. Ở đây, tôi muốn nhắc đến một chú ý quan trọng: Có một số nhà toán học, những người quen thuộc với những cách tư duy trong nhiều hơn một ngành hẹp, đôi khi là nhiều ngành như thế. Một số nhà toán học học được biệt ngữ của vài ngành hẹp khi là học viên cao học, một số lại nhạy bén với việc thu nạp những ngôn ngữ và văn hóa toán học của ngành khác còn một số khác thì lại ở các trung tâm của toán học nơi mà họ được tiếp xúc với rất nhiều ngành hẹp. Những người có thể làm việc thoải mái với nhiều hơn một ngành hẹp thường có một ảnh hưởng rất tích cực, họ bắc những cây cầu hay giúp đỡ những nhóm các nhà toán học học hỏi lẫn nhau. Nhưng khả năng hiểu biết của con người trong đa lĩnh vực có thể có ảnh hưởng tiêu cực, qua việc dọa dẫm người khác, hay giúp phê chuẩn và duy trì một hệ thống giao tiếp kém. Chẳng hạn, một hiệu ứng thường xuất hiện trong những buổi hội thảo chuyên đề, khi một hay hai người có hiểu biết rộng rãi ngồi ở hàng đầu có thể đóng vai trò như là người dẫn dắt tinh thần của báo cáo viên cho thính giả. Có một hiệu ứng khác, có nguồn gốc từ những khác biệt lớn giữa cách chúng ta nghĩ về toán học và cách chúng ta viết nó. Một nhóm các nhà toán học tương tác với nhau có thể giữ một tập hợp các ý tưởng toán học tồn tại trong một quãng thời gian vài năm, mặc dù những phiên bản 69 Tạp chí Epsilon, Số 04, 08/2015 ghi chép về công trình toán học của họ khác với những gì họ thực sự nghĩ, lại nhấn mạnh nhiều hơn rất nhiều vào ngôn ngữ, ký hiệu, lô-gic và tính hình thức. Nhưng khi những nhóm các nhà toán học mới học về chủ đề này, họ có khuynh hướng mô tả những gì họ đọc và nghe bằng lời, do vậy những hình thức và cơ cấu có thể dễ dàng ghi lại hay trao đổi sẽ có khuynh hướng lấn át các hình thức tư duy khác. Có hai thước đo cho khuynh hướng này, do vậy toán học không hoàn bị đẩy vào tình thế khó khăn trong vấn đề hình thức. Thứ nhất, các thế hệ nhà toán học trẻ hơn đang tiếp tục tự khám phá và tái khám phá những cách nhận thức, do vậy đan cài lại những trạng thái tư duy đa dạng của con người vào toán học. Thứ hai, đôi khi các nhà toán học sáng tạo ra những cái tên và tình cờ thống nhất những định nghĩa mà thay thế các diễn đạt luẩn quẩn mang tính kỹ thuật và đưa ra những cách luận giải tốt cho các cách nhận thức. Những cái tên như “nhóm” để thay thế cho “một hệ các phép thế thỏa mãn ...”, và “đa tạp” để thay thế cho Chúng ta không thể đưa ra các tọa độ để tham số hóa một cách đồng thời tất cả các nghiệm của những phương trình của mình, nhưng trong lân cận của bất kỳ một nghiệm cụ thể nào ta có thể đưa ra các tọa độ f1.u1; u2; u3/; f2.u1; u2; u3/; f3.u1; u2; u3/; f4.u1; u2; u3/; f5.u1; u2; u3/ trong đó có ít nhất một trong mười định thức ... Œ10 định thức 3 3 cho các ma trận của những đạo hàm riêng] là khác không. có thể hoặc không thể diễn đạt được những đột phá trong nhận thức của các chuyên gia, nhưng chúng làm giảm rất nhiều những khó khăn trong việc trao đổi nhận thức. Các nhà toán học cần phải dồn thêm nhiều tâm sức hơn nữa vào việc trao đổi các ý tưởng. Để hoàn thành việc này, chúng ta cần phải chú ý nhiều hơn tới việc trao đổi không chỉ những định nghĩa, định lý, và chứng minh, mà còn cả cách tư duy của mình nữa. Ta cần phải đánh giá đúng giá trị của những cách tư duy khác nhau về cùng một cấu trúc toán học. Chúng ta cần phải tập trung thật nhiều năng lượng hơn nữa cho việc hiểu và giải thích các cơ sở tinh thần căn bản của toán học – và hệ quả là dành ít hơn năng lượng cho các kết quả mới. Điều này dẫn đến sự phát triển ngôn ngữ toán học mà có hiệu quả cho mục đích nguyên sơ của việc truyền giao ý tưởng cho những người chưa biết. Một phần trong việc trao đổi này là qua các chứng minh. 4. Thế nào là một phép chứng minh Khi tôi mới bắt đầu vào học sau đại học ở Berkeley, tôi có vấn đề với việc tưởng tượng làm thế nào mình có thể “chứng minh” một định lý toán học mới và thú vị. Tôi không thực sự hiểu thế nào là một “phép chứng minh”. Qua việc đi seminar, đọc các bài báo, và trò chuyện với các học viên sau đại học khác, tôi dần dần nắm được vấn đề. Trong bất kỳ ngành nào, có một số định lý và kỹ thuật nhất định được biết đến và chấp nhận rộng rãi. Khi bạn viết một bài báo, bạn nhắc đến chúng mà không cần dẫn chứng minh. Bạn nhìn vào những bài báo khác trong ngành, bạn thấy những cơ sở lập luận mà họ trích lại không kèm chứng minh, và những gì họ trích dẫn trong phần tài liệu tham khảo. Bạn học vài ý tưởng về các phép chứng minh từ những người khác. Và rồi bạn có thể tự do trích lại cùng định lý đó và cùng những trích dẫn kia. Bạn không cần phải đọc toàn bộ những bài báo hay các cuốn sách trong phần tài liệu tham khảo của bạn. Có rất nhiều thứ được biết đến rộng 70 Tạp chí Epsilon, Số 04, 08/2015 rãi là những thứ mà không còn văn bản nguồn được biết đến nữa. Chừng nào mà những người làm việc trong ngành đó còn thấy thoải mái vì những ý tưởng đó thực sự có tác dụng, nó không cần phải có một văn bản nguồn chính thức. Đầu tiên, tôi đã thực sự rất nghi ngờ quá trình này. Tôi đã ngờ rằng liệu có một ý tưởng nào thực sự được công bố hay chưa. Nhưng tôi thấy rằng tôi có thể hỏi mọi người và họ có thể đưa ra những giải đáp và chứng minh, hoặc có thể giới thiệu tôi tới ai đó khác hay tới những văn bản nguồn mà có cung cấp những lời giải thích hay các chứng minh. Có những định lý đã được công bố mà cũng được biết đến rộng rãi là không chính xác hay những chứng minh là không hoàn thiện. Tri thức và hiểu biết toán học được ẩn trong tâm trí và trong kết cấu xã hội của cộng đồng những người nghiên cứu một chủ đề nhất định. Tri thức toán học này được hỗ trợ bởi những văn bản lưu trữ, nhưng những tài liệu ấy cũng không thực sự chính yếu. Tôi nghĩ mẫu hình này thay đổi chút ít qua từng ngành. Tôi đã quan tâm đến lĩnh vực hình học của toán học, nơi bây giờ rất hiếm tìm được một tài liệu phản ánh tốt cách thức mà người ta thực sự tư duy. Trong những lĩnh vực đại số hơn hay mang tính ký hiệu nhiều hơn, thì không nhất thiết phải như thế, và tôi có ấn tượng rằng trong nhiều lĩnh vực, các tài liệu thực sự gần như là xương sống của ngành. Nhưng trong lĩnh vực nào cũng có một tiêu chuẩn xã hội mạnh cho tính hợp lệ và sự đúng đắn. Chứng minh của Andrew Wiles cho Định lý cuối cùng của Fermat là một ví dụ minh họa tốt cho điều này, trong một lĩnh vực mang nhiều tính đại số. Các chuyên gia nhanh chóng tin rằng chứng minh của ông căn bản là đúng trên nền tảng của những ý tưởng cao cấp, từ rất lâu trước khi những chi tiết trong chứng minh có thể được kiểm chứng. Chứng minh này sẽ nhận được rất nhiều sự xem xét và kiểm tra kỹ lưỡng so với hầu hết các phép chứng minh toán học khác, nhưng bất kể quá trình kiểm tra hé lộ điều gì, nó cũng giúp minh họa xem toán học tiến triển thế nào qua những hệ thống tâm lý học và quá trình xã hội học. Khi mọi người làm toán, dòng các ý tưởng và tiêu chí xã hội cho giá trị và sự chính xác là đáng tin cậy hơn nhiều so với những tài liệu hình thức. Người ta thường không giỏi lắm trong việc kiểm tra tính đúng đắn hình thức của các phép chứng minh, nhưng họ lại khá chính xác trong việc phát hiện những điểm yếu tiềm tàng hay những lỗi sai trong các phép chứng minh ấy. Để tránh giải thích sai, tôi muốn nhấn mạnh vào hai thứ mà tôi không đang nói đến. Trước tiên, tôi không bào chữa cho bất kỳ yếu kém nào của tiêu chí chuẩn về phép chứng minh của cộng đồng chúng ta, mà tôi đang cố gắng diễn tả quá trình chứng minh ấy thực sự vận hành như thế nào. Các phép chứng minh cẩn thận mà sẽ chống lại sự soi xét là rất quan trọng. Tôi nghĩ rằng, nếu xét toàn thể, quá trình của các phép chứng minh vận hành khá tốt trong cộng đồng toán học. Kiểu thay đổi mà tôi muốn bào chữa là các nhà toán học cẩn thận hơn với các phép chứng minh của họ, làm cho chúng rõ ràng và đơn giản nhất có thể và nhờ đó nếu bất kỳ điểm yếu nào xuất hiện, thì cũng dễ dàng được phát hiện. Thứ hai, tôi không phê bình nghiên cứu toán học của các chứng minh hình thức, tôi cũng không phê bình những người dành năng lượng vào việc tạo ra những luận điểm toán học ngày một cụ thể và hình thức hơn. Chúng đều là những hoạt động có ích mà soi rọi những nhận thức mới về toán học. Tôi đã khá nỗ lực trong nhiều quá trình của sự nghiệp của mình để khám phá những câu hỏi toán học bằng máy tính. Theo quan điểm của kinh nghiệm này, tôi đã ngạc nhiên khi thấy mệnh đề của Jaffe và Quinn rằng toán học là vô cùng chậm chạp và khó khăn, và rằng có thể xác minh được rằng nó là hoạt động mang tính chặt chẽ nhất trong tất cả các hoạt động của con người. Tiêu chuẩn cho sự chính xác và hoàn thiện để có được một chương trình máy tính vận hành được ở mức cao hơn hai lần so với tiêu chuẩn của cộng đồng toán học cho các phép chứng minh đúng 71 Tạp chí Epsilon, Số 04, 08/2015 đắn. Tuy nhiên, những chương trình máy tính lớn, thậm chí khi chúng đã được viết và kiểm tra một cách rất cẩn thận, thì lại luôn có vẻ như có lỗi. Tôi nghĩ rằng toán học là một trong những phần thưởng trí tuệ lớn nhất trong các hoạt động của con người. Bởi vì chúng ta có một tiêu chuẩn cao cho sự rõ ràng và thuyết phục của tư duy và do chúng ta đặt một tiêu chuẩn cao trong việc lắng nghe và cố gắng tiếp thu lẫn nhau, chúng ta không tham gia vào những luận điểm dài dòng hay làm đi làm lại những vấn đề toán học của mình. Chúng ta được chuẩn bị để được thuyết phục bởi những người khác. Nói một cách trí tuệ, toán học chuyển động rất nhanh. Toàn bộ cảnh quan toán học thay đổi liên tục theo những cách đáng ngạc nhiên trong suốt một sự nghiệp đơn lẻ. Khi ta biết là viết một chương trình máy tính tiếp cận mục tiêu trí thức của một bài báo toán học tốt khó đến thế nào, và sẽ phải tốn nhiều nỗ lực và thời gian để biến nó thành “gần như” đúng một cách hình thức, thật phi lý khi khẳng định rằng toán học mà chúng ta đang thực hành lại không ở đâu gần đúng một cách hình thức. Toán học mà chúng ta thực hành, một cách hình thức là hoàn thiện hơn rất nhiều và chính xác hơn nhiều ngành khoa học khác, nhưng nó thiếu hoàn thiện và chính xác một cách hình thức so với các phần mềm máy tính. Sự khác biệt không chỉ liên quan tới mức độ nỗ lực: kiểu nỗ lực khác biệt về lượng. Trong những phần mềm máy tính đồ sộ, một lượng nỗ lực khủng khiếp phải được sử dụng cho vô số vấn đề về tính tương thích: đảm bảo rằng tất cả các định nghĩa là nhất quán, phát triển những cấu trúc dữ liệu “tốt” mà hữu ích nhưng phần đông không làm vướng víu, quyết định trên sự tổng quát “phù hợp” cho các hàm số, etc. Tỉ lệ năng lượng sử dụng trên phần hoạt động của một phần mềm đồ sộ, để phân biệt với phần tínhtoán, là nhỏ đáng ngạc nhiên. Bởi vì những vấn đề tương thích mà hầu như chắc chắn vượt quá tầm kiểm soát do những định nghĩa "chuẩn" thay đổi khi nguyên tắc chung và phạm vi vận hành được thêm vào, các phần mềm máy tính hay cần phải được viết lại thường xuyên, thường là từ những hỗn độn. Một kiểu nỗ lực tương tự có lẽ đã đi vào toán học để giúp toán học đúng đắn, hoàn thiện một cách hình thức. Không phải sự chính xác về mặt hình thức là khó đến không vượt qua được dưới thang kích thước nhỏ - mà là có rất nhiều sự lựa chọn khả dĩ cho sự hình thức hóa trên những thang kích thước nhỏ mà có thể dịch sang số lượng khổng lồ của lựa chọn độc lập trong thang kích thước lớn. Việc làm cho những lựa chọn này tương thích với nhau là rất khó, làm như thế sẽ chắc chắn dẫn đến việc quay ngược lại và viết lại từ hỗn độn tất cả những bài báo toán học cũ có những kết quả chúng ta phải phụ thuộc vào. Cũng khá khó khăn để đưa ra những lựa chọn kỹ thuật cho các định nghĩa mang tính hình thức thích hợp với những cách thức đa dạng mà các nhà toán học muốn sử dụng chúng và điều này sẽ thúc đẩy sự mở rộng trong tương lai của toán học. Nếu chúng ta tiếp tục cộng tác, hầu hết thời gian của chúng ta sẽ được dành cho những hội đồng tiêu chuẩn quốc tế để thiết lập những định nghĩa thống nhất và giải quyết những vấn đề gây tranh cãi khổng lồ. Các nhà toán học có thể và thực sự khỏa lấp được những cách biệt, sửa chữa các lỗi, cung cấp thêm những chi tiết, phương pháp khoa học cẩn thận hơn khi họ được chọn hay thúc đẩy để làm như thế. Hệ thống của chúng ta làm khá tốt việc đưa ra những định lý tin cậy được mà có thể được lưu trữ một cách chắc chắn. Chỉ là tính tin cậy được không hoàn toàn đến từ chuyện các nhà toán học kiểm tra một cách hình thức các luận điểm hình thức, nó đến từ những nhà toán học suy nghĩ cẩn trọng, có phản biện về các ý tưởng toán học. Ở một mức độ nền tảng, những cơ sở của toán học là rất thiếu vững chãi so với thứ toán học mà chúng ta nghiên cứu. Hầu hết các nhà toán học bám lấy những nguyên lý mà được biết đến như là những hư cấu tao nhã. Chẳng hạn, có một định lý nói rằng không tồn tại cách nào để thực sự xây dựng hay thậm chí là định nghĩa một thứ tự tốt trên tập hợp số thực. Có một nguyên nhân 72 Tạp chí Epsilon, Số 04, 08/2015 đáng kể (nhưng không có chứng minh) rằng chúng ta có thể bỏ những hư cấu này đi mà cũng không sao cả, nhưng điều này cũng không giúp chúng trở nên chính xác được. Các nhà tập hợp xây dựng nhiều những "hoàn vũ toán học" mâu thuẫn xen kẽ và đan cài lẫn nhau sao cho nếu một trong số đó mà nhất quán thì những cái còn lại cũng thế. Việc này để lại rất ít độ tin cậy rằng hoàn vũ này hay hoàn vũ khác là lựa chọn đúng đắn hay lựa chọn tự nhiên. Định lý bất toàn của Kurt Godel hàm ý rằng không thể có hệ hình thức nào lại nhất quán được, nhưng lại đủ mạnh để có thể phục vụ như một cơ sở cho tất cả toán học mà chúng ta nghiên cứu. Đối nghịch với con người, máy tính lại giỏi thực hiện những quá trình hình thức. Một số người đang tích cực làm việc trong dự án hình thức hóa một cách thực sự các phần của toán học bằng máy tính, với những suy diễn hình thức chính xác. Tôi nghĩ rằng đây là một dự án lớn, rất đáng giá và tôi tự tin rằng chúng ta sẽ học được rất nhiều từ đó. Quá trình này sẽ giúp đơn giản hóa và làm toán học sáng sủa hơn. Không lâu nữa, tôi kỳ vọng chúng ta sẽ có những phần mềm máy tính mang tính tương tác mà có thể giúp con người dịch mã những khó khăn của toán học chính xác và hoàn thiện một cách hình thức (dựa trên một ít những giả định có lẽ vẫn yếu nhưng chí ít là cụ thể), và rằng chúng sẽ trở thành một phần của môi trường làm việc chuẩn của nhà toán học. Tuy nhiên, chúng ta nên nhận thấy rằng những chứng minh có thể hiểu được và có thể kiểm chứng được dưới góc độ của con người mà chúng ta thực sự làm được là những thứ quan trọng nhất với chúng ta và chúng khá khác biệt với những chứng minh hình thức. Hiện tại, những chứng minh hình thức vẫn nằm ngoài tầm với và hầu như không thích hợp: chúng ta có những quá trình đủ tốt của con người để kiểm chứng tính chính xác toán học. (Còn tiếp) ... 73 Tạp chí Epsilon, Số 04, 08/2015 74 ỨNG DỤNG CỦA XÁC SUẤT Huỳnh Xuân Tín (Trường THPT Chuyên Lương Văn Chánh, Phú Yên) 1. Mở đầu Các số Ramsey R.k; l/ được chỉ ra là luôn tồn tại với mọi k; l 2 N, nhưng chỉ rất ít trong các số đó là được biết giá trị chính xác. Năm 1947, P. Erdos đã đưa ra một chứng minh cho cận dưới ˝ của số Ramsey dạng đối xứng bằng một phương pháp mới lúc bấy giờ: phương pháp xác suất. Bài toán như sau: Định lý 1. Với mọi số nguyên dương k 3, ta có R.k; k/ > 2 k2 . Chứng minh. Đặt G D Kn; n 2k2 , và xét 2 tô màu cạnh cho G một cách ngẫu nhiên (mỗi cạnh được tô đỏ hoặc xanh ngẫu nhiên với xác suất 12). Ta chứng minh tồn tại ít nhất một cách 2tô màu cho G sao cho nó không chứa đồ thị con Kk cùng màu. Gọi S là một Kk-đồ thị con của G, đặt AS là biến cố chỉ S có cùng màu cạnh. Chú ý rằng, một Kk-đồ thị con của G có tất cả C2kcạnh, mỗi cạnh có 2 cách tô màu. Do đó PŒAS D22C2kD 21C2k : Theo tính chất của xác suất và chú ý rằng đồ thị G có tất cả Cknđồ thị con Kk, nên P h[ SAS i XSPŒAS D Ckn 21C2k : Ta chứng minh Ckn 21C2k < 1. Ta có Ckn D.n k C 1/.n k C 2/ .n 1/n kŠ Dnk kŠ : (1.1) Suy ra kŠ 3. Ta chứng minh bất đẳng thức đúng với k vì kŠ D 2 2k1 2 2k2 do đó 2 212 .k 1/Šk < 2 212 k<3k 1; 2 2k2 kŠ < 1; 8k 3: (1.3) Từ (1.1), (1.2), (1.3) suy ra Ckn 21C2k < 1; 8k 3, bài toán được chứng minh. Gần đây, phương pháp xác suất đã phát triển mạnh mẽ và trở thành một công cụ hữu hiệu để giải quyết các bài toán tổ hợp. Cơ sở của phương pháp xác suất có thể được diễn tả như sau: để chứng minh sự tồn tại của một cấu trúc tổ hợp thỏa tính chất nào đó, ta xây dựng một không gian xác suất thích hợp rồi chỉ ra rằng một phần tử với tính chất đã cho được chọn ngẫu nhiên trong không gian đó có xác suất dương. Trong tài liệu này, chúng tôi cũng đề cập đến một số ứng dụng của phương pháp xác suất trong tổ hợp, đặc biệt là chứng minh bài toán tồn tại. Nội dung chính là xem xét một số ứng dụng của phương pháp xác suất trong các bài toán tổ hợp và đồ thị theo hai hướng cơ bản: dựa vào định nghĩa xác suất và dựa vào tính chất của kỳ vọng. Ngoài các bài toán về tổ hợp và đồ thị, tác giả cũng đã đưa thêm các bài toán mà có thể ứng dụng phương pháp này trong các lĩnh vực khác. 2. Phép chứng minh sử dụng định nghĩa xác suất Trước tiên ta cần mở rộng khái niệm đồ thị. Một siêu đồ thị là một cặp H D .V; E/, ở đây V là tập hữu hạn các phần tử được gọi là các đỉnh và E là họ các tập con của V gọi là các cạnh. H được gọi là n-siêu đồ thị đều nếu mỗi cạnh của nó chứa đúng n đỉnh. Ta nói rằng H thỏa tính chất B hoặc 2-tô màu được nếu có một cách 2-tô màu cho các đỉnh trong V sao cho không có cạnh nào cùng màu. Ký hiệu m.n/ là số cạnh nhỏ nhất của một n-siêu đồ thị đều không có tính chất B. Ta đi xác định cận dưới cho m.n/. Định lý 2. Mỗi n-siêu đồ thị đều với ít hơn 2n1cạnh có tính chất B. Do đó m.n/ 2n1: Chứng minh. Đặt H D .V; E/ là một n-siêu đồ thị đều với ít hơn 2n1cạnh. Tô màu ngẫu nhiên cho V bằng 2 màu (mỗi màu có xác suất được chọn là 12). Với mỗi cạnh e 2 E, đặt Ae là biến cố chỉ e có cùng màu. Khi đó PŒAe D22nD 21n: Do đó, xác suất để có ít nhất một cạnh trong E cùng màu là Xe2EPŒAe < 1; P tức là 1 P Se2E Ae > 0. h[ e2EAe i Điều này cho thấy rằng tồn tại một cách 2tô màu cho V sao cho không có cạnh cùng màu. 76 Tạp chí Epsilon, Số 04, 08/2015 Dưới đây là một số bài toán liên quan: Bài 1. Cho G D .V; E/ là đồ thị hai mảng n đỉnh với một tập S.v/ chứa nhiều hơn log2 n màu gắn với mỗi đỉnh v 2 V . Chứng minh rằng có một cách tô màu thích hợp cho G mà mỗi đỉnh v được tô một màu từ tập màu S.v/ của nó. Lời giải. Do G là đồ thị hai mảng nên tập V có thể phân hoạch thành hai tập rời nhau V1 và V2 sao cho mỗi cạnh trong G có một đỉnh trong V1 và một đỉnh trong V2, đặt S DS v2V tất cả các màu có thể. S.v/ là tập Xét phân hoạch ngẫu nhiên S D S1 [ S2, trong đó mỗi màu được chọn ngẫu nhiên, độc lập cho vào S1 hoặc S2 với xác suất bằng nhau (và bằng 12). Ta sẽ chứng minh tồn tại một phân hoạch của S sao cho tất cả các đỉnh trong Vi; i D 1; 2, có thể được tô màu bằng các màu trong Si; i D 1; 2. Lấy v 2 Vi; i D 1; 2; khi đó xác suất để không có màu nào trong tập màu S.v/ nằm trong Si xác định bởi: Vậy ta có PŒS.v/ \ Si D ; D h[ 1 2 jS.v/j <1n; (do jS.v/j > log2 n). i P v2VifS.v/ \ Si D ;g 2; 014 log2 n > 0. Khi đó, ta có thể tô màu mỗi cạnh của Kn;n là đỏ hoặc xanh sao cho không có đồ thị con Km;m có cùng màu cạnh được tạo thành. Lời giải. Đồ thị Km;m có 2m đỉnh và m2cạnh, do đó số cách để 2-tô màu cạnh cho đồ thị con Km;m của đồ thị Kn;n là 2m2, và trong các cách tô màu đó chỉ có 2 kết quả thuận lợi để được Km;m cùng màu. Suy ra, xác suất để được Km;m cùng màu cạnh là 2 2m2 D 21m2: Đồ thị Kn;n có .C m n/2 đồ thị con Km;m, mỗi đồ thị con Km;m có khả năng cùng màu cạnh như nhau. Do đó, xác suất để có ít nhất một đồ thị con Km;m cùng màu luôn nhỏ hơn hoặc bằng .C m n/2 21m2. Do đó để chứng minh yêu cầu của bài toán, ta chỉ cần chứng minh .C m n/2 21m2< 1: Vì m > 2; 014 log2 n > 2, nên ta có 2.C m n/2 D 2 .n m C 1/.n m C 2/ .n 1/n mŠ 77 2 < n2m: Tạp chí Epsilon, Số 04, 08/2015 Vì m > 2; 014 log2 n > 2 log2 n, nên suy ra n2m < .2 m2 /2m: n/2 < n2m < .2 m2 /2m D 2m2: Từ 2 điều trên, suy ra 2.C m Bản chất của số 2; 014 trong điều kiện m > 2; 014 log2 n đó là nó lớn hơn 2: Bởi vậy, bất kì số 2 C ", với " > 0 nào đó đều có thể được. Bài 3. (Định lý Erdos - Ko - Rado) Nếu ˝ jXj D n; n 2k và F là họ giao nhau các k-tập con của X, tức là 8A; B 2 F; A \ B ¤ ;, thì ta có jFj Ck1 n1: Chứng minh. Ta cần bổ đề sau: Bổ đề 1. Xét X D f0; 1; : : : ; n 1g, và với 0 s < n, ta định nghĩa As D fs; s C 1; : : : ; s C k 1g X với phép cộng modulo n. Khi đó, với n 2k, thì bất kì họ giao nhau F các k-tập con của X đều chứa nhiều nhất k tập As. Thật vậy, Nếu Ai 2 F, thì bất kì tập As 2 F nào đó khác Ai phải là 1 trong số các tập AikC1; : : : ; Ai1 hoặc AiC1; : : : ; AiCk1. Có 2k 2 tập như thế, các tập này có thể được chia thành .k 1/ cặp có dạng .As; AsCk/. Vì n 2k; As \ AsCk D ; và chỉ có một tập trong mỗi cặp là có thể xuất hiện trong F, nên ta có điều phải chứng minh. Tiếp theo, giả sử X D f0; ; 1; : : : ; n 1g và F là họ giao nhau các k-tập con của X. Với một hoán vị W X ! X, ta định nghĩa .As/ D f .s/; .s C 1/; : : : ; .s C k 1/g; với phép cộng modulo n. Các tập .As/ chính là các tập nói trong bổ đề 3 với các phần tử được gán nhãn lại bởi hoán vị , do đó, theo bổ đề trên thì có nhiều nhất k trong số n tập này nằm trong F. Do đó, nếu chọn s độc lập, ngẫu nhiên và đều, thì PŒ .As/ 2 F kn: Nhưng việc chọn .As/ này tương đương với việc chọn ngẫu nhiên một k-tập con của X. Bởi vậy PŒ .As/ 2 F DjFj Ckn; và jFj D Ckn PŒ .As/ 2 F Ckn kn D Ck1 n1: Bài 4. Cho A1; A2; : : : ; An và B1; B2; : : : ; Bn là các tập con phân biệt của N sao cho jAij D k và jBij D l; 8 1 i n, với mỗi i, Ai \ Bi D ;, và với mỗi i ¤ j; Ai \ Bj ¤ ;: Chứng minh rằng n CkkCl: 78 Tạp chí Epsilon, Số 04, 08/2015 Lời giải. Đặt X DSn iD1 .Ai [ Bi/ và xét một cách sắp thứ tự các thành phần trong X một cách ngẫu nhiên (có tất cả jXjŠ cách sắp thứ tự có xác suất như nhau). Đặt Uilà biến cố chỉ mỗi phần tử của Ai đứng trước mỗi phần tử của Bi. Ta có PŒUi DCkCl jXj kŠ l Š .jXj k l/Š jXjŠD1 CkkCl; 1 i k: Ta cần chú ý rằng Ui và Uj không xảy ra đồng thời với i ¤ j . Thật vậy, giả sử Ui và Uj xảy ra đồng thời. Không mất tính tổng quát ta giả sử phần tử cuối cùng của Ai không đứng sau phần tử cuối cùng của Aj . Nhưng trong trường hợp này, tất cả các phần tử của Ai đều đứng trước tất cả các phần tử của Bj . Điều này mâu thuẫn với giả thiết Ai \ Bj ¤ ;. Vậy ta có 1 P SniD1 Ui DPniD1 PŒUi D n CkkCl: Bài 5. Cho A1; A2; : : : ; An và B1; B2; : : : ; Bn là các tập con phân biệt của N sao cho jAij D r và jBij D s; 8 1 i n, với mỗi i, Ai \ Bi D ;, và với mỗi i ¤ j; .Ai \ Bj / [ .Aj \ Bi/ ¤ ;: Chứng minh rằng n .r C s/rCs rr ss: Lời giải. Đặt X DSn iD1 .Ai [ Bi/. Định nghĩa p D r rCs, và xét một đồng xu có một mặt là A, một mặt là B với xác suất xuất hiện mặt A là p. Với mỗi phần tử trong X, ta tung đồng xu một cách độc lập, điều này xác định một ánh xạ f W X ! fA; Bg. Định nghĩa Eilà biến cố xảy ra khi tất cả các phần tử x 2 Ai có f .x/ D A và tất cả các phần tử y 2 Bi có f .y/ D B. Ta có PŒEi D pr .1 p/s; 1 i n: Chú ý rằng Ei và Ej không xảy ra đồng thời nếu i ¤ j , vì nếu ngược lại, thì sẽ có phần tử thuộc hoặc Ai \ Bj , hoặc Aj \ Bi, và nó không thể là A cũng không thể là B, mâu thuẫn. Do đó, các biến cố Ei rời nhau,Xn iD1 PŒEi D n pr.1 p/s: Suy ra 1 P h[n iD1Ei i DXniD1PŒEi D n pr.1 p/s; hay n pr .1 p/s D.s C r/sCr rr ss: Bài 6. Chứng minh rằng có một hằng số c > 0 với tính chất như sau. Cho A là ma trận n n có các phần tử đôi một khác nhau, thì có một hoán vị của các dòng của A sao cho không có cột nào trong ma trận hoán vị chứa một dãy con tăng độ dài ít nhất cpn. Lời giải. Ta cần chứng minh hai bổ đề sau: 79 Tạp chí Epsilon, Số 04, 08/2015 Bổ đề 2. Với mọi số n nguyên dương lớn hơn 1 thì n Chứng minh.. Bằng quy nạp, ta có nŠ > n e .n C 1/Š D nŠ.n C 1/ > n e n .n C 1/ D n C 1 e nC1 n n C 1 n e n C 1 nC1 1 n C 1 nC1 D e 1 C 1n n e > e (do e1n > 1 C 1n:) Bổ đề 3. Với n là số nguyên dương và n k, ta có Ckn 0 (sẽ được giới hạn sau), và ký hiệu Eilà tập của các hoán vị dòng cho ta ít nhất một dãy con tăng độ dài (ít nhất) cpn trong cột i. Hiển n dãy con độ dài cpn, và mỗi dãy con sẽ là dãy tăng với nhiên rằng, mỗi cột trong A có Ccpn xác suất 1 .cpn/Š, ta có PŒEi 1 .cpn/Š Ccpn n: Theo các bổ đề trên, ta có .cpn/Š > n 14 cpn e cpn ; Ccpn n < en cpn cpn D epn c cpn ; suy ra e PŒEi 1 .cpn/Š Ccpn n < c 2cpn n1=4: Do đó P h[ iEi i XiPŒEi < ec 2cpn n34 : Theo giả thiết bài toán, tức luôn có một hoán vị của các dòng của A sao cho không có cột nào trong ma trận hoán vị chứa một dãy con tăng độ dài ít nhất cpn, nên bắt buộc P h[ iEi i < 1: Vậy ta chỉ cần chọn c > e đủ lớn, suy ra điều cần chứng minh. Bài 7. Chứng minh rằng giữa 2100 người, không nhất thiết phải có 200 người đôi một quen nhau hoặc 200 người đôi một không quen nhau. 80