Join Peggy Fisher for an in-depth discussion in this video Event probability, part of Foundations of Programming: Discrete Mathematics.
- [Voiceover] Probability and discrete mathematics involves the probability of events using enumerative combinatorics. Discrete probability is the theory that deals with events that occur in countable spaces. For example, when observing nature, we might count the number of birds in a flock, which is comprised only of positive integers. For experiments that have very well-defined constraints, such as throwing dice or experiments with decks of cards, calculating the probability of events is basically, again, enumerative combinatorics.
When tossing or throwing a set of two die, what are the chances of getting two sixes? We start by identifying the power set of two die. Each die has a cardinality of six. So the total number of sets would be 36. There's only one combination that provides us with two sixes. So the probability is one out of 36, or about 3%. Let's extend this to the probability of getting two die that sum to seven.
First, we need to list the ordered pairs that add to seven. Which include one and six, two and five, three and four, four and three, five and two, and six and one. Remember, order is important when you're dealing with ordered pairs. Therefore, the probability would be six out of 36, or approximately 17%. Another type of experiment might be trying to identify all possible routes from one destination to another with one stop along the way.
When flying the friendly skies, the program used to find the routes must first identify all flights from destination A to destination B, and then B to C. Finally, what is the total possible flight patterns, and the cost of each? Suppose these three icons represent my flights, where A is State College, B is Chicago, and C is Dallas. We have three flights from State College to Chicago.
Three flights go from A to B. One. Two. And three. Now, each one of those flights can take one of four flights from Chicago onto Dallas. Flight one can take four different flights to get to Dallas. And the same is true for flight two and flight three. I'm going to abbreviate this by putting a "four" here in parentheses.
So, the total number of possible trips would be four, eight, nine, 10, 11, 12. So there's 12 variations. It was easy to visualize three flights, then four flights. But you can see, as this gets exponentially larger, it's going to be difficult. But what we can do is take the number of flights from A to B times the number of flights from B to C. And that will give us the total number of possible combinations. As you can see from these two examples, discrete math encompasses a portion of statistical probability.
In both examples, we saw a combination of set theory and number theory, which are the foundations of discrete mathematics.
This course relies on an open-source SML (standard machine language) library to demo the concepts behind discrete math. Peggy Fisher shows you how to manipulate sets of data, write proofs and truth tables, analyze data sequences, and visualize data using graph theory. Challenges at the end of every chapter allow you to test your knowledge. By the end of the course, you should be able to make the leap from theory to using discrete math in practice: saving time and resulting in code that's cleaner and easier to maintain in the long run.
- Real-world discrete math
- Objects as sets
- Set notation and operations
- Standard machine language (SML) setup
- Working with data types, strings, and functions in SML
- Analyzing data sequences
- Writing truth tables
- Identifying and evaluating predicates
- Validating arguments
- Writing proofs: subset, conditional, and biconditional proofs
- Visualizing data with graphs
- Advanced discrete math techniques