Wednesday, October 17, 2007

Computers and Math

The advent of computing affected a great many fields, and one of those was that of mathematics.

One method of mathematical proof is proof by exhaustion. This is when you split a statement into a number of cases, and prove each of those cases to be true. Some problems that can be solved this way require hundreds of cases. A problem so large would take a extremely long time to check by hand. So computers are enlisted. This was done for the first time in 1976 to prove the Four Color Theorem, which states that given a plane divided into numerous sections, no more than four colors are required to color every section so that no two sections sharing a border would be the same color.

More recently, checkers was solved with the aid of computers. It was determined that given perfect play, the game would result as a draw, like tic-tac-toe. Though, that was done by checking every possible board configuration, which took eighteen years.

Computers have also opened new fields of mathematics. One example of this is analysis of algorithms. Although algorithms have been around for over a millennium, they were not so important as to need their own field of study until computers. Because computers can only run using algorithms, it becomes important to be able to tell if one algorithm is better or worse than another. One way of doing this is by big O notation. Big O notation allows you to analyze how long an algorithm will take to solve a problem, given an input of a known size.

No comments: