Blog:Computer Science
From Evan Sultanik
del.icio.usComputer Science: an Introduction
People often ask me what I do or about what I am studying. Many have certain misconceptions and stereotypes that render the simple answer of "Computer Science" insufficient. For example, the vast majority of non-technical people with whom I've talked seem to think that learning new programming languages and writing programs are the primary areas of study for computer-related university majors. That's like believing literature majors go to university to learn the intricacies of using pens and typewriters. In the ~7 years—and counting (gasp!)—in which I've been in higher education, I haven't been taught a single programming language.
The following is an attempt on my part to answer these questions, in the hopes that I can hereafter simply refer people to this page instead of having to explain this for the thousandth time.
Contents |
What is Computer Science?
The vast majority of people that call themselves "Computer Scientists" occupy themselves with solving problems. This begs the question: What is a problem? In this context, a problem is a language. Do I mean a language in the sense of "English," "Russian," or "Pig Latin?" In a way, yes. Now, let me explain.
Languages and problems
A language is really just a set of grammar rules and a set of words that constitute a vocabulary. For example, everything I've written so far is a part of the English language because (1) all of the sentences conform to the English grammar, and (2) all of the words of the sentences are of the English vocabulary. Although the sentence "Evan writing" contains two words that are both in the English vocabulary, the lack of a given verb (i.e. the verb to be) means that it does not conform with the English grammar and is thereby not an English sentence. Likewise, the sentence, "Boy ball threw," is not an English sentence because it is unclear from the word order which noun is the subject and which is the object.
The majority of the work in Computer Science is concerned with automatically and efficiently testing whether a given sentence conforms to a given language.
Example: Sudoku
For example, let's consider the popular game of Sudoku. A "language" for Sudoku might consist of:
- Vocabulary: 1, 2, 3, 4, 5, 6, 7, 8, 9
- Grammar: The set of all sentences that are exactly
characters long (representing the 81 Sudoku squares) and that conform to the Sudoku property.
It's relatively easy to test whether a given sentence conforms to the Sudoku grammar; all we have to do is make sure that the Sudoku property holds (i.e. there are no repeats in the columns, rows, or boxes). This can be done relatively quickly by a human, and almost instantaneously by a computer. A computer scientist, however, might try and solve the following problem: "Given a partially complete sentence, either complete the sentence such that it conforms to the Sudoku grammar or prove that such a completion does not exist." Such a problem is much harder to solve.
The majority of computer science consists of creating automated algorithms that can solve such problems. The question is: how expensive is the algorithm? Since testing whether a sentence is in the grammar is easy, one might just enumerate all of the possible Sudoku grid layouts and find the first one that is a part of the grammar. The problem is that, in the worst case, there will be on the order of 981 = 196,627,050,475,552,913,618,075,908,526,912,116,283,103,450,944,214,766,927,315,415,537,966,391,196,809 (i.e. about one Quinquavigintillion) possibilities to test! Even if a computer could test a trillion sentences per second, such an algorithm would take about 6 octodecillion years to finish (that's 6 with 57 zeros afterward)! What we really want are what are called polynomial time algorithms.
Polynomial time
Let's say a given problem is of size n. For example, our Sudoku problem would be of size n = 3 because the grid is composed of nine 3-by-3 sub-squares. Now let's say we devise an algorithm (i.e. solution method) that allows us to solve any given Sudoku problem in no more than 1000 steps. That's pretty quick! Using this algorithm a computer could solve any n = 3 Sudoku problem almost instantaneously. Now, let's say we get bored with n = 3 Sudokus (since they're so easy to solve now) and we now want to solve Sudoku problems on larger grids—say a n = 4 Sudoku (i.e. a grid of sixteen 4-by-4 sub-squares). As I mentioned before, the number of possibilities for n = 9 was about 981; for n = 10 there are on the order of 
possibilities! By most estimates that's over three times the number of atoms in the universe! The question is: given that our algorithm is so efficient at solving problems where n = 3, how fast will it be able to solve problems when we just increase n by 1?
If for each increase in n it turns out that the amount of time the algorithm needs to solve the problem increases by at most a linear amount, then we say the algorithm runs in polynomial time. This means that if we have a problem of size n then a polynomial time algorithm for that problem will run in at most roughly nc steps, where c is some constant.
Why polynomial time matters
Moore's law states that processor speed doubles every two years
[1]. This means that if we have a polynomial time algorithm that is able to quickly solve a problem of size n on current hardware, we will only have to wait about 
years until computer hardware becomes fast enough to solve a problem of size n + 1. For most values of n and c, that's a very short time!
Why Computer Science isn't just a science
Depending on one's discipline, Computer Science is really an amalgam of mathematics, science, and engineering. One way of thinking about the various computing disciplines is in what types of problems they aim to solve. There is a whole field of "Computer Science" concerned with discovering new efficient (e.g. polynomial time) algorithms; this field is rooted in pure mathematics. Once can devise an algorithm and formally prove its computational efficiency; no "experimentation" is required.
It turns out, however, that there are some classes of languages/problems that are so hard that it is probably impossible to devise a polynomial time algorithm to solve them! Sudoku is actually one such problem. There is therefore an entire discipline within Computer Science concerned with finding algorithms that give an approximate solution whose quality is not necessarily optimal but within a close range of optimal. This field is also rooted in pure mathematics.
Then there are problems that are so complex that either no approximation can be found or, perhaps, one doesn't even know the grammar for the problem's language. For example, consider the game of poker. Since poker is both non-deterministic (i.e. there is chance involved) and unobservable (i.e. one doesn't necessarily know what is going on in other players' hands/heads), an optimal poker-playing algorithm/strategy will be a function of the other players' strategies. How can one prove that one's poker playing algorithm is not only efficient, but optimal? How does one know that it will always play well, regardless of the opponents' strategies? Creating the algorithm may require building heuristics, which is engineering. Evaluating the algorithm requires experimentation: playing one's algorithm against a number of opponents over a number of games and observing the outcome, which is science.
The latter field generally falls under the term "Artificial Intelligence" (AI), the definition for which I usually give being, "The creation of systems capable of finding solutions to arbitrarily difficult problems." The practitioners of AI generally fall into two camps: the neats and the scruffies. The neats like to design systems using formal logic and mathematics; since such methods are infallible, once a method is produced then the work is done. The scruffies, on the other hand, like to engineer systems that tend to get a job done and then, retrospectively, examine the system to figure out why it worked.
I study AI and I generally fall into the "neat" camp.
References
| Previous: Wireless remote control | Blog Entries | Next: Economics of Education |
| Date | 25 February 2009 10:07 + |
| Title | Computer Science: an Introduction |