Luận văn Thạc sĩ: Dãy ngẫu nhiên, giả ngẫu nhiên và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO<br /> TRƯỜNG ĐẠI HỌC THĂNG LONG<br /> ---------------------------------------<br /> <br /> Lưu Thị Vân Xa<br /> <br /> DÃY NGẪU NHIÊN, GIẢ NGẪU NHIÊN VÀ ỨNG DỤNG<br /> <br /> LUẬN VĂN THẠC SĨ<br /> CHUYÊN NGÀNH: TOÁN ỨNG DỤNG<br /> MÃ SỐ: 60.46.01.12<br /> <br /> NGƯỜI HƯỚNG DẪN KHOA HỌC:<br /> Người hướng dẫn chính: T.S Nguyễn Công Sứ<br /> <br /> Hà Nội – Năm 2015<br /> <br /> LỜI CAM ĐOAN<br /> Tôi xin cam đoan:<br /> - Luận văn này là sản phẩm nghiên cứ của tôi.<br /> - Các số liệu, những kết luận nghiên cứu được trình bày trong luận văn<br /> này trung thực.<br /> - Tôi xin chịu tránh nhiệm về nghiên cứu của mình.<br /> <br /> Thang Long University Libraty<br /> <br /> MỤC LỤC<br /> Trang<br /> Trang phụ bìa ......................................................................................................<br /> Lời cam đoan ......................................................................................................<br /> Mục lục................................................................................................................<br /> <br /> Chương I<br /> CÁC KHÁI NIỆM CƠ BẢN VÀ CÁC TÍNH CHẤT CỦA<br /> CÁC DÃY NGẪU NHIÊN<br /> Khái niệm về dãy ngẫu nhiên .................................................................. 1<br /> Các tính chất của dãy ngẫu nhiên ........................................................... 2<br /> I.2.1. Block – L (xâu) ......................................................................................... 3<br /> I.2.2. Cỡ của xâu ............................................................................................... 3<br /> I.2.3. GAP (Mảng) ............................................................................................. 5<br /> I.2.4. Xâu đủ ...................................................................................................... 6<br /> I.2.5. Xâu đơn điệu (loạt) .................................................................................. 7<br /> <br /> Chương II<br /> MỘT VÀI TIÊU CHUẨN THỐNG KÊ ĐỂ KIỂM ĐỊNH VỀ TÍNH<br /> NGẪU NHIÊN CỦA MỘT DÃY SỐ<br /> Các tiêu chuẩn phù hợp ........................................................................ 11<br /> II.1.1. Tiêu chuẩn χ2 (Khi bình phương) ......................................................... 11<br /> II.1.2. Tiêu chuẩn Kômôgôrôp – Smirnôp (Tiêu chuẩn K – C) ...................... 13<br /> II.1.3. So sánh hai tiêu chuẩn 2 và tiêu chuẩn K – C .................................... 14<br /> Các tiêu chuẩn phi tham số và các tính chất khác ............................. 16<br /> <br /> II.2.1. Kiểm tra tính đều (kiểm tra tần số) ...................................................... 17<br /> II.2.2. Kiểm tra Xêri (Cặp) .............................................................................. 18<br /> II.2.3. Kiểm tra (GAP – Mảng ) ...................................................................... 20<br /> II.2.4. Tiêu chuẩn cỡ (Poken).......................................................................... 22<br /> II.2.5. Tiêu chuẩn đủ ....................................................................................... 23<br /> II.2.6. Kiểm tra hoán vị ................................................................................... 23<br /> II.2.7. Tiêu chuẩn về nhóm (Runtest) .............................................................. 24<br /> II.2.8. Tiêu chuẩn nghịch thế .......................................................................... 26<br /> <br /> Chương III<br /> CÁC DÃY GIẢ NGẪU NHIÊN<br /> Khái niệm về dãy giả ngẫu nhiên ....................................................... 29<br /> Dãy giả ngẫu nhiên thặng dư bậc hai ................................................ 31<br /> III.2.1. Định nghĩa ........................................................................................... 31<br /> III.2.2. Giả thuyết thặng dư bậc hai ................................................................ 32<br /> III.2.3. Tính chất của bộ tạo x2 mod N ............................................................ 33<br /> Phương pháp toàn đẳng tuyến tính ................................................... 34<br /> III.3.1. Công thức ............................................................................................ 34<br /> III.3.2. Tiêu chuẩn tần số ................................................................................ 40<br /> III.3.3. Tiêu chuẩn tương quan ....................................................................... 42<br /> III.3.4. Công suất............................................................................................. 44<br /> III.3.5. Ví dụ .................................................................................................... 45<br /> Dãy ghi dịch – Dãy ghi dịch tuyến tính ............................................. 47<br /> III.4.1. Thanh ghi dịch phản hồi tuyến tính bậc n........................................... 47<br /> III.4.2. Dãy ghi dịch, dãy ghi dịch tuyến tính ................................................. 48<br /> <br /> Thang Long University Libraty<br /> <br /> III.4.3. Tính chất của dãy ghi dịch. ................................................................. 49<br /> III.4.4. Tính chất của các M-dãy ..................................................................... 51<br /> III.4.5. Chu kỳ của dãy ghi dịch tuyến tính và điều kiện M – dãy .................. 53<br /> III.4.5.1. Hàm đặc trưng, đa thức đặc trưng của dãy ghi dịch ........................ 53<br /> III.4.5.2. Chu kỳ của dãy ghi dịch tuyến tính. ................................................ 54<br /> III.4.6. Hàm tự tương quan ............................................................................. 59<br /> III.4.7. Một vài ví dụ về dãy ghi dịch chu kỳ cực đại ...................................... 60<br /> <br />