5
$\begingroup$

Can anyone point me in the direction of good introductory material on the use of mathematical notation in the field of computer science? I often come across notation in research papers that I don't understand and I would like to at least have an overview of its meaning/intent, if not a thorough understanding. I don't have much of a mathematical background and don't expect to become an expert in this field overnight but any ideas would be appreciated.

UPDATE: The kind of notation I've been having trouble with can be seen on page three of this article. Note: this isn't an article I've been using for research, it's just the first publicly available example I came across!

$\endgroup$
5
  • 4
    $\begingroup$ There's lots of different mathematical notation used in computer science literature. Are you reading about a specific topic? Or better yet, can you link so some of the papers you're having trouble deciphering? $\endgroup$
    – axblount
    Aug 24, 2012 at 13:26
  • 1
    $\begingroup$ There is no single piece of notation that is used in Computer Science, and it is also unlikely that you will find it all in one place. Depending on the subject area you are looking at, you would need to find perhaps a graduate text book on the subject to get all the background you need. $\endgroup$
    – Uday Reddy
    Aug 24, 2012 at 13:51
  • $\begingroup$ Thanks both. I've updated the question accordingly. My course is pretty broad - covering networking, programming, e-commerce and more - but at a pretty high level so I often come across things where I need to have a basic understanding without having to get the maths. $\endgroup$
    – Willl
    Aug 24, 2012 at 14:15
  • 1
    $\begingroup$ but at a pretty high level so I often come across things where I need to have a basic understanding without having to get the maths - I think you'll always be missing (smaller or larger) parts, if you don't know the (often long) story behind a concept. $\endgroup$
    – miku
    Aug 24, 2012 at 22:13
  • $\begingroup$ Do you have problem with later pages than three? Because for them, you should become familiar with the probabilistic language, for that case, I can say a few words. $\endgroup$
    – user48547
    Jan 10, 2013 at 18:18

5 Answers 5

6
+50
$\begingroup$

That's set theory. I honestly recommend that you study set theory, as nowdays all mathematics are built on sets. Just pick any introductory book to set theory, that ill be (imo) enough.

Now, what you may having difficulties with, is the interpretation of those things, let's take an example from that page:

Given the set of N observations Y = {yi ; i = 1, . . . , N } we want to identify which observations belong to the same object.

This basically mean that $Y$ is a set containing observations, more simple (not so formal) translation could be: "We have a bunch of observations".

We are looking for a partition ω of observations from Y into several trajectories Yk ⊂ Y (subsets of Y ) such that each trajectory collects observations believed to come from a single person.

This now means that $\omega$ (defined in the next parragraph) is a partition from a space of partitions, and you're looking for subsets, that they call $Y_k$ that is believed to belong to the same person. Now the translation: "We are looking for observations that we believe belong to the same person, and we are going to separate the observations that belong to every person in different groups (sets)".

A valid partition expresses the set of all observations as an exhaustive union of trajectories: Y = Y1 ∪ . . . ∪ YKω , where Kω is the number of objects proposed by a partition ω. The trajectories must be mutually exclusive: Y ∩ Yk = ∅, when = k.

And last, they say a valid $\omega$ must have trajectories that contain (alltogether) the initial set $Y$, and that this trayectories' intersection must be empty. The translation: "The partition must have all subsets of observations, that means we must have formed groups that cover all observations, and two different subsets of observations cannot share a member, that would be obviously absurd, if we had two belonging to person A, and another two belonging to person B, and one of those two was repeated, then A and B would be the same person"

That goes on for the whole article. The final parragraph means:

We have a bunch of observations. We are looking for observations that we believe belong to the same person, and we are going to separate the observations that belong to every person in different groups (sets), that separation is called "partition". The partition must have all subsets of observations, that means we must have formed groups that cover all observations, and two different subsets of observations cannot share a member, that would be obviously absurd, if we had two belonging to person A, and another two belonging to person B, and one of those two was repeated, then A and B would be the same person.

This notation is used because it doesn't let space for ambiguity, and is more rigouruos, so besides studying set theory, which is basic, you should train you interpretation of these articles (just read more and try to do what I've done here)

BTW, I don't think there's any book about mathematical notation for computer science (it would really surprise me), because such thing doesn't exist, that's just mathematical/formal notation.

$\endgroup$
1
  • $\begingroup$ Thanks for substantial, detailed answer. Really useful points on the notation itself and the wider use of mathematical notation in academic papers and computer science. $\endgroup$
    – Willl
    Jan 11, 2013 at 9:25
2
$\begingroup$

It looks like the notation you've referenced is from set theory. I know the first chapters of this book discuss set theory somewhat. It's a free reference, so it doesn't cost anything but time to look at...

I haven't formally covered set theory yet in my curriculum, so I don't know of any other books to suggest... Perhaps look in your discrete math book?

$\endgroup$
2
$\begingroup$

The notation from the article you linked to is entirely from set theory. Any textbook from a discrete mathematics course should cover these notations and concepts reasonably well. "Discrete Mathematics with Applications" by Susana Epp was a good introduction and seems to be used a lot in computer science departments.

If you need to improve your background in mathematics for computer science, then I strongly recommend reading and working through Knuth's "The Art of Computer Programming" books.

$\endgroup$
2
$\begingroup$

Look at chapter one of this book, "Schaum's Outline of Set Theory and Related Topics". It's a short chapter and should cover all the notion on that page. You can also quickly look at this book, "Schaum's Outline of Probability, Random Variables, and Random Processes". Chapter one of this book has both the set theory notation, and the probability notation at the bottom of the page. They are both very simple books, without a lot of explanation, so it shouldn't take you very long to familiarize yourself with just the notation.

More broadly, the paper you provided looks like machine learning, a good introductory book is "Machine Learning: A Probabilistic Perspective". A review of probability starts on page 28. There is section called 'Notation' at the end of the book which lists some general machine learning notation.

$\endgroup$
1
$\begingroup$

I have used this Theoretical Computer Science Cheat Sheet to answer most of my questions.

$\endgroup$
2
  • $\begingroup$ Can you recreated in a format that is not postscript? $\endgroup$ Feb 15, 2015 at 11:55
  • 1
    $\begingroup$ @CMCDragonkai, My work-around was taking the .ps file to a print shop, where they printed and laminated for me. $\endgroup$ Feb 15, 2015 at 13:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .