Primality Testing in Polynomial Time: From Randomized Algorithms to “PRIMES is in P”

Download (click link)

This book is devoted to algorithms for the venerable primality problem: Given a natural number n, decide whether it is prime or composite.

The problem is basic in number theory, efficient algorithms that solve it, i.e., algorithms that run in a number of computational steps which is polynomial in the number of digits needed to write n, are important for theoretical computer science and for applications in algorithmics and cryptology.

This book gives a self-contained account of theoretically and practically important efficient algorithms for the primality problem, covering the randomized algorithms by Solovay-Strassen and Miller-Rabin from the late 1970s as well as the recent deterministic algorithm of Agrawal, Kayal, and Saxena. The textbook is written for students of computer science, in particular for those with a special interest in cryptology, and students of mathematics, and it may be used as a supplement for courses or for self-study.

A Programmer’s Companion to Algorithm Analysis

Download (click link)

Focusing on practical issues, A Programmer’s Companion to Algorithm Analysis bridges the gap between algorithms and software programs. This book explains the fundamental differences between the computational model assumed for algorithms and the real architectures in which programs execute. It highlights the pitfalls that can occur when implementing an algorithm as software and offers suggestions to solve these problems. The book also explores the interactions among program, compiler, and run-time support system, contrasting this with the simpler model assumed for algorithms. Intended for software developers and programmers, it places particular emphasis on the implications of the memory hierarchy on program efficiency.

ACM/ICPC Training

Online judge System

 

• Valladolid Problem Archive with Online Judge, about 2500 problems, supports C, C++, Pascal and Java programming languages
• Ural State University Problem Archive with Online Judge, over 700 problems
• Saratov State University Problem Archive with Online Judge, over 300 problems
• Peking University Online Judge, over 2800 problems including more than 200 original problems, supports C/C++/Pascal/Java/Fortran.
• Moscow Problem Archive with Online Judge, supports C/C++/Java/Free Pascal/Perl/Python/Haskell/Kylix/Lua/OCaml/Ruby/Scheme.
• Sphere Online Judge, over 5000 problems formulated in English, Polish, Vietnamese, Portuguese; supports 39 different programming languages, hosting own contests supported.
• Lviv National University Online Judge, over 100 hard ACM-type problems. Only Ukrainian language.
• Tianjin University Online Judge, over 2000 problems, supports C/C++/Pascal/Java, virtual contests supported.
• Zhejiang University Online Judge, over 3000 problems, supports C, C++, Pascal and Java.
• Harbin Institute of Technology Online Judge, over 1800 problems. Popular among Chinese people.
• Fuzhou University Online Judge, over 800 problems. Popular among Chinese people.
  

The Data Compression Book

The Data Compression Book 2nd edition By Mark Nelson and Jean-loup Gailly

Download The Data Compression Book

Assembly language

A programming language that is once removed from a computer’s machine language. Machine languages consist entirely of numbers and are almost impossible for humans to read and write. Assembly languages have the same structure and set of commands as machine languages, but they enable a programmer to use names instead of numbers.

Each type of CPU has its own machine language and assembly language, so an assembly language program written for one type of CPU won’t run on another. In the early days of programming, all programs were written in assembly language. Now, most programs are written in a high-level language such as FORTRAN or C. Programmers still use assembly language when speed is essential or when they need to perform an operation that isn’t possible in a high-level language.

Compile and Run C / Java coding directly from Notepad ++

1. Download và Install Notepad++

http://sourceforge.net/projects/notepad-plus/files/

2. Download và Install MinGW hay JDK compiler

http://www.mingw.org/

http://java.sun.com/javase/downloads/index.jsp

3. Cài đặt biến môi trường cho compiler

4. Download và giải nén các files sau đến thư mục gốc của Notepad ++

http://www.mediafire.com/download.php?wylrctyjyym

5. Mở Notepad ++, Goto Run > Run …

6. Paste các dòng text dưới đây vào theo hình minh họa

Compile (C)
"$(NPP_DIRECTORY)\compilec.bat" $(CURRENT_DIRECTORY) $(FILE_NAME) $(NAME_PART)

Run (C)
"$(NPP_DIRECTORY)\runc.bat" $(CURRENT_DIRECTORY) $(NAME_PART)

Compile (Java)
"$(NPP_DIRECTORY)\compilejava.bat" $(CURRENT_DIRECTORY) $(FILE_NAME)

Run (Java)
"$(NPP_DIRECTORY)\run.bat" $(CURRENT_DIRECTORY) $(NAME_PART)

7. Và cuối cùng,

Word Clouds

Làm được bởi wordle.net.

Random Curves : Journeys of a mathematician

Được biết quyển sách này qua lời giới thiệu trên trang chủ của diendantoanhoc, trích sơ lược từ bài viết đó thế này.

Link down sách (click link)

Cuốn tự sự Random Curves kể lại những chuyến du lịch cùng với hoạt động thúc tiến khoa học của GS. Neal Koblitz qua những quốc gia như Liên Xô, Châu Mỹ La Tinh và Việt Nam, cũng như nhiều nơi khác, nơi mà các hoạt động chính trị và các cuộc tranh luận hàn lâm có dính dáng tới nền giáo dục toán học của nước sở tại; đồng thời tác giả không ngừng đấu tranh, thúc đẩy quyền bình đẳng phụ nữ trong nghiên cứu khoa học tại các quốc gia này. Ý tưởng về cuốn Tự sự chỉ mới được hình thành sau khi trao đổi với GS. Scott Vanstone và GS. Ian McKinnon ở một bữa ăn tối tại Hội nghị mật mã năm 2006. Nhiều sự kiện, trải nghiễm mặc dù đã diễn ra từ hơn 30 năm trước song được lột tả lại một cách đầy đủ, chân thực, nguyên bản và vẫn mang tính thời sự, nóng hồi.

Lời giới thiệu

Chương 1: Early Years.
Chương 2:Harvard.
Chương 3: SDS.
Chương 4: The Army.
Chương 5: Spring of 1972.
Chương 6: Academics.
Chương 7: The Soviet Union.
Chương 8: Racism and Apartheid.
Chương 9: Vietnam. Part I.
Chương 10: Vietnam. Part II.
Chương 11: Nicaragua and Cuba.
Chương 12: El Salvador.
Chương 13: Two Cultures.
Chương 14: Cryptography.
Chương 15: Education.
Chương 16: Arizona.
- Mục lục

Và đôi điều về tác giả như sau:

GS. Neal Koblitz đến từ trường đại học Washington, ông được nhiều người biết đến sau năm 1985 khi GS. Neal Koblitz cùng với TS. Victor Miller, một nhà khoa học của IBM, đã độc lập đề xướng kỹ thuật mật mã hóa công khai mới dựa trên các đường cong elliptics.

Nhờ có phương pháp Elliptic Curve Cryptography (ECC) này mà rất nhiều các hướng nghiên cứu cũng như thương mại trong lĩnh vực mật mã đã được bùng nổ. GS. Neal Koblitz tốt nghiệp cử nhân toán học tại trường đại học Harvard và là Putnam Fellow năm 1968. Sau đó ông bảo vệ luận án tiến sĩ tại trường đại học Princeton năm 1974 dưới sự hướng dẫn của GS. Nick Katz. Hiện tại giáo Neal Koblitz đang công tác tại trường đại học Washington đồng thời làm giáo sư thỉnh giảng tại Viện nghiên cứu mật mã ứng dụng thuộc trường đại học Waterloo, Canada.

GS. Neam Koblitz không chỉ dạy Lý thuyết số và công bố các bài báo khoa học ở những tạp chí toán học và mật mã học đầu ngành, ông còn được biết đến rộng rãi qua những hoạt động thúc đẩy khoa học và ủng hộ quyền bình đẳng nữ giới ở những vùng đất bị giới hạn và cấm vận bởi cuộc chiến tranh lạnh trong đó có Liên Xô, Cuba, Việt Nam, Nicaragua và El Salvador. Trong cuốn sách mới nhất xuất bản trên Springer cuối năm 2007 với tiêu đề : Random Curves : Journeys of a mathematician, GS. Neal Koblitz đã kể về cuộc sống nghiên cứu khoa học cũng như những hoạt động thúc tiến của mình ở nhiều vũng lãnh thổ trên thế giới mà ông đã từng đi qua và trải nghiệm. Chính từ cuốn sách này, nhiều người mới cảm thấy khâm phục và trân trọng tình cảm của GS. Neal Koblitz đã ưu ái dành cho Việt Nam, thông qua Viện toán học, qua quỹ Kovalevskaia và cho nền giáo dục của một đất nước gắn liền với hai từ “Chiến tranh” như trong cuốn tự sự của ông đã viết. Diễn đàn toán học xin được trích lại một đoạn từ 2 chương trong tổng số 16 chương của cuốn tự sự này, cũng với lời cảm ơn sâu sắc tới GS. Neal Koblitz – một người bạn lớn của Việt Nam .

Nguồn diendantoanhoc.net

The Nobel Prize in Physics 2009

The Nobel Prize in Physics 2009 for groundbreaking achievements concerning the transmission of light in fibers for optical communication and for the invention of an imaging semiconductor circuit – the CCD sensor

(be known by NQHung’s blog)

See more: Vnexpress.net (Vietnamese) or Cnet.com (English)

Mid-Autumn Festival

The joyous Mid-Autumn Festival, the third and last festival for the living, was celebrated on the fifteenth day of the eighth moon, around the time of the autumn equinox. Many referred to it simply as the “Fifteenth of the Eighth Moon”. In the Western calendar, the day of the festival usually occurred sometime between the second week of September and the second week of October.

This day was also considered a harvest festival since fruits, vegetables and grain had been harvested by this time and food was abundant. With delinquent accounts settled prior to the festival , it was a time for relaxation and celebration. Food offerings were placed on an altar set up in the courtyard. Apples, pears, peaches, grapes, pomegranates , melons, oranges and pomelos might be seen. Special foods for the festival included moon cakes, cooked taro, edible snails from the taro patches or rice paddies cooked with sweet basil, and water caltrope, a type of water chestnut resembling black buffalo horns. Some people insisted that cooked taro be included because at the time of creation, taro was the first food discovered at night in the moonlight. Of all these foods, it could not be omitted from the Mid-Autumn Festival.

The round moon cakes, measuring about three inches in diameter and one and a half inches in thickness, resembled Western fruitcakes in taste and consistency. These cakes were made with melon seeds, lotus seeds, almonds, minced meats, bean paste, orange peels and lard. A golden yolk from a salted duck egg was placed at the center of each cake, and the golden brown crust was decorated with symbols of the festival. Traditionally, thirteen moon cakes were piled in a pyramid to symbolize the thirteen moons of a “complete year,” that is, twelve moons plus one intercalary moon.

Origin

The Mid-Autumn Festival is a traditional festivity for both the Han and minority nationalities. The custom of worshipping the moon (called xi yue in Chinese) can be traced back as far as the ancient Xia and Shang Dynasties (2000 B.C.-1066 B.C.). In the Zhou Dynasty(1066 B.C.-221 B.C.), people hold ceremonies to greet winter and worship the moon whenever the Mid-Autumn Festival sets in. It becomes very prevalent in the Tang Dynasty(618-907 A.D.) that people enjoy and worship the full moon. In the Southern Song Dynasty (1127-1279 A.D.), however, people send round moon cakes to their relatives as gifts in expression of their best wishes of family reunion. When it becomes dark, they look up at the full silver moon or go sightseeing on lakes to celebrate the festival. Since the Ming (1368-1644 A.D. ) and Qing Dynasties (1644-1911A.D.), the custom of Mid-Autumn Festival celebration becomes unprecedented popular. Together with the celebration there appear some special customs in different parts of the country, such as burning incense, planting Mid-Autumn trees, lighting lanterns on towers and fire dragon dances. However, the custom of playing under the moon is not so popular as it used to be nowadays, but it is not less popular to enjoy the bright silver moon. Whenever the festival sets in, people will look up at the full silver moon, drinking wine to celebrate their happy life or thinking of their relatives and friends far from home, and extending all of their best wishes to them.

Moon Cakes

There is this story about the moon-cake. during the Yuan dynasty (A.D. 1280-1368) China was ruled by the Mongolian people. Leaders from the preceding Sung dynasty (A.D. 960-1280) were unhappy at submitting to the foreign rule, and set how to coordinate the rebellion without being discovered. The leaders of the rebellion, knowing that the Moon Festival was drawing near, ordered the making of special cakes. Backed into each moon caked was a message with the outline of the attack. On the night of the Moon Festival, the rebels successfully attached and overthrew the government. Today, moon cakes are eaten to commemorate this legend and was called the Moon Cake.

For generations, moon cakes have been made with sweet fillings of nuts, mashed red beans, lotus-seed paste or Chinese dates, wrapped in a pastry. Sometimes a cooked egg yolk can be found in the middle of the rich tasting dessert. People compare moon cakes to the plum pudding and fruit cakes which are served in the English holiday seasons.

Nowadays, there are hundreds varieties of moon cakes on sale a month before the arrival of Moon Festival.

Different Celebrated Forms

For thousands of years, the Chinese people have related the vicissitudes of life to changes of the moon as it waxes and wanes; joy and sorrow, parting and reunion. Because the full moon is round and symbolizes reunion, the Mid-Autumn Festival is also known as the festival of reunion. All family members try to get together on this special day. Those who can not return home watch the bright moonlight and feel deep longing for their loved ones.

Today,festivities centered about the Mid-Autumn Festival are more varied. After a family reunion dinner, many people like to go out to attend special perfomances in parks or on public squares.

People in different parts of China have different ways to celebrate the Mid-Autumn Festival. In Guangzhou in South China, a huge lantern show is a big attraction for local citizens. Thousands of differently shaped lanterns are lit, forming a fantastic contrast with the bright moonlight.

In East Chia’s Zhejiang Province, watching the flood tide of the Qian-tang River during the Mid-Autumn Festival is not only a must for local peple, but also an attraction for those from other parts of the country. The ebb and flow of tides coincide with the waxing and waning of the moon as it exerts a strong gravitational pull. In mid autumn, the sun, earth and moon send out strong gravitational forces upon the seas. The outh of the Qiantang River is shaped lik a bugle. So the flood tide which forms at the narrow mouth is particularly impressive. Spectators crowd on the river bank,watching the roaring waves. At its peak, the tide rises as high as three and a half meters.

Legends

There are many beautiful legends about the moon in China. the most popular one tells how a goddess named Chang’e ascended to the moon.

A long, long time ago, a terrible drought plagued the earth. Ten suns burned fiercely in the sky like smoldering volcanoes. The trees and grass were scorched. The land was cracked and parched, and rivers ran dry. Many people died of hunger and thirst.

The King of Heaven sent Hou Yi down to the earth to help. When Hou Yi arrived, he took out his red bow and white arrows and shot down nine suns one after another. The weather immediately turned cooler. Heavy rains filled the rivers with fresh water and the grass and trees turned green. Life had been restored and humanity was saved.

One day, a charming young woman, Chang’e makes her way home from a stream, holding a bamboo contaiver, A young man comes forward, asking for a drink. When she sees the red bow and white arrows hanging from his belt, Chang’e tealizes that he is their savior, Hou Yi. Inviting him to drink, Chang’e plucks a beautiful flower and gives it to him as a token of respect. Hou Yi, in turn, selects a beautiful silver fox fur as his gift for her. This meeting kindles the spark of their love. And soon after that, they get married.

A mortal’s life is limited, of course. So in order to enjoy his happy life with Chang’e forever, Hou Yi decides to look for an elixir of life.He goes to the Kunlun Mountains where the Western Queen Mother lives.

Out of respect for the good deeds the has done, the Western Queen Mother rewards Hou Yi with elixir, a fine powder made from kerndls of fruit which grows on the tree of eternity. At the same time, she tells him:If you and your wife share the elixir, you will both enjoy eternal life. But if only one of you takes it,that one will ascend to Heaven and become immortal.

Hou Yi returns home and tells his wife all that has happened and they decide to drink the elixir together on the 15th day of the eighth lunar month when the moon is full and bright.

A wicked and merciless man named Feng Meng secretly hears about their plan.He wishes Hou Yi an early death so that he can drink the elixir himeslf and become immortal.His opportunity finally arrives. One day,when the full moon is rising, Hou Yi is on his way home from hunting. Feng Meng kills him. The murderer then runs to Hou Yi’s home and forces Chang’e to give him the elixir, Without hesitating, Chang’e picks up the elixir and drinks it all.

Overcome with grief, Chang’e rushes to her dead husband’s sied, weeping bitterly.Soon the elixir begins to have its effect and Chang’e feels herself being lifted towards Heaven.

Chang’e decides to live on the moon because it is nearest to the earth. There she lives a simple and contented life. Even though she is in Heaven, her heart remains in the world of mortals. Never does she forget the deep love she has for Hou Yi and the love she feels for the people who have shared their sadness and happiness.

Another legend explained the role of the Old Man on the Moon, the Divine Match-maker. The Chinese believed that marriages were made in Heaven but prepared on the moon. The Old Man on the Moon tied the feet of young men and women with red cords for marriage. Thus a maiden made offerings and prayed to him during the Mid-Autumn Festival, hoping that some day she would ride in the red bridal sedan chair.

source http://www.chinavoc.com/festivals/Midautumn.htm

Mid-Autumn Festival in VietNam

Vietnamese people are living in a joyful atmosphere of the forthcoming Mid-Autumn Festival as moon- cakes in vivid red boxes and various kinds of colorful toys crop up all over the country.

Mid-Autumn Festival, which falls on Thursday, is a traditional one for children in Vietnam. However, in recent years, many people, especially youths have taken advantages of the festival to gather for drinking, eating and going out.

In recent days, along Ba Trieu street from the Sword Lake to Dai Co Viet street in Hanoi, there are dozens of shops selling moon cakes with trademarks of Kinh Do, Dong Khanh, Huu Nghi, and Bao Ngoc. In many other streets, such as Trang Tien, Hang Buom, and Hang Than, it is common to catch a sight of piles of moon- cakes displayed in shops beautifully decorated with colorful banners and lanterns.

Loan, a resident in Hang Than street, told Xinhua that this is the first time the street has seen so many beautiful moon-cake shops. Moon-cakes with diversified flavors, shapes, sizes, and prices have flooded the market. The cake prices range from thousands to hundreds of thousands of Vietnamese dong (15,000 Vietnamese dong equaling to a US dollar) per package, depending on its size and core.

Besides moon-cakes with traditional flavors of lotus seed, salted egg, and green bean, many of Hanoi’s large hotels, such as Sofitel Metropole, Hilton and Horision, are offering their guests some variations of the festival favorite, such as French-style, chocolate, taro, and red bean flavors. Its price is averagely about 15 US dollars per package which may be out of reach of most Hanoians.

Despite moon-cake flooded market, Hanoians remain loyal to the products with lower prices of some local well-known makers such as Kinh Do and Huu Nghi. At an agent of Kinh Do Bakery in Thai Ha street, customers have to queue up to buy cakes.

Nguyen Huyen, head of Marketing Department of Kinh Do Bakery said, about a week before the festival is the peak period of selling moon-cakes. This year, consumers tend to buy beautifully packaged high-quality products. To meet the rising demand, the enterprise has turned out 260 tons, up 20 percent over last year.

Together with moon-cakes and fruits, toys are an important part of the festival for children. The local toy market is heating up when the festival nearly comes. This year, most of shops in Hanoi’ s main toy-selling streets of Luong Van Can, Hang Luoc and Hang Ma have launched the newest toy models. However, the traditional toys such as enlightened star-shaped lanterns and masks still appear to be available.

Folk toys in bright colors, including animals made of porcelain, hand-made dolls, and boats, are widely displayed in pavements of Hang Ma Street in evenings.

Chinese-made products are dominating the local toy market as more than 70 percent of plastic toys in the market are imported from China. Shops in some toy-selling streets show 500-1,000 items, including supermen, moon sailors, dolls, and battery-powered cars. Most of the products are newly designed with fashionable styles and colors.

Hung, a shop owner in Hang Ma Street, said every day he receives more than 100 customers. Best sellers include Chinese- made modern toys and enlightened lanterns, which are indispensable for the festival’s parties.

Toy-selling streets attract thousands of children and parents every day. In evenings, especially on Saturday and Sunday evenings, the streets are jammed toy buyers and are in a festive atmosphere of colorful lights and flowers.

A wide range of art performances are being held nationwide to serve children during the festival which falls on Thursday. A Mid- Autumn festival with children and family fair is ongoing in Hanoi’ s Center for Cultural Exhibition. A giant star-shaped lantern, 23. 9 meters in height, the biggest ever made in Vietnam, is on display at the fair.