HK6

1/SHTT:
http://dangtuanhiep.wordpress.com/2008/09/23/so-hoc/

2/

PTTT+SHTT:
Xem diễn đàn tin để học thuật toán
http://vnoi.info/index.php?option=com_fireboard&Itemid=26&func=showcat&catid=4

3/  Cac bai bao : http://www.crypto-world.com/FactorPapers.html

4/ So hoc : http://primes.utm.edu/index.html

5/ Sach ve Ly thuyet so http://www.dpmms.cam.ac.uk/Number-Theory-Web/N10.html

6/ http://www.dpmms.cam.ac.uk/Number-Theory-Web/N1.html

PTTT:
Randomize Algorithmetic
( Thuật toán XS)
http://www.diendantoanhoc.net/forum/index.php?showtopic=2892&st=20&#entry15385

http://diendantoanhoc.net/forum/lofiversion/index.php?t2956.html

http://www.cse.buffalo.edu/~hungngo/Vietnamese/cantor.pdf

21 Responses to “HK6”

  1. vanchanh123 Says:

    Các vấn đề quan tâm
    – Thuật toán XS
    – Giải thuật di truyền
    _ Bien-Doi-Wavelet

  2. vanchanh123 Says:

    Lịch cao học
    TKB

  3. vanchanh123 Says:

    Working:
    -Read newspaper example http://www.americares.org/newsroom/news/deadly-earthquake-strikes-haiti-2010.html

    http://englishstudyforvms.wordpress.com/

    http://vncd.wordpress.com/

    http://dethi.net/ http://dethi.com/

    http://tailieuduhoc.org

    http://www.uiowa.edu/~acadtech/phonetics/
    – practising,reading book on all subject
    -one day read once http://www.maths.vn/forums/showthread.php?t=27729

    Note:THÔNG BÁO HỌP BAN ĐIỀU HÀNH
    Thời gian dự kiến : 17h thứ bẩy ngày 13/3/2010
    Địa điểm : quán cafe VÀNG ANH trên dg 3 THÁNG 2 . Mọi người tập trung ở trường lúc 17h , rồi chúng ta sẽ cùng qua quán .

  4. vanchanh123 Says:

    Information Theory
    Encode:
    1/Các cách mã hóa tiếng Việt
    http://www.3c.com.vn/Story/vn/tintucvasukien/traodoikinhnghiem/legtiengviet/2010/3/61101.html

    2/Sự kiện mã hóa lớn nhất tại Việt Nam
    http://www6.vnmedia.vn/newsdetail.asp?NewsId=171582&Catid=35

    3/http://vi.wikipedia.org/wiki/M%C3%A3_h%C3%B3a_kh%E1%BB%91i

    ———————————-
    compress data

    II. Một số phương pháp nén dữ liệu

    1. Phương pháp mã hoá độ dài loạt (Run-Length Encoding)

    Loại dư thừa đơn giản nhất trong một tập tin là các đường chạy dài gồm các kí tự lặp lại, điều này thường thấy trong các tập tin đồ hoạ bitmap, các vùng dữ liệu hằng của các tập tin chương trình, một số tập tin văn bản…

    Ví dụ, xét chuỗi sau:

    AAAABBBAABBBBBCCCCCCCCDABCBAAABBBBCCCD

    Chuỗi này có thể được mã hoá một cách cô đọng hơn bằng cách thay thế chuỗi kí tự lặp lại bằng một thể hiện duy nhất của kí tự lặp lại cùng với một biến đếm số lần kí tự đó được lặp lại. Ta muốn nói rằng chuỗi này gồm bốn chữ A theo sau bởi ba chữ B rồi lại theo sau bởi hai chữ A, rồi lại theo sau bởi năm chữ B… Việc nén một chuỗi theo phương pháp này được gọi là mã hoá độ dài loạt. Khi có những loạt dài, việc tiết kiệm có thể là đáng kể. Có nhiều cách để thực hiện ý tưởng này, tuỳ thuộc vào các đặc trưng của ứng dụng (các loạt chạy có khuynh hướng tương đối dài hay không ? Có bao nhiêu bit được dùng để mã hoá các kí tự đang được mã ?).

    Nếu ta biết rằng chuỗi của chúng ta chỉ chứa các chữ cái, thì ta có thể mã hoá biến đếm một cách đơn giản bằng cách xen kẻ các con số với các chữ cái. Vì vậy chuỗi kí tự trên được mã hoá lại như sau:

    4A3BAA5B8CDABCB3A4B3CD

    Ở ÐÂY “4A” có nghĩa là “bốn chữ A”… Chú ý là không đáng để mã hoá các loạt chạy có độ dài 1 hoặc 2 vì cần đến hai kí tự để mã hoá.

    Ðối với các tập tin nhị phân một phiên bản được tinh chế của phương pháp này được dùng để thu được sự tiết kiệm ÐÁNG KỂ. Ý tưởng ở đây là lưu lại các độ dài loạt, tận dụng sự kiện các loạt chạy thay đổi giữa 0 và 1 để tránh phải lưu chính các số 0 và 1 đó. Ðiều này giả định rằng có một vài loạt chạy ngắn (Ta tiết kiệm các bit trên một loạt chạy chỉ khi độ dài của đường chạy là lớn hơn số bit cần để biễu diễn chính nó trong dạng nhị phân), nhưng khó có phương pháp mã hoá độ dài loạt nào hoạt động thật tốt trừ phi hầu hết các loạt chạy đều dài.

    Việc mã hoá độ dài loạt cần đến các biễu diễn riêng biệt cho tập tin và cho bản đã được mã hoá của nó, vì vậy nó không thể dùng cho mọi tập tin, điều này có thể hoàn toàn bất lợi, ví dụ, phương pháp nén tập tin kí tự đã được đề nghị ở trên sẽ không dùng được đối với các chuỗi kí tự có chứa số. Nếu những kí tự khác được sử dụng để mã hoá các số đếm, thì nó sẽ không làm việc với các chuỗi chứa các kí tự đó. Giả sử ta phải mã hoá bất kì kí tự nào từ một bảng chữ cái cố định bằng cách chỉ dùng các kí tự từ bảng chữ cái đó. Ðể minh hoạ, giả sử ta phải mã hoá bất kì một chuỗi nào từ một chữ cái đó, ta sẽ giả định rằng ta chỉ có 26 chữ cái trong bảng chữ cái (và cả khoảng trống) để làm việc.

    Ðể có thể dùng vài chữ cái để biểu diễn các số và các kí tự khác biểu diễn các phần tử của chuỗi sẽ được mã hoá, ta phải chọn một kí tự được gọi là kí tự “Escape”. Mỗi một sự xuất hiện của kí tự đó báo hiệu rằng hai chữ cái tiếp theo sẽ tạo thành một cặp (số đếm, kí tự) với các số đếm được biểu diễn bằng cách dùng kí tự thứ i của bảng chữ cái để biểu diễn số i. Vì vậy, chuỗi ví dụ của chúng ta sẽ được biểu diễn như sau với Q được xem là các kí tự “Escape”

    QDABBBAABQHCDABCBAAAQDBCCCD

    Tổ hợp của kí tự “Escape”, số đếm và một kí tự lặp lại được gọi là một dãy Escape. Chú ý rằng không đáng để mã hoá các đường chạy có chiều dài ít hơn bốn kí tự, vì ít nhất là cần đến ba kí tự để mã hoá bất kì một loạt chạy nào.

    Trong trường hợp bản thân kí tự “Escape” xuất hiện trong dãy kí tự cần mã hoá ta sử dụng một dãy “Escape” với số đếm là 0 (kí tự space) để biểu diễn kí tự “Escape”. Như vậy trong trường hợp kí tự “Escape” xuất hiện nhiều thì có thể làm cho tập tin nén phình to hơn trước.

    Các loạt chạy dài có thể được cắt ra để mã hoá bằng nhiều dãy Escape, ví dụ, một loạt chạy gồm 51 chữ A sẽ được mã hoá như QZAQYA bằng cách dùng trên.

    Phương pháp mã hoá độ dài loạt thường được áp dụng cho các tập tin đồ hoạ bitmap vì ở đó thường có các mảng lớn cùng màu được biểu diễn dưới dạng bitmap là các chuỗi bit có đường chạy dài. Trên thực tế, nó được dùng trong các tập tin .PCX, .RLE.

    2. Phương pháp mã hoá Huffman

    Các tập tin của máy tính được lưu dưới dạng các kí tự có chiều dài không đổi là 8 bits. Trong nhiều tập tin, xác suất xuất hiện các kí tự này là nhiều hơn các kí tự khác, từ đó ta thấy ngay rằng nếu chỉ dùng một vài bit để biểu diễn cho các kí tự có xác suất xuất hiện lớn và dùng nhiều bit hơn để biểu diễn cho các kí tự có xác suất xuất hiện nhỏ thì có thể tiết kiệm được độ dài tập tin một cách đáng kể. Ví dụ, để mã hoá một chuỗi như sau:

    “ABRACADABRA”

    Nếu mã hoá chuỗi trên trong dạng mã nhị phân 5 bit ta sẽ có dãy bit sau:

    00001000101001000001000110000100100000010001010010 00001

    Ðể giải mã thông điệp này, chỉ đơn giản là đọc ra 5 bits ở từng thời điểm và chuyển đổi nó tương ứng với việc mã hoá nhị phân đã được định nghĩa ở trên. Trong mã chuẩn này, chữ D xuất hiện chỉ một lần sẽ cần số lượng bit giống chữ A xuất hiện nhiều lần.

    Ta có thể gán các chuỗi bit ngắn nhất cho các kí tự được dùng phổ biến nhất, giả sử ta gán: A là 0, B là 1, R là 01, C là 10 và D là 11 thì chuỗi trên được biễu diễn như sau:

    0 1 01 0 10 0 11 0 1 01 0

    Ví dụ này chỉ dùng 15 bits so với 55 bits như ở trên, nhưng nó không thực sự là một mã vì phải lệ thuộc vào khoảng trống để phân cách các kí tự. Nếu không có dấu phân cách thì ta không thể giải mã được thông điệp này. Ta cũng có thể chọn các từ mã sao cho thông điệp có thể được giải mã mà không cần dấu phân cách, ví dụ như: A là 11, B là 00, C là 010, D là 10 và R là 011, các từ mã này gọi là các từ mã có tính prefix (Không có từ mã nào là tiền tố của từ mã khác). Với các từ mã này ta có thể mã hoá thông điệp trên như sau:

    1100011110101110110001111

    Với chuỗi đã mã hoá này ta hoàn toàn có thể giải mã được mà không cần dấu phân cách. Nhưng bằng cách nào để tìm ra bảng mã một cách tốt nhất ? Vào năm 1952, D.Huffman đã phát minh ra một cách tổng quát để tìm ra bảng mã này một cách tốt nhất.

    – Bước đầu tiên trong việc xây dựng mã Huffman là đếm số lần xuất hiện của mỗi kí tự trong tập tin sẽ được mã hoá.

    – Bước tiếp theo là xây dựng một cây nhị phân với các tần số được chứa trong các nút. Hai nút có tấn số bé nhất được tìm thấy và một nút mới được tạo ra với hai nút con là các nút đó với giá trị tần số của nút mới bằng tổng tần suất của hai nút con. Tiếp theo hai nút mới với tần số nhỏ nhất lại được tìm thấy và một nút mới nữa lại được tao ra theo cách trên. Lặp lại như vậy cho đến khi tất cả các nút được tổ hợp thành một cây duy nhất.

    – Sau khi có cây nhị phân, bảng mã Huffman được phát sinh bằng cách thay thế các tần số ở nút đáy bằng các kí tự tương ứng.

    Ưu điểm của phương pháp mã hoá Huffman là đạt được hệ số nén cao (Hệ số nén tuỳ thuộc vào cấu trúc của các tập tin). Nhược điểm của phương pháp này là bên nhận muốn giải mã được thông điệp thì phải có một bảng mã giống như bảng mã ở bên gửi, do đó khi nén các tập tin bé hệ số nén không được cao.

    3. Phương pháp nén LZW

    Phương pháp nén LZW được phát minh bởi Lempel – Zip và Welch. Nó hoạt động đựa trên một ý tưởng rất đơn giản là người mã hoá và người giải mã cùng xây dựng bản mã.

    Nguyên tắc hoạt động của nó như sau:

    – Một xâu kí tự là một tập hợp từ hai kí tự trở lên.

    – Nhớ tất cả các xâu kí tự đã gặp và gán cho nó một dấu hiệu (token) riêng.

    – Nếu lần sau gặp lại xâu kí tự đó, xâu kí tự sẽ được thay thế bằng dấu hiệu của nó.

    Phần quan trọng nhất của phương pháp nén này là phải tạo một mảng rất lớn dùng để lưu giữ các xâu kí tự đã gặp (Mảng này được gọi là “Từ điển”). Khi các byte dữ liệu cần nén được đem đến, chúng liền được giữ lại trong một bộ đệm chứa (Accumulator) và đem so sánh với các chuỗi đã có trong “từ điển”. Nếu chuỗi dữ liệu trong bộ đệm chứa không có trong “từ điển” thì nó được bổ sung thêm vào “từ điển” và chỉ số của chuỗi ở trong “từ điển” chính là dấu hiệu của chuỗi. Nếu chuỗi trong bộ đệm chứa đã có trong “từ điển” thì dấu hiệu của chuỗi được đem ra thay cho chuỗi ở dòng dữ liệu ra. Có bốn qui tắc để thực hiên việc nén dữ liệu theo thuật toán LZW là:

    qui tắc 1: 256 dấu hiệu đầu tiên được dành cho các kí tự đơn (0 – 0ffh).

    qui tắc 2: Cố gắng so sánh với “từ điển” khi trong bộ đệm chứa đã có nhiều hơn hai kí tự.

    qui tắc 3: Các kí tự ở đầu vào (Nhận từ tập tin sẽ được nén) được bổ sung vào bộ đệm chứa đến khi chuỗi kí tự trong bộ đệm chứa không có trong “từ điển”.

    qui tắc 4: Khi bộ đệm chứa có một chuỗi mà trong “từ điển” không có thì chuỗi trong bộ đệm chứa được đem vào “từ điển”. Kí tự cuối cùng của chuỗi kí tự trong bộ đệm chứa phải ở lại trong bộ đệm chứa để tiếp tục tạo thành chuỗi mới.

    Ví dụ: Các bước để mã hoá chuỗi “!BAN!BA!BAA!BAR!” như sau (Bảng 4. 1):

    – bước 1: Kí tự thứ nhất ‘!’ được cất vào bộ đệm chứa để chuẩn bị tạo nên một chuỗi.

    – bước 2: Kí tự thứ hai ‘B’ nối thêm vào sau kí tự !. Vì trong “từ điển” chưa có chuỗi “!B” nên chuỗi này được thêm vào “từ điển” và được gán dấu hiệu là 100h (Vì từ 000h đến 0ffh được dành riêng cho các kí tự đơn: Qui tắc 1). ‘!’ được gửi ra còn ‘B’ phải ở lại trong bộ đệm chứa.

    http://i145.photobucket.com/albums/r238/Katatonia19_9/untitled1.jpg (http://i145.photobucket.com/albums/r238/Katatonia19_9/untitled1.jpg)

    http://i145.photobucket.com/albums/r238/Katatonia19_9/untitled2.jpg (http://i145.photobucket.com/albums/r238/Katatonia19_9/untitled2.jpg)

    – bước 3: Kí tự thứ ba ‘A’ thêm vào sau ‘B’. Chuỗi “BA” cũng chưa có trong “từ điển” nên nó được thêm vào “từ điển” và gán dấu hiệu là 101h. ‘A’ ở lại trong bộ đệm chứa còn ‘B’ được gửi ra.

    – bước 4: Kí tự thứ tư ‘N’ thêm vào sau ‘A’ tạo thành chuỗi “AN” cũng chưa có trong “từ điển” nên được thêm vào “từ điển” và có dâu hiệu là 102h. ‘N’ ở lại trong bộ đệm chứa còn ‘A’ được gửi ra.

    – bước 5: Kí tự thứ năm ‘!’ thêm vào sau ‘N’ để tạo thành chuỗi “N!”, “N!” được thêm vào “từ điển” với dấu hiệu là 103h. ‘!’ ở lại còn ‘N’ được gửi ra.

    – bước 6: Kí tự thứ sáu ‘B’ thêm vào sau ‘!’. Lần này thì chuỗi “B!” đã có trong “từ điển” nên không có kí tự nào được gửi ra. “B!” tiếp tục ở lại trong “từ điển” để tạo ra chuỗi mới.

    – bước 7: Kí tự thứ bảy ‘A’ thêm vào sau ‘B’ để tạo thành chuỗi “B!A”, do “B!A” không có trong “từ điển” nên nó được thêm vào “từ điển” và gán dấu hiệu là 104h đồng thời dấu hiệu 100h được gửi ra thay cho “B!” (Qui tắc 4). A tiếp tục ở lại trong bộ đệm chứa để tạo thành chuỗi mới.

    Các bước trên cứ thế tiếp tục cho đến khi hết tập tin cần nén. Việc giảm kích thước chỉ thực sự bắt đầu tại bước 7 khi mà một dấu hiệu 12 bits là được gửi ra thay cho hai byte “B!”.

    Trong thuật toán nén này, phần lớn thời gian khi bắt đầu nén chủ yếu mất vào việc tạo “từ điển”. Khi “từ điển” đủ lớn, xác suất gặp chuỗi ở bộ đệm chứa trong “từ điển” tăng lên và càng nén được nhiều hơn. Một điều cần chú ý ở đây là mỗi một dấu hiệu, ta phải lưu một chuỗi trong “từ điển” để so sánh. Vì dấu hiệu được biểu diễn bằng một số 12 bits nên “từ điển” sẽ có 4096 lối vào, khi tăng số bit dể biễu diễn dấu hiệu lên thì hiệu quả nén sẽ tốt hơn nhưng lại bị giới hạn bởi bộ nhớ của máy tính. Vì dụ, khi dùng 16 bits để biểu diễn một dấu hiệu thì “từ điển” phải có đến 65536 lối vào, nếu mỗi lối vào có khoảng 20 kí tự thì “từ điển” phải lớn khoảng 1,2 MB. Với một từ điển có dung lượng như vậy rất khó có thể thực hiện trên các máy tính PC hoạt động dưới hệ điều hành DOS vì giới hạn của một đoạn (Segment) là 64KB. Ưu điểm của phương pháp nén LZW là bên nhận có thể tự xây dựng bảng mã mà không cần bên gửi phải gửi kèm theo bản tin nén.

    4. Chọn phương pháp nén

    Qua ba phương pháp nén được dùng phổ biến trên, ta thấy rằng, thuật toán nén độ dài loạt (Runlength) không thể áp dụng cho mhiều loại tập tin được, ví dụ như tập tin chương trình, tập tin cơ sở dữ liệu… vì ở đó các loạt chạy là rất ngắn, do đó nếu áp dụng thuật toán này không những không làm bé tập tin mà còn làm phình to chúng.

    Hai thuật toán còn lại (Huffman và LZW) đều có thể áp dụng được để nén nhiều loại tập tin trên các máy vi tính.

    Thuật toán Huffman có ưu điểm là hệ số nén tương đối cao, phương pháp thực hiện tương đối đơn giản, đòi hỏi ít bộ nhớ, có thể xây dựng dựa trên các mảng bé hơn 64KB. Nhược điểm của nó là phải chứa cả bảng mã vào tập tin nén thì phía nhận mới có thể giải mã được do đó hiệu suất nén chỉ cao khi ta thực hiện nén các tập tin lớn.

    Thuật toán nén LZW có các ưu điểm là hệ số nén tương đối cao, trong tập tin nén không cần phải chứa bảng mã. Nhược điểm của thuật toán này là tốn nhiều bộ nhớ, khó thực hiện dựa trên các mảng đơn giản (bé hơn 64KB).

    Từ các ưu và nhược điểm trên, ta chọn phương pháp nén Huffman vì tính đơn giản của nó hệ số nén lại cao. Nhược điểm của phương pháp nén này có thể khắc phục bằng cách thực hiện nén một lần nhiều tập tin chuẩn bị truyền, làm như vậy coi như chúng ta đang thực hiện nén một tập tin lớn.

    Nguồn:cộng đồng C Việt (http://forums.congdongcviet.com/index.php)

  5. vanchanh123 Says:

    Note : 30/4 SN th Coi

  6. vanchanh123 Says:

    Bài Học Cho Cuộc Sống
    http://my.opera.com/blackmoon/blog/show.dml/123706

    Chu y: xem cac reply phia truoc va sau

    —————————————-
    Câu chuyện của người nông dân này đã giúp chúng ta nhận ra một điều quý giá mà rất nhiều người trong chúng ta không bao giờ nhận thấy: Vật cản đôi khi cũng có thể là một cơ hội tốt

    ———————————-
    http://www.travelatvietnam.com/forum/showthread.php?t=101

    http://itp.vn/forums/index.php?topic=1560.0

    http://vietbao.vn/The-gioi-tre/Bai-hoc-tu-cuoc-song/30147737/275/

  7. vanchanh123 Says:

    Strategy 12/03/2010
    Read book: Information theory (book.pdf)
    XLDC: read file pca.pdf from Diary_Version 2: XLDC Duong

  8. vanchanh123 Says:

    What is ASF?
    Advanced Systems Format (formerly Advanced Streaming Format, Active Streaming Format) is Microsoft’s proprietary digital audio/digital video container format, especially meant for streaming media. ASF is part of the Windows Media framework.

    What is MP3?
    MPEG-1 Audio Layer 3, more commonly referred to as MP3, is a digital audio encoding format using a form of lossy data compression. It is a common audio format for consumer audio storage, as well as a de facto standard encoding for the transfer and playback of music on digital audio players. MP3’s use of a lossy compression algorithm is designed to greatly reduce the amount of data required to represent the audio recording and still sound like a faithful reproduction of the original uncompressed audio for most listeners, but is not considered high fidelity audio by audiophiles. An MP3 file that is created using the mid-range bit rate setting of 128 kbit/s will result in a file that is typically about 1/10th the size of the CD file created from the original audio source. An MP3 file can also be constructed at higher or lower bit rates, with higher or lower resulting quality. The compression works by reducing accuracy of certain parts of sound that are deemed beyond the auditory resolution ability of most people. This method is commonly referred to as perceptual coding. It internally provides a representation of sound within a short term time/frequency analysis window, by using psychoacoustic models to discard or reduce precision of components less audible to human hearing, and recording the remaining information in an efficient manner. This is relatively similar to the principles used by JPEG, an image compression format.

    Convert ASF to MP3 Related Topics: WMA to WAV, WMV to MP3, WMV to WAV, ASF to MP3, ASF to WAV, WAV to WMA, MP3 to WMA, WMV to WMA, ASF to WMA, OGG to WMA, AU to WMA, SND to WMA, AAC to WMA, ADX to WMA, AIFF to WMA, APE to WMA, CDA to WMA, FLAC to WMA, M4A to WMA, M4B to WMA, M4V to WMA, MP4 to WMA, MPC to WMA, SPX to WMA, TTA to WMA, WV to WMA, Resample WMA

    http://www.wma-mp3.net/convert-asf-to-mp3.htm

  9. vanchanh123 Says:

    Solve eqn by computer
    Bessel


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: