6.01, Fall Semester, 2007—Assignment 2 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.01—Introduction to EECS IFall Semester, 2007Assignment 2Issued: Tuesday, Sept. 11This handout contains:• Software Lab for Tuesday, September 11• Pre-Lab exercises to do before Thursday, September 13 at 10AM; you can come and do themin lab on Wednesday, September 12. Don’t forget that Part 2.2 of the on-line Tutor problemsare also due before Thursday lab.• Robot Lab for Thursday, September 13 (read the lab before coming to 34-501)• Post-lab writeup and exercises due Tuesday, September 18 at 10AM. Don’t forget that Part 2.3and 2.4 of the on-line Tutor problems are also due before Tuesday lecture.Higher-order procedures; Behaviors and utility functionsThis week’s work gives you practice with higher-order procedures, i.e., procedures that manipulateother procedures. Tuesday’s lecture, the post-class software lab, and the on-line problems, coverPython’s support for functional programming. Thursday’s lab applies higher-order procedures tothe tasks of specifying robot behaviors with the aid of utility functions.Make sure you do:athrun 6.01 updateso that you can get the Desktop/6.01/lab2 directory which has the files mentioned in thishandout.6.01, Fall Semester, 2007—Assignment 2 2Tuesday Software Lab: Higher-order proceduresAt the end of this lab, go to the on-line Tutor at http://sicp.csail.mit.edu/6.01/fall07, choose PS2, and paste all your code, including your test cases, into the box providedin the “Software Lab” problem.This session gives you practice with Python’s basic tools for functional programming: higher-orderprocedures and list comprehension.A higher-order procedure is a procedure that takes procedures as inputs and/or returns proceduresas results. We will be working with a simple model of probability spaces, one that we will use laterin the course.ProbabilityProbability theory is a calculus that allows us to assign numerical assessments of uncertainty topossible events, and then do calculations with the numerical assessments in a way that preservestheir meaning. (A similar system that you might be more familiar with is algebra: you start withsome facts that you know, and the axioms of algebra allow certain manipulations that will preservetruth.)We’ll just consider worlds that can be represented by the values of a small number of discretevariables. We’ll let U be the universe (or sample space), which is a set of atomic events. An atomicevent is just an outcome or a way the world could be. The universe associated with rolling a normaldie once can be written asU = {1, 2, 3, 4, 5, 6} .The universe associated with rolling two dice, or one die twice, can be written asU = {(1, 1), (1, 2), ..., (1, 6), ..., (6, 5), (6, 6)} .Atomic events could indicate which room a robot is in and whether the battery is charged, or anydescription of the world under consideration, but we are assuming that there are a finite numberof possible combinations of values, so that the universe is finite.An event is a subset of U. For example the set of atomic events in which the single die roll resultis greater than 3 is an event. A probability measure P is a mapping from events to numbers thatsatisfy the following axioms:P (U) = 1P ({}) = 0P (A ∪ B) = P (A) + P (B) − P (A ∩ B)Or, in English:• The probability that something will happen is 1.• The probability that nothing will happen is 0.• The probability that an atomic event in the set A or an atomic event in the set B will happenis the probability that an atomic event of A will happen plus the probability that an atomicevent of B will happen, minus the probability that an atomic event that is in both A and Bwill happen (because those events effectively got counted twice in the sum of P (A) and P (B)).6.01, Fall Semester, 2007—Assignment 2 3Armed with these axioms, we are prepared to do anything that can be done with discrete probability!For example, consider the universe associated with rolling two fair dice (shown above); each of theatomic events is equiprobable. So, each event has probability 1/36.• The probability of rolling a pair of twos is: P (Die1 = 2 ∩ Die2 = 2) = 1/36• The probability that the first die is a 2 is: P (Die1 = 2) = 1/6, the sum of 6 atomic events.• The probability of one of the dice coming up 2 isP (Die1 = 2∪Die2 = 2) = P (Die1 = 2)+P (Die2 = 2)−P (Die1∩Die2) = 1/6+1/6−1/36 ,note that the (2, 2) atomic event is included in both events “Die1 = 2” and “Die2 = 2”.One more important idea is conditional probability, where we ask the probability of some event E1,assuming that some other event E2is true; we do this by restricting our attention to the part ofthe sample space (universe) in E2. The conditional probability is the amount of the sample spacethat is both in E1and E2, divided by the amount in E2:P (E1|E2) =P (E1∩ E2)P (E2).That is, the fraction of the E2probability that is also in E1.The expression P (E1|E2) is read as: the conditional probability of E1given E2or, more loosely,the probability of E1given E2. The expression P(E1∩ E2) is read as: the probability of E1andE2.Manipulating Probability SpacesWe’re going to build Python models of discrete probability spaces, that is, sample spaces withcorresponding probability measures. Concretely, we’ll represent a probability space as a list ofatomic events, each with its assigned probability. Each element of the probability space, whichwe will call a sample (sometimes also known as an outcome) will be a list with two elements: aprobability and the value that defines an atomic event. For example, to represent the probabilityspace for a standard, six-sided die we can have:dieSpace = [ [1.0/6 , 1] , [1.0/6 , 2] , [1.0/6 , 3] ,[1.0/6 , 4] , [1.0/6 , 5] , [1.0/6 , 6] ]The atomic events don’t have to be equiprobable. We can also model a loaded die:load edDie S pace = [ [1.0/10 , 1] , [1.0/10 , 2] , [1.0/10 , 3] ,[1.0/10 , 4] , [1.0/10 , 5] , [1.0/2 , 6] ]It is essential that the probabilities of all of the samples add up to 1.0, as required by the axioms.The value used to define an atomic sample could be more complicated, e.g. another list. Forexample, if we wanted to represent the probability space for the roll of two fair dice, we could have:diceSpace = [ [1.0/36 , [1 , 1]] , [1.0/36 , [1 , 2]] , [1.0/36 , [1 , 3]] ,... , [1.0/36 , [6 , 6]] ]6.01, Fall Semester,
View Full Document
Unlocking...