Về quan hệ giữa toán học và tin học - Hồ Tú Bảo

Toán học và Tin học1 Hồ Tú Bảo Viện Công nghệ Thông tin, Viện KH & CN Việt Nam Japan Advanced Institute of Science and Technology Về quan hệ giữa toán học và tin học Toán học và Tin học2 Toán học và tin học „ Vài lĩnh vực tiêu biểu của toán học trong tin học „ Toán học trong xử lý ngôn ngữ tự nhiên „ Toán học và Web „ Toán học trong sinh học „ Toán học trong học máy (machine learning) Toán học và Tin học3 hardware software Supercomputers, mainframes Cray Y-MP8E Minicomputers,workstations Phần mềm hệ thống Phần mềm ứng dụng Nhận dạng Thuật toán An toàn thông tin Cơ sở dữ liệu Trí tuệ nhân tạo DOS, Windows, Mac OS, UNIX, Linux Pascal,C, C++, Java, Máy tính song song Toán học cho tin học Kỹ nghệ phần mềm PC computers Mạng máy tính LAN, WAN, Internet Truyền thông Đại thể về tin học (khoa học máy tính) Tin sinh học Toán học và Tin học4 Hai con đường của toán trong tin học Các lý thuyết, mô hình toán học làm cơ sở cho sự phát triển tin học. Để giải quyết các vấn đề của tin học và ứng dụng tin học, tìm và dùng các lý thuyết và công cụ toán học. Toán học và Tin học5 Toán học rời rạc đối với tin học „ Logic (lập luận tự động, AI, hệ thông minh) „ Set theory (tập mờ, tập thô, tính toán với thông tin không đủ, không chính xác, ) „ Number theory(bảo mật thông tin) „ Combinatorics(hình học tổ hợp, ) „ Graph theory(mạng, sinh học, vật lý, ) „ Digital geometry and digital topology(phân tích ảnh, etc.) „ Algorithmics (phương pháp tính toán) „ Computability(giới hạn lý thuyết và thực tế của thuật toán) „ Probability and Markov chains (xử lý tiếng nói, sinh học, ) „ Linear algebra(phân tích dữ liệu, ...) „ Probability (ngẫu nhiên) „ Proofs (kỹ nghệ phần mềm, AI) „ etc. Toán học và Tin học6 Một số lĩnh vực toán học khác „ Thống kê và phân tích dữ liệu (statistics, data analysis) „ Lý thuyết tối ưu (Optimization) Toán học và Tin học7 Logic trong tin học „ Logic mệnh đề, logic tân từ, logic không chuẩn (modal, temporal, non-monotonic, fuzzy, high order, ... logic) „ Thí dụ: Máy tự động dùng tam đoạn luận (syllosism) Elephants are bigger than dogs Dogs are bigger than mice Therefore Elephants are bigger than mice = + Knowledge (đại số, thống kê, toán học rời rạc, ...) Inference (logic toán học, ) Toán học và Tin học8 Lý thuyết tập hợp (tập mờ, tập thô) „ Tập mờ (Zadeh 1965), tập thô (Pawlak, 1982) „ Rough fuzzy hybridization? Rough sets + Fuzzy sets? } ,{ shapecolor=R {/ . =colorclassEq {/ . =shapeclassEq { . =classEq ,, ,,} {{ }} , ,} {,} { ,{ }} ,} {, ,} {,} {{ }} }, , {=X }, {* =X } , , {* =X Xấp xỉ dưới X* :Hợp của các lớp tương đương nằm trọn trong X Xấp xỉ trên X* : Hợp của các lớp tương đương có giao khác rỗng với X },, ,{=U , , X Toán học và Tin học9 23 bài toán của thế kỷ 20 „ Tại Đại hội Toán học Thế giới lần thứ hai (Paris, tháng Năm 1900), Hilbert nêu ra 23 bài toán, thách thức các nhà toán học toàn thế giới giải trong thế kỷ 20. „ 12 bài toán đã được giải toàn bộ, 8 bài toán được giải từng phần, 3 bài vẫn chưa có lời giải. Toán học và Tin học10 „ 4 giờ chiều Thứ tư ngày 24 tháng 5 năm 2000, Viện Toán học Clay công bố và thách thức 7 bài toán của thế kỷ 21 (1 triệu $ cho mỗi lời giải). „ Bài toán số 1: P versus NP „ Sáu bài toán khác: 1. The Hodge Conjecture 2. The Poincaré Conjecture (solved 2006) 3. The Riemann Hypothesis 4. Yang-Mills Existence and Mass Gap 5. Navier-Stokes Existence and Smoothness 6. The Birch and Swinnerton-Dyer Conjecture. 7 bài toán của thế kỷ 21 Toán học và Tin học11 Bài toán “P versus NP” „ Nếu ai đó hỏi rằng liệu 13.717.421 có là tích của hai số nhỏ hơn không, bạn sẽ cảm thấy rất khó trả lời là đúng hay sai. „ Nếu người đó bảo bạn rằng số này có thể là tích của 3607 và 3803, bạn có thể kiểm tra điều này thật dễ dàng. „ Xác định xem với một bài toán cho trước, liệu có tồn tại một lời giải có thể kiểm chứng nhanh (bằng máy tính chẳng hạn), nhưng lại cần rất nhiều thời gian để giải từ đầu (nếu không biết lời giải)? „ Có rất nhiều bài toán như vậy. Chưa ai có thể chứng minh được rằng, với bất kỳ bài toán nào như vậy, thực sự cần rất nhiều thời gian để giải. Có thể chỉ đơn giản là chúng ta vẫn chưa tìm ra được cách giải chúng nhanh chóng. Stephen Cook phát biểu bài toán P versus NP vào năm 1971. Toán học và Tin học12 „ Bài toán SAT: cho trước một mạch điện tử Boolean, liệu có các cách chọn inputs sao cho output là True hay không? „ Inputs của các mạch điện tử Boolean (với cổng AND, OR và NOT) hoặc là T (true) hoặc là F (false). Mỗi cổng nhận một số các inputs, và outputs giá trị logic tổng hợp được. Tôi không tìm nổi cho chef một thuật toán hiệu quả. Đầu óc tôi dạo này có vẻ âm u quá. Hãy tìm ngay cho tôi một thuật toán hiệu quả để giải SAT. Bài toán “P versus NP” Toán học và Tin học13 Tôi không thể tìm được một thuật toán hiệu quả bởi vì không thể có một thuật toán nào như vậy. Tôi không thể tìm được một thuật toán hiệu quả bởi vì tất cả những người nổi tiếng này cũng không tìm được nó. nếu bạn chứng minh được SAT là intractable nếu bạn biết SAT là NP-complete (chứng minh intractability có thể khó như việc tìm lời giải hiệu quả) Bài toán “P versus NP” Toán học và Tin học14 „ Độ phức tạp tính toán: P (thời gian đa thức) và non-P (thời gian hàm mũ). Bài toán kiểu P có thể giải dễ dàng (sắp xếp dãy số theo thứ tự), bài toán kiểu non-P rất khó giải (tìm các thừa số nguyên tố của một số nguyên cho trước). „ Người ta tin rằng có rất nhiều bài toán thuộc kiểu non-P, nhưng chưa bao giờ chứng minh được chính chúng là như vậy (hết sức khó). „ NP (Nondeterministic Polynomial) là một họ đặc biệt các bài toán kiểu non-P: nếu bất kỳ trong chúng có nghiệm thời gian đa thức thì tất cả sẽ có nghiệm thời gian đa thức. „ P = NP? Các bài toán kiểu P và NP là như nhau? Độ phức tạp tính toán—Sự tồn tại các bài toán giải được nhưng vô cùng khó giải Toán học và Tin học15 Thời gian đa thức và hàm mũ 1.3x1013centuries 2x10 8 centuries3855 centuries6.5 years58 minutes0.059second3n 336 centuries 35.7 years12.7 days17.9 second1.0 second0.01second2n 13.0 minutes 5.2 minutes1.7 minutes24.3 second3.2 second1secondn5 0.06 second0.05 second0.04 second0.03 second0.02 second0.01secondn3 0.006 second0.005 second0.004 second0.003 second0.002 second0.001secondn2 0.0006 second0.0005 second0.0004 second0.0003 second0.0002 second0.0001secondn n = 60n = 50n = 40n = 30n = 20n = 10 Time complexity function Toán học và Tin học16 „Điều gì xảy ra khi dữ liệu lớn, N>106? „Cần thuật toán heuristic nhanh, gần đúng ÎFast CMB analysis by Szapudi et al (2001) O(NlogN) cần 1 ngày O(N3) cần 10 triệu năm „Chú trọng đến giá của tính toán ÎCần luôn điều khiển được độ chính xác ÎĐạt kết quả tốt nhất trong thời gian và tài nguyên cho phép „Dùng máy tính song song Polynomial time algorithms do not always work! Scalable algorithms Toán học và Tin học17 Mật mã và an toàn thông tin „ Là nghiên cứu về bí mật của truyền tin (truyền tin trong điều kiện có kẻ địch). „ An toàn mạng và máy tính: quản lý sự truy nhập máy tính và tin cậy của thông tin, và các ứng dụng như: ATM cards, computer passwords, e-commerce, ... Germany Lorenz cipher machine Toán học và Tin học18 Mật mã và an toàn thông tin „ Tạo mã (encryption: plaintextÆ ciphertext) và giải mã (decryption) „ Khái niệm: mật mã (cipher: letter, bit), mã (code: word or phrase meaning), khóa (key). Rất nhiều kỹ thuật: Î Symmetric-key cryptography (cùng một key cho nhận/gửi) Î Public-key cryptography 1976 (public/private key) dựa trên number theory (integer factorization) Î Cryptanalysis (tìm điểm yếu, không an toàn trong một hệ dùng mật mã) Î Cryptographic primitives Î Cryptographic protocols (Khóa là một đoạn tin (piece of information) kiểm soát hoạt động của một thuật toán tạo mật mã, chữ ký điện tử, định quyền hạn (encryption, digital signature, authentication)). Toán học và Tin học19 Public-key cryptography „ integer factorization là quá trình phân tích một chữ số đa hợp thành tích của các ước số nhỏ hơn sao cho khi nhân các ước số này ta được số ban đầu. „ BSI team: Nov. 2005, RSA-640 (193 decimal digits, 640 bits) on 80 AMD Opteron CPUs computer. „ Khó nhất trong các bài toán này là trường hợp ước số là các số nguyên tố được chọn ngẫu nhiên với cùng độ lớn. Vẫn chưa có thuật toán thời gian đa thức để phân tích một số lớn b-bit thành tích của hai số nguyên tố có cùng kích thước. „ Một trong các bài toán lớn chưa giải được trong KHMT và lý thuyết số là việc tìm một thuật toán để nhân tử hóa các số trong thời gian đa thức. Toán học và Tin học20 Finite state machinesMáy hữu hạn trạng thái „ Là mô hình của các hành vi tạo nên bởi một số hữu hạn các trạng thái (states), các chuyển đổi trạng thái (transitions), và các hành động. „ Mô hình toán học: (Σ,S,s0,δ,F), „ Việc thực hiện một phần cứng máy tính đòi hỏi một công-tơ (register) để chứa các biến trạng thái, một khối (block) mạch logic xác định sự chuyển trạng thái, và một khối thứ hai các mạch logic xác định output của một FSM. Toán học và Tin học21 Machine learning and data miningHọc máy và Khai phá dữ liệu ƒMachine learning Xây các hệ máy tính có thể học như con người (một số khả năng). ƒ ICML since 1982 ECML since 1989 ƒECML/PKDD since 2001 ƒData mining Tìm tri thức mới và hữu ích từ những cơ sở dữ liệu lớn. ƒACM KDD since 1995, PKDD and PAKDD since 1997, IEEE ICDM and SIAM DM since 2000, etc. Toán học và Tin học22 Machine learning and data miningHọc máy và Khai phá dữ liệu ƒMachine learning Xây các hệ máy tính có thể học như con người (một số khả năng). ƒ ICML since 1982 ECML since 1989 ƒECML/PKDD since 2001 ƒData mining Tìm tri thức mới và hữu ích từ những cơ sở dữ liệu lớn. ƒACM KDD since 1995, PKDD and PAKDD since 1997, IEEE ICDM and SIAM DM since 2000, etc. „ 1997: Deep Blue beats Kasparov (12.2006: Deep Fritz beets Kramnik) „ 1997: Robot cup „ 2005: DARPA Grand Challenge Toán học và Tin học23 „ Rất nhiều dữ liệu được thu thập và tích lũy trong các cơ sở dữ liệu lớn (hàng triệu bản ghi, hàng nghìn thuộc tính). „ Rất nhiều dữ liệu là loại được cấu trúc phức tạp (không ở dạng vectơ). Complexly structured data Thách thức: Tìm thuật toán khả cỡ để xử lý dữ liệu lớn và cấu trúc phức tạp? Toán học và Tin học24 Hai con đường của toán trong tin học Các lý thuyết, mô hình toán học làm cơ sở cho sự phát triển tin học. Để giải quyết các vấn đề của tin học và ứng dụng tin học, tìm và dùng các lý thuyết và công cụ toán học. Toán học và Tin học25 Toán học và tin học „ Vài lĩnh vực tiêu biểu của toán học trong tin học „ Toán học trong xử lý ngôn ngữ tự nhiên „ Toán học và Web „ Toán học trong sinh học „ Toán học trong học máy (machine learning) Toán học và Tin học26 Lexical / Morphological Analysis Syntactic Analysis Semantic Analysis Discourse Analysis Tagging (gán nhãn từ loại) Chunking (phân cụm từ) Word Sense Disambiguation Grammatical Relation Finding Named Entity Recognition Reference Resolution Shallow parsing The woman will give Mary a book The/Det woman/NN will/MD give/VB Mary/NNP a/Det book/NN POS tagging [The/Det woman/NN]NP [will/MD give/VB]VP [Mary/NNP]NP [a/Det book/NN]NP chunking [The woman] [will give] [Mary] [a book] relation finding subject i-object object text meaning Natural language processing (NLP) Ông già đi nhanh quá Toán học và Tin học27 „1990s–2000s: Statistical learning Îalgorithms, evaluation, corpora „1980s: Standard resources and tasks ÎPenn Treebank, WordNet, MUC „1970s: Kernel (vector) spaces Îclustering, information retrieval (IR) „1960s: Representation Transformation ÎFinite state machines (FSM) and Augmented transition networks (ATNs) „1960s: Representation—beyond the word level Î lexical features, tree structures, networks Trainable FSMs Trainable parsers Xu thế trong NLP Toán học và Tin học28 Machine learning and statistics in NLP some ML/Stat no ML/Stat (Marie Claire, ECML/PKDD 2005) Toán học và Tin học29 Trainable finite state machines ... ... Hidden Markov Models (HMMs) [Baum et al., 1970] - Generative - Need independence assumption - Local optimum - Local normalization ... ... ... ... ... ... ... ... ... ... St-1 St St+1 St-1 St St+1 St-1 St St+1 Ot-1 Ot Ot+1 Ot-1 Ot Ot+1 Ot-1 Ot Ot+1 Maximum Entropy Markov Models (MEMMs) [McCallum et al., 2000] - Discriminative - No independence assumption - Global optimum - Local normalization More accurate than HMMs Conditional Random Fields (CRFs) [Lafferty et al., 2001] - Discriminative - No independence assumption - Global optimum - Global normalization More accurate than MEMMs Toán học và Tin học30 Increasing computing power 30MB 1 . 6 m e t e r s 1966 30 Mb JAIST’s CRAY XT3 Linux OS, 180 AMD Opteron 2.4GHz CPUs, 8Gb RAM/CPU, total: 1.44Tb RAM -100 100 300 500 700 900 1100 1300 1500 1700 1900 2100 2300 2500 2700 2900 3100 3300 3500 1 2 5 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 1 0 0 1 1 0 1 2 0 1 3 0 1 4 0 1 5 0 # of parallel processes T r a i n i n g t i m e ( m i n u t e ) Second order of Conditional Random Fields (Text chunking): All phrase chunking, 17h46’ on 90 processes vs.1348h Toán học và Tin học31 Toán học và tin học „ Vài lĩnh vực tiêu biểu của toán học trong tin học „ Toán học trong xử lý ngôn ngữ tự nhiên „ Toán học và Web „ Toán học trong sinh học „ Toán học trong học máy (machine learning) Toán học và Tin học32 Web link data Food Web [Martinez ’91] Friendship Network [Moody ’01] Over 3 billion documents Toán học và Tin học33 Hai cách tiêu biểu (1998): 1. Page rank: tìm các trang Web quan trọng và liên quan nhất trên Web (như trong Google) 2. Hubs and authorities: đánh giá chi tiết hơn tầm quan trọng của các trang Web. Larry Page, Sergey Brin Tìm kiếm trên Web Toán học và Tin học34 PageRank: key idea „Google thường đưa ra một số rất lớn các trang Web (‘weather forecast’Æ 5.5 million pages). Các trang liên quan nhất thường nằm trong một, hai chục trang đầu. „ Làm sao search engine biết được các trang Web nào là quan trọng nhất? „Google gắn cho mỗi trang Web một con số đặc trưng tầm quan trọng. Con số này được gọi là số PageRank và được tính như giá trị riêng (eigenvalue) của bài toán Pw = λw ở đây P được tính dựa trên link structure của Internet. Vấn đề cơ bản là làm sao thiết lập xác đáng được link structure của toàn bộ Web, i.e., ma trận P. Toán học và Tin học35 PageRank: key idea „ Mô hình cơ sở của thuật toán PageRank là random walk thực hiện trên toàn bộ các trang Web trên Internet. „ Ký hiệu pt(x) khả năng ta ở tại trang Web x ở thời điểm t. Số PageRank của x được các định như lim(pt(x)) khi tÆ ∞. „ Ma trận P có tính chất không rút gọn được (irreducible) và ngẫu nhiên (stochastic), nên random walk có thể biểu diễn qua chuỗi Markov, và PageRank của mọi trang có thể tính được qua các vectors riêng của P. Toán học và Tin học36 PageRank: Stochastic matrix „ Mỗi trang i tương ứng với dòng i và cột i của P „ Nếu trang j có n successors (links) và trang i là một trong số n succesors của j thì ô ijth của ma trận được là to 1/n, nếu không là 0. A B C Assume the Web consists of only three pages A, B, and C. The links among these pages are shown as in the graph. A B C A 1/2 1/2 0 B 1/2 0 1 C 0 1/2 0 Toán học và Tin học37 The PageRank algorithm „Ma trận Google P hiện có kích thước 4.2×109 và do đó việc tìm giá trị riêng là không tầm thường. „Tìm xấp xỉ các véc tơ riêng của P (power method) „Việc tính toán (matrix-vector multiplications) phải thực hiện trên các hệ máy tính song song lớn. w0 = initial guess For k = 1 to 50 wk = P*wk-1 End Return w50 Toán học và Tin học38 PageRank: Example Bắt đầu cho w1 = w2 = w3 = 1, và tính đệ quy phép nhân ma trận với các giá trị này a = 1 1 5/4 9/8 5/4 6/5 b = 1 3/2 1 11/8 17/16 6/5 c = 1 1/2 3/4 1/2 11/16 ... 3/5 w0 = initial guess For k = 1 to 50 wk = P*wk-1 End Return w50⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ × ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 3 2 1 2 1 2 1 2 1 2 1 3 2 1 00 10 0 w w w w w w Toán học và Tin học39 foodscience.com-Job2 JobTitle: Ice Cream Guru Employer: foodscience.com JobCategory: Travel/Hospitality JobFunction: Food Services JobLocation: Upper Midwest Contact Phone: 800-488-2611 DateExtracted: January 8, 2004 Source: www.foodscience.com/jobs_midwest.html OtherCompanyJobs: foodscience.com-Job1 Information extraction: the process of extracting text segments of semi-structured or free text to fill data slots in a predefined template Finding “things” but not “pages”Information Extraction vs. Information Retrieval Toán học và Tin học40 Toán học và tin học „ Vài lĩnh vực tiêu biểu của toán học trong tin học „ Toán học trong xử lý ngôn ngữ tự nhiên „ Toán học và Web „ Toán học trong sinh học „ Toán học trong học máy (machine learning) Toán học và Tin học41 Problems in bioinformatics 30,000 Genes 10,000 Proteins 1400 Chemicals Metabolomics Proteomics Genomics Toán học và Tin học42 Một mẩu 350 chữ cái của dãy DNA 1.6 triệu chữ (nhỏ hơn 4570 lần): How biological data look like? TACATTAGTTATTACATTGAGAAACTTTATAATTAAAAAAGATTCATG TAAATTTCTTATTTGTTTATTTAGAGGTTTTAAATTTAATTTCTAAGGGT TTGCTGGTTTCATTGTTAGAATATTTAACTTAATCAAATTATTTGAATTT TTGAAAATTAGGATTAATTAGGTAAGTAAATAAAATTTCTCTAACAAATA AGTTAAATTTTTAAATTTAAGGAGATAAAAATACTACTCTGTTTTATTAT GGAAAGAAAGATTTAAATACTAAAGGGTTTATATATATGAAGTAGTTAC CCTTAGAAAAATATGGTATAGAAAGCTTAAATATTAAGAGTGATGAAGT ATATTATGT Nhiều loại dữ liệu khác Toán học và Tin học43 (Approximate) String Matching Input: Text T , Pattern P Question(s): P xuất hiện trong T? Tìm một xuất hiện của P trong T. Tìm mọi xuất hiện của P trong T. Tính số xuất hiện của P trong T. Tìm dãy con dài nhất của P trong T. Tìm dãy con gần nhất của P trong T. Xác định các lặp trực tiếp của P trong T. và nhiều biến dạng khác I t: t , tt ti : t i tr ì t t i tr . ì i t i tr . í t i tr . ì i t tr . ì t tr . ị l tr ti tr . i i Applications: Liệu P đã có trong cơ sở dữ liệu T? Xác định vị trí của P trong T. Liệu có thể dùng P như một nguyên tố của T? P có tương đồng với gì đó trong T? P có bị hỏng bởi T? Liệu prefix(P) = suffix(T)? Xác định các lặp sau trước (tandem) của P trong T. li ti : i tr li ị ị trí tr . i t t t t i ì tr ị i i r fi ( ) ffi ( ) ị l tr (t ) tr . Đối sánh dãy (string matching) Toán học và Tin học44 Pairwise Sequence AlignmentSắp dãy từng cặp „ Input Î Hai dãy chữ cái Î Một cách cho điểm „ Output Î Cách sắp thẳng dãy tối ưu ATTGCGC ATTGCGC Æ ATTGCGC Æ ATCCGCC ATTGCGC AT-CCGCÆ ATTGCGC ATC-CGCÆ ™ Bài toán cơ bản nhất của tin sinh học ™ Các dãy được sắp thẳng ⇒ có dùng cấu trúc hoặc chức năng ™ Cho nhiều gợi ý nếu cấu trúc và chức năng của một trong các dãy được sắp thẳng đã biết ATTGCGC ATCCG-CÆ Toán học và Tin học45 „ Phổ biến dùng HMM: Các cặp dãy được sắp do dùng các thuật toán vét cạn bởi quy hoạch động. ÎĐộ phức tạp của các phương pháp vét cạn là O(2n mn) În = số các dãy „ Sắp dãy bội xử dụng các phương pháp heuristic Pairwise Sequence AlignmentSắp dãy từng cặp #Rat ATGGTGCACCTGACTGATGCTGAGAAGGCTGCTGT #Mouse ATGGTGCACCTGACTGATGCTGAGAAGGCTGCTGT #Rabbit ATGGTGCATCTGTCCAGT---GAGGAGAAGTCTGC #Human ATGGTGCACCTGACTCCT---GAGGAGAAGTCTGC #Oppossum ATGGTGCACTTGACTTTT---GAGGAGAAGAACTG #Chicken ATGGTGCACTGGACTGCT---GAGGAGAAGCAGCT #Frog ---ATGGGTTTGACAGCACATGATCGT---CAGCT Toán học và Tin học46 Đoán nhận gene Gene prediction Là bài toán quan trọng của