Discrete Math Concepts

I’m taking a test tomorrow, so I’m going to use this post to help me study. So this post isn’t so much what I have been thinking about all week (I’ve been out of town for a wedding), it’s what I should have been thinking about this week. It’s also an experiment in talking about math and technology using words (If you find math boring, feel free to read someone else’s blog). I’m taking a class called Discrete Math, most people don’t know what this is (I didn’t either, before I took the class). Discrete Math is a requirement for most Computer Science students, it’s a jumble of math concepts that apply to computers including Logic, Algorithms, Set-Theory, Graph Theory, Combinatorics and Number Theory (here’s a video intro if you’re curious). It’s not discreet meaning hidden or restrained, it’s discrete; meaning distinct and separate. Discrete math deals with numbers that you can count, as opposed to Calculus which deals with infinity and continuity. It’s my understanding that computer’s can’t deal with infinity, they will just count and count until they run out of memory or power. They can count pretty high, but they’ll never get to infinity.

I’m almost done with the course so I can share some of the things I’ve learned and how (I think) they apply to Comp Sci. First we went over some basic logic, we thought about how to convert English sentences and arguments into logical symbols, how to test the validity of an argument and also how to use truth tables. How to convert spoken language into symbols is helpful, but to me the clearest application of logic to computer science is the use of truth tables. Truth tables are manipulations of true (T) and false (F) values, if you substitute 1 and 0 for T and F, you have classic binary values that computers can read. A bit is a boolean string of length 1, it just tells you whether something is true or false, on or off, black or white.

Next we studied basic sets, and equivalence relations. Sets are essentially primitive databases, in fact, a csv file, that you can open in excel, is just a set of numbers or strings (csv stands for comma separated values). Proofs and relations help us to define exactly what is in a set and how sets relate to each other. These laws determine how to manipulate data; a lot of it has to do with what things we consider to be equivalent. It’s really important for computers to know whether something is the same or not. Things that are the same can be grouped with other equivalent things, they related to themselves (reflexive) and others in a certain way (symmetric and transitive). Equivalences set the parameters for a computer’s sense of discretion, it helps computers to discern and judge like things from unlike things. To me, this is what makes computers ‘smart’, the fact that they can distinguish one kind from another (maybe someday they’ll be able to tell good from bad, right from wrong).

In the second unit we looked at sequences, sums, induction, algorithms, and number theory. Here we took a basic look at the different ways to tell computers what to do, and how effective they are. For a set you can input each entry separately, or you can populate an entire dataset by defining a function, and saying everything in that sequence is in the set. There are two main ways of defining sequences, you can define the first term and have a rule from there (recursive), or you can define it abstractly (closed set). Mathematical induction is a type of proof that uses the same idea as a recursive set; it says if you can prove the first idea and then say that the second idea is implied by the first idea everything else falls into place. I understand this in theory, but I had a lot of trouble with this in practice, it tends to use a lot of algebra I haven’t used in a while.

Next we looked at algorithms. My teacher says ‘Algorithms are a recipe to solve a problem,’ an algorithm is a series of steps which when followed will solve a certain type of problem. For example we looked at the Euclidean Algorithm to solve Greatest Common Factor problems. To apply the concept of algorithms to my programming class an algorithm is like pseudocode. One way to write a program is to start with pseudocode, it’s like a very detailed outline. You write out a line of code saying, for example, “if a < b, switch b and a". The code in JAVA would look something like if (a < b) { a=b; b=a;} In another programming language it would look different, but the algorithm or pseudocode could be the same. In number theory we looked at how integers interact with each other, the Rules of Arithmetic (addition and multiplication are closed, commutative, associative, have identity, inverse and multiplication distributes; there is an ordering relation and a divides relation). Using these rules we are able to find primes and come up with a division algorithm. These types of rules would be very helpful if you were trying to build a calculator, and what is a computer but a giant calculator?. My test is on the second unit so I'll have to go over some induction examples, and also memorize the formulas for recursive sequences and the rules of arithmetic. p.s. As if it didn't take me long enough to learn how to spell rhythm, now I have to learn algorithm?

Leave a Reply

Your email address will not be published. Required fields are marked *