All computer programs do some form of counting as a small part of a task. Counting a hundred items does not take a long time, even without a computer. However, some computers may have to count a billion items or more. If the counting is not done efficiently, it may take days for a program to finish a report when it should take only minutes. For example, the counting winning lottery numbers of all lottery tickets should involve stopping a ticket count when the minimum number of correct numbers cannot be reached on that particular ticket. When the lottery numbers on each ticket are presorted, the count can be very quick with a divide and conquer strategy. The branch of mathematics called combinatorics gives students the theory needed to code counting programs that include the short cuts that will reduce the run time of the program.
After a count has been completed, a task to do something with the actual number from the count is needed. The number of steps needed to complete a task should be minimized so the computer can return a result faster for a large number of tasks. Again, if a task needs to be done only 20 times, it will not take long even for the slowest computer. However, if the task needs to be done a billion times, an inefficient algorithm with too many steps could take days instead of hours to be completed, even on a million-dollar computer. For example, there are many ways to sort a list of unsorted numbers from lowest to highest, but some algorithms take too many steps, which could cause the program to run much longer than necessary. Learning the mathematics behind algorithms allows students to create efficient steps in their programs.
Problems in computers are much bigger than just counting and algorithms. Automata theory studies problems that have a finite or infinite number of potential outcomes of varying probability. For example, computers trying to understand the meaning of word with more than one definition would need to analyze the entire sentence or even a paragraph. After all the counting and algorithms on the sentence or paragraph are done, rules to determine the correct definition are needed. The creation of these rules is part of automata theory. Probabilities are assigned to each definition depending on the results of the algorithm portion for the paragraph. Ideally, the probabilities are just 100 percent and 0 percent, but many real-world problems are complicated with no certain outcome. Computer compiler design, parsing and artificial intelligence make heavy use of automata theory.
About the Author
John Wu is a writer who has covered computers, health, fitness and business since 2008 for various online publications. He is also an IT manager at a government agency. Wu holds a B.A. in legal studies from University of California, Berkeley and a B.S. in computer science from San Jose State University.