It is now time to move away from the introductory posts, and delve deeper into specific topics. Being a graph theorist myself, I decided to make Graph Theory my first non-introductory post.
(For the introductory post to this field, please read this post.)
In the previous post on this topic, I finished with certain questions one can ask about graphs. The first of these is about the connectivity of graphs. Namely, the question is, given two vertices u and v in a graph, can we find some way to get from u to v, following edges in the graph? This is a very easy problem to visualise. If a graph is made up of two or more parts (known as components), then it is impossible to get from a vertex in one component to a vertex in another component. We say that the graph is disconnected. Now, let's say that for every pair of vertices u and v in a graph, you can find some path u, x1, x2, ... , v which moves through consecutively adjacent vertices x1, x2 and so on. Then there cannot be more than one component in the graph and we say the graph is connected.
This question of connectivity can be easily extended in two important ways. The first one deals with the best way to get from one vertex to another. Let's say that the vertices correspond to cities and the edges to roads connecting them. Now, for simplicity, let's say that each edge costs you 5 euros in gasoline. Then, to minimise your costs, you will want to find the path that uses the fewest edges. Going from Munich to Bologna and from there to Paris is possible, but it is generally much cheaper to go as directly as you can. This leads to the idea of the shortest path. That is, given vertices u and v in a graph, what is the shortest path between them? Clearly, for any two vertices, if you can find some path between them, a shortest path must also exist. This is because paths have non-negative length, so you cannot reduce path length indefinitely. One of the most well-known methods for finding shortest paths is Dijkstra's Algorithm. The way it works is by searching for the shortest path from the starting vertex u to every other vertex. This is done by splitting the graph into two parts: the explored vertices and the unexplored vertices. Additionally, for every vertex v, the algorithm maintains a tentative distance from u to v. Initially, only the starting vertex is explored. At each step, the algorithm picks the unexplored vertex with the shortest distance and explores it. Whenever a vertex v is explored, the algorithm attempts to find a shortest path from u to the neighbours of v, by incorporating v. If a path shorter than what was available before can be found, these neighbours are updated accordingly.
The reason this algorithm works, is that the shortest path between two vertices is made up of other shortest paths. That is, if the shortest path from u to v goes through x, then it contains the shortest path from u to x, followed by the shortest path from x to v. The algorithm seeks all such shortest subpaths and picks the best available one.
The second way in which connectivity can be extended is with the notion of k-connectivity. Let's say there are several path between two vertices, u and v. If we were to remove some vertices from the graph (and all the edges that go with them) would there still be a path between u and v? How many vertices make it impossible for us to find such a path? What about removing edges? The ideas of connectivity are important in various problems of resource management. Suppose you have to provide internet service to some locations. You would use various connecting stations, which would handle the traffic of information and route it from place to place. But what if some of these stations were to be damaged? Could your network cope? And how many stations can you safely shut down at a time for maintenance, without compromising the quality of your service? As you can see, the question of connectivity is very important for proper resource management.
Saturday, August 25, 2012
Friday, August 24, 2012
Algorithms
The joke goes that when George W. Bush found out that colleges were teaching their Computer Science majors about Algorithms, he complained about unequal representation and asked that they also teach GeorgeBushisms as well. But what exactly are Algorithms? Why do computer scientists learn about them? What do they, in fact, do?
Imagine you are about to do something. This "something" could be a very simple task, like opening your internet browser, or something more complicated, like baking a cake. How do you go about doing it?
If you think about it, all processes have certain steps, which need to be carried out, usually in a precise sequence, in order to be completed. Opening your browser can, for example, be achieved by moving your mouse until the cursor is pointing to the relevant icon, then double-clicking. Performing these steps out of sequence probably won't get you very far, unless you're lucky.
Algorithms are nothing but step-by-step instructions for performing a task. We usually use the word to denote a mathematical or computational task, but, in fact, the instructions for opening your internet browser is also an algorithm.
Now, let's take a different task. Take a piece of paper and a pen. Draw a straight line. Now draw a second line, which starts wherever the first one ended and goes in a different direction. Draw a third line, starting from the same point, but in a different direction. Now connect the remaining three end points with a curve.
Did you get the Mercedes-Benz logo? Probably not. The reason for this was that my instructions were extremely imprecise. I did not tell you how to orient the lines. I did not tell you what angles to make between them. I did not tell you how long to make them. I did not tell you to make the final curve a circle. All these omissions most likely made your drawing something completely arbitrary, not resembling the mentioned logo at all. An algorithm cannot be vague like that. Each instruction must be precise enough, so that whenever someone attempts to perform the same task under the same conditions must get the same result. (With the exception of using randomness, like rolling a die).
When it comes to computers, every piece of software is a sequence of instructions to the computer, telling it what to do, from moving numbers around, to accepting some sort of input, to controlling your enemies in a video game. These instructions are in the language of the computer itself, so there is no longer a problem about vague instructions. So, why is there a need to study algorithms? There are two main reasons. The first one is that, even though a set of instructions can be precise, this doesn't mean that it will do what is intended. The study of algorithms helps us understand ideas like data flow, prerequisites and programme correctness. The second reason is that the same task can often be performed in many different ways. Instead of using a mouse to double-click on the correct icon, you may also be able to open your browser by going into a command prompt and type the appropriate commands to get to the correct folder and run the correct file and so on. Sometimes, one of the ways of performing a task is better (faster, more efficient, less prone to error and so on) than another. However, which method is better is not always clear. This is where algorithm analysis helps. We can analyse a given set of instructions in terms of the time it takes, the possible errors it may encounter and even its correctness, before even running the programme itself.
Imagine you are about to do something. This "something" could be a very simple task, like opening your internet browser, or something more complicated, like baking a cake. How do you go about doing it?
If you think about it, all processes have certain steps, which need to be carried out, usually in a precise sequence, in order to be completed. Opening your browser can, for example, be achieved by moving your mouse until the cursor is pointing to the relevant icon, then double-clicking. Performing these steps out of sequence probably won't get you very far, unless you're lucky.
Algorithms are nothing but step-by-step instructions for performing a task. We usually use the word to denote a mathematical or computational task, but, in fact, the instructions for opening your internet browser is also an algorithm.
Now, let's take a different task. Take a piece of paper and a pen. Draw a straight line. Now draw a second line, which starts wherever the first one ended and goes in a different direction. Draw a third line, starting from the same point, but in a different direction. Now connect the remaining three end points with a curve.
Did you get the Mercedes-Benz logo? Probably not. The reason for this was that my instructions were extremely imprecise. I did not tell you how to orient the lines. I did not tell you what angles to make between them. I did not tell you how long to make them. I did not tell you to make the final curve a circle. All these omissions most likely made your drawing something completely arbitrary, not resembling the mentioned logo at all. An algorithm cannot be vague like that. Each instruction must be precise enough, so that whenever someone attempts to perform the same task under the same conditions must get the same result. (With the exception of using randomness, like rolling a die).
When it comes to computers, every piece of software is a sequence of instructions to the computer, telling it what to do, from moving numbers around, to accepting some sort of input, to controlling your enemies in a video game. These instructions are in the language of the computer itself, so there is no longer a problem about vague instructions. So, why is there a need to study algorithms? There are two main reasons. The first one is that, even though a set of instructions can be precise, this doesn't mean that it will do what is intended. The study of algorithms helps us understand ideas like data flow, prerequisites and programme correctness. The second reason is that the same task can often be performed in many different ways. Instead of using a mouse to double-click on the correct icon, you may also be able to open your browser by going into a command prompt and type the appropriate commands to get to the correct folder and run the correct file and so on. Sometimes, one of the ways of performing a task is better (faster, more efficient, less prone to error and so on) than another. However, which method is better is not always clear. This is where algorithm analysis helps. We can analyse a given set of instructions in terms of the time it takes, the possible errors it may encounter and even its correctness, before even running the programme itself.
Wednesday, August 8, 2012
Game Theory
This topic is one of the main parts of what are known as Decision Mathematics. Naturally, the title Game Theory makes the field sound like people playing chess or poker; doing recreational activities. This is actually not the case.
Game Theory is all about making choices, in given scenarios. What makes these scenarios special is that you are not the only one making choices; others are doing this as well and the outcome is affected by their choices as well as yours. One such example is that of conflict. In a battle between two opposing sides, each side may choose to fight or retreat (there are actually many more choices, but I am simplifying here for illustration purposes). If one side fights and the other retreats, the side that fought gains some advantage, e.g. some high ground. In game theory, we may assign a certain amount of points to this outcome, for example the attacking side gets 1 point, whilst the retreating side gets -1 point, to quantify the advantages gained and lost. On the other hand, if both sides fight, they will have a lot of casualties, so both sides get -2 points. Finally, if both sides retreat, they have not yielded anything to the opponent, so they both get 0 points.
Let us assume you are a military advisor of sorts, to one of the sides. What would be the best plan, for this battle? Should you attack or retreat? If we look at the possible results, fighting will get you either 1 or -2 points, whilst retreating will get you 0 or -1. If you want to make sure that you do no worse than a score of -1, you should retreat. This is known as the maximin strategy, as it seeks to maximise the minimum possible result. On the other hand, attacking ensures that the enemy will certainly have a score of at most -1. This would be an aggressive tactic. Of course, if the opponent is known to be aggressive, attacking will result in the worst possible score, for both sides. On the other hand, if the enemy is known to retreat a lot, attacking will cause a gain in points for your side.
As you can see, this sort of decision making is not always easy. In fact, depending on the scenario presented, it could be that every choice is a "bad" one. Or, alternatively, there can be an "obviously good" choice, which is always the best to choose. All these considerations are what Game Theorists study. From the above, it is obvious that the ideas of game theory have a clear practical application in such things as warfare (as well as politics, business management and so on). This may seem like a stretch, considering the simplicity of the scenario I presented, but the ideas were applied during the Cold War, amongst others. And since nuclear arms were already available by then, it can be seen how desirable it is that military advisors should be able to identify strategies such as "minimax" as the best ones to take.
As an exercise, you can try to teach yourself some elementary decision-making. Make your own scenario for two sides in a game, each having two options and each pair of options resulting in a certain point score. It should be fairly easy to figure out what scores make a perfect strategy possible. What about more choices? Or more players? Or both? Is it always clear if a scenario has a perfect strategy or not?
Game Theory is all about making choices, in given scenarios. What makes these scenarios special is that you are not the only one making choices; others are doing this as well and the outcome is affected by their choices as well as yours. One such example is that of conflict. In a battle between two opposing sides, each side may choose to fight or retreat (there are actually many more choices, but I am simplifying here for illustration purposes). If one side fights and the other retreats, the side that fought gains some advantage, e.g. some high ground. In game theory, we may assign a certain amount of points to this outcome, for example the attacking side gets 1 point, whilst the retreating side gets -1 point, to quantify the advantages gained and lost. On the other hand, if both sides fight, they will have a lot of casualties, so both sides get -2 points. Finally, if both sides retreat, they have not yielded anything to the opponent, so they both get 0 points.
Let us assume you are a military advisor of sorts, to one of the sides. What would be the best plan, for this battle? Should you attack or retreat? If we look at the possible results, fighting will get you either 1 or -2 points, whilst retreating will get you 0 or -1. If you want to make sure that you do no worse than a score of -1, you should retreat. This is known as the maximin strategy, as it seeks to maximise the minimum possible result. On the other hand, attacking ensures that the enemy will certainly have a score of at most -1. This would be an aggressive tactic. Of course, if the opponent is known to be aggressive, attacking will result in the worst possible score, for both sides. On the other hand, if the enemy is known to retreat a lot, attacking will cause a gain in points for your side.
As you can see, this sort of decision making is not always easy. In fact, depending on the scenario presented, it could be that every choice is a "bad" one. Or, alternatively, there can be an "obviously good" choice, which is always the best to choose. All these considerations are what Game Theorists study. From the above, it is obvious that the ideas of game theory have a clear practical application in such things as warfare (as well as politics, business management and so on). This may seem like a stretch, considering the simplicity of the scenario I presented, but the ideas were applied during the Cold War, amongst others. And since nuclear arms were already available by then, it can be seen how desirable it is that military advisors should be able to identify strategies such as "minimax" as the best ones to take.
As an exercise, you can try to teach yourself some elementary decision-making. Make your own scenario for two sides in a game, each having two options and each pair of options resulting in a certain point score. It should be fairly easy to figure out what scores make a perfect strategy possible. What about more choices? Or more players? Or both? Is it always clear if a scenario has a perfect strategy or not?
Saturday, July 28, 2012
Infinity and Cardinality
Infinity is a topic which is generally rather hard to grasp. Our world does not readily provide anything infinite for us to study in the Sciences. Indeed, if some structure was infinite, we would not be able to study it fully; indeed, we would not be able to find all its edges. It would have no shape, no measurable volume, no mass, energy or velocity which we would be in any way able to comprehend. And yet, in mathematics, the idea of infinity can actually have meaning, which shows that our imagination is not solely confined to the extent of our experiences. More than that, infinity can actually help us understand the finite physical, chemical, biological etc. structures with which scientists deal all the time. Infinity helps us understand sequences, which in turn helps in the understanding of limits, giving rise to the ideas of calculus, on which most contemporary Science and Engineering methods rely.
So, what is infinity? In general, we often treat it as a number. We may put it in the limits of a sum, a product or an integral, we may even give it as the result of these things. However, infinity is not, in fact a number. (This assertion is true in the reals. There are formal systems, like the hyperreal numbers, where infinity is a number. These systems are not what I am talking about here.)
Probably the most important work on infinity was done by Georg Cantor, when he formalised the ideas of infinite sets. Indeed, the best way to think of infinity is as a measure of the elements of an infinite set. As for finding such an infinite set, this is simple. We can simply take the positive integers (also known as the natural numbers), 1, 2, 3... and so on. We call this set N and consider the number of elements it contains. Obviously, it cannot be empty, as it contains the number 1. It cannot have only 1 element, as it contains the numbers 1 and 2. Similarly, it cannot contain only 100 elements, as every number from 1 to 101 is in N. For any positive integer we think of, we can find that many elements in N, and more. This is the very idea of infinity: something that is not bounded, which is larger than any number.
As we can see, this set of the natural numbers is infinite, in that it has infinitely many elements. Naturally, this means that any set which contains the natural numbers and others as well (a "superset" of N, as it is called) would also be of infinite size. We can take, for example, the set of all integers, Z. This includes the natural numbers (since they are the positive integers), as well as the negative integers and zero. Intuitively we can see that this must be a bigger set than N. Unfortunately, our intuition is wrong. When it comes to infinite sets, the only way to decide if Z is larger than N is to examine whether a bijection (one-to-one and onto function) exists between the two sets. If such a function can be found, then automatically the sets must have the same "size". Note that the natural numbers are essentially the numbers we count with, 1, 2, 3 and so on. So, finding a bijection between Z and N is the same as finding some way of listing all the elements of Z, without missing any, in a certain order. If such a sequence exists for Z, then Z and N have the same "size". This sequence is extremely easy to come up with: 0, 1, -1, 2, -2... and so on. Obviously this ordering will go through every single integer, much in the same way that 1, 2, 3... goes through every natural number.
The above shows us that Z has, in a sense, the same number of elements as N. Except that, as they both have infinitely many elements, we are not really talking about a number of elements. Because of this, the idea of cardinality was formulated. Cardinality can be thought of as the size of infinite sets, like the naturals or the integers. so, our example above shows that in fact both N and Z have the same cardinality, even if one is a subset of the other. This is a very important concept; infinity does not behave in the same way that other numbers do. Cutting infinity in half or doubling it does not actually change its size at all.
At this point one might think that all infinite sets must have the same cardinality as the natural numbers. After all, it should be easy to find a sequence that lists all the elements in a set. This is often the case; sets like the rational numbers, the algebraic numbers, the set of polynomials with integer coefficients and so on are certainly all countable (i.e. have the same cardinality as N). But there are sets which are actually much larger. The set of real numbers is actually uncountable. Any attempt to make a comprehensive list of all the reals, will result in failure. Indeed any such list can be shown to be missing some real numbers (in fact, an infinite amount of them). The proof for this uses a rather elegant method devised by Cantor, known as Cantor's diagonal argument.. I do not propose to present it here, as it is readily available online in other places. However, it should be clear from all this that the subject of cardinalities and the nature of infinity is one with a lot of substance.
So, what is infinity? In general, we often treat it as a number. We may put it in the limits of a sum, a product or an integral, we may even give it as the result of these things. However, infinity is not, in fact a number. (This assertion is true in the reals. There are formal systems, like the hyperreal numbers, where infinity is a number. These systems are not what I am talking about here.)
Probably the most important work on infinity was done by Georg Cantor, when he formalised the ideas of infinite sets. Indeed, the best way to think of infinity is as a measure of the elements of an infinite set. As for finding such an infinite set, this is simple. We can simply take the positive integers (also known as the natural numbers), 1, 2, 3... and so on. We call this set N and consider the number of elements it contains. Obviously, it cannot be empty, as it contains the number 1. It cannot have only 1 element, as it contains the numbers 1 and 2. Similarly, it cannot contain only 100 elements, as every number from 1 to 101 is in N. For any positive integer we think of, we can find that many elements in N, and more. This is the very idea of infinity: something that is not bounded, which is larger than any number.
As we can see, this set of the natural numbers is infinite, in that it has infinitely many elements. Naturally, this means that any set which contains the natural numbers and others as well (a "superset" of N, as it is called) would also be of infinite size. We can take, for example, the set of all integers, Z. This includes the natural numbers (since they are the positive integers), as well as the negative integers and zero. Intuitively we can see that this must be a bigger set than N. Unfortunately, our intuition is wrong. When it comes to infinite sets, the only way to decide if Z is larger than N is to examine whether a bijection (one-to-one and onto function) exists between the two sets. If such a function can be found, then automatically the sets must have the same "size". Note that the natural numbers are essentially the numbers we count with, 1, 2, 3 and so on. So, finding a bijection between Z and N is the same as finding some way of listing all the elements of Z, without missing any, in a certain order. If such a sequence exists for Z, then Z and N have the same "size". This sequence is extremely easy to come up with: 0, 1, -1, 2, -2... and so on. Obviously this ordering will go through every single integer, much in the same way that 1, 2, 3... goes through every natural number.
The above shows us that Z has, in a sense, the same number of elements as N. Except that, as they both have infinitely many elements, we are not really talking about a number of elements. Because of this, the idea of cardinality was formulated. Cardinality can be thought of as the size of infinite sets, like the naturals or the integers. so, our example above shows that in fact both N and Z have the same cardinality, even if one is a subset of the other. This is a very important concept; infinity does not behave in the same way that other numbers do. Cutting infinity in half or doubling it does not actually change its size at all.
At this point one might think that all infinite sets must have the same cardinality as the natural numbers. After all, it should be easy to find a sequence that lists all the elements in a set. This is often the case; sets like the rational numbers, the algebraic numbers, the set of polynomials with integer coefficients and so on are certainly all countable (i.e. have the same cardinality as N). But there are sets which are actually much larger. The set of real numbers is actually uncountable. Any attempt to make a comprehensive list of all the reals, will result in failure. Indeed any such list can be shown to be missing some real numbers (in fact, an infinite amount of them). The proof for this uses a rather elegant method devised by Cantor, known as Cantor's diagonal argument.. I do not propose to present it here, as it is readily available online in other places. However, it should be clear from all this that the subject of cardinalities and the nature of infinity is one with a lot of substance.
Wednesday, July 25, 2012
Group Theory
This post will assume some fundamental knowledge of Set Theory, as well as Functional Analysis. Only the basic ideas, e.g. what a set is, what functions are, what a bijection is, and so on are required.
Ideally, I should have titled this post "Algebra", however I hesitate to do this, as there are many misconceptions about what algebra actually is. In middle-school people learn it informally as equations with letters replacing some of the numbers. In fact, algebra is the study of relations between mathematical objects.
A group G is a set which has a built-in binary function, F(x, y). This function takes two elements from the set and returns one element from the set. This property is known as closure and is one of the requirements for a group. The other properties a group must have, with respect to its binary function are:
1) An identity element. This is an element e for which F(e, x) = F(x, e) = x. Think of this as the number 0, when we add integers. 0 + x = x + 0 = x, for any integer x. Note that the identity element is unique.
2) Inverses. Every element of the set must also have an inverse in the set. Two elements a and b are inverses of each other if F(a, b) = F(b, a) = e, where e is the identity. This is similar to the negative of a number. When adding integers, x + (-x) = (-x) + x = 0. Note that each element has a unique inverse. This includes the identity, which is its own inverse.
3) Associativity. Using the addition example, this means that (a + b) + c = a + (b + c). That is, the order in which the additions are carried out does not matter; whereas the order of the elements added does.
The last part may seem strange, in light of the addition example. After all, 2 + 3 = 3 + 2 = 5. The order is irrelevant! This is, in fact, not the case, with more general groups. For example, if we take the set of 2x2 matrices with non-zero determinant, under normal matrix multiplication, they form a group. But in this group AB is not equal to BA. The order of the elements added (or multiplied) matters in many groups. The groups for which a + b = b + a are known as abelian groups; the integers under addition are such a group.
Having read all these rather abstract notions which define a group, one may ask what the point of Group Theory is. Why should it be a field of study, when it seems so disconnected from anything which can relate to the experience of our senses? In fact, the same question could be asked of most high-level fields of Mathematics, and the answer will roughly be the same. There are in fact three reasons to study Group Theory, or indeed any sort of Mathematics. The first is because of the applications they have. With Group Theory these may not be readily apparent, however modern Physics, Chemistry and Cryptography rely on the study of Group Theory. The second reason is that we humans have a natural curiosity and a tendency to look for patterns. In many ways, the study of Mathematics in general and Algebra in particular is the study of patterns. The third reason is that mathematical study helps one develop a rational way of thinking. Abstracting problems into mathematical models is the only way which has been discovered so far, which is consistently successful in solving said problems.
Ideally, I should have titled this post "Algebra", however I hesitate to do this, as there are many misconceptions about what algebra actually is. In middle-school people learn it informally as equations with letters replacing some of the numbers. In fact, algebra is the study of relations between mathematical objects.
A group G is a set which has a built-in binary function, F(x, y). This function takes two elements from the set and returns one element from the set. This property is known as closure and is one of the requirements for a group. The other properties a group must have, with respect to its binary function are:
1) An identity element. This is an element e for which F(e, x) = F(x, e) = x. Think of this as the number 0, when we add integers. 0 + x = x + 0 = x, for any integer x. Note that the identity element is unique.
2) Inverses. Every element of the set must also have an inverse in the set. Two elements a and b are inverses of each other if F(a, b) = F(b, a) = e, where e is the identity. This is similar to the negative of a number. When adding integers, x + (-x) = (-x) + x = 0. Note that each element has a unique inverse. This includes the identity, which is its own inverse.
3) Associativity. Using the addition example, this means that (a + b) + c = a + (b + c). That is, the order in which the additions are carried out does not matter; whereas the order of the elements added does.
The last part may seem strange, in light of the addition example. After all, 2 + 3 = 3 + 2 = 5. The order is irrelevant! This is, in fact, not the case, with more general groups. For example, if we take the set of 2x2 matrices with non-zero determinant, under normal matrix multiplication, they form a group. But in this group AB is not equal to BA. The order of the elements added (or multiplied) matters in many groups. The groups for which a + b = b + a are known as abelian groups; the integers under addition are such a group.
Having read all these rather abstract notions which define a group, one may ask what the point of Group Theory is. Why should it be a field of study, when it seems so disconnected from anything which can relate to the experience of our senses? In fact, the same question could be asked of most high-level fields of Mathematics, and the answer will roughly be the same. There are in fact three reasons to study Group Theory, or indeed any sort of Mathematics. The first is because of the applications they have. With Group Theory these may not be readily apparent, however modern Physics, Chemistry and Cryptography rely on the study of Group Theory. The second reason is that we humans have a natural curiosity and a tendency to look for patterns. In many ways, the study of Mathematics in general and Algebra in particular is the study of patterns. The third reason is that mathematical study helps one develop a rational way of thinking. Abstracting problems into mathematical models is the only way which has been discovered so far, which is consistently successful in solving said problems.