CS188.1x: Syllabus

1. FIND COURSES

1. cantoral
2. ▾

CS188.1x: Introduction to Artificial IntelligenceBerkeleyX

YOU ARE REGISTERED FOR THIS COURSE (CS188.1X)

overview

ABOUT THIS COURSE

CS188.1x is a new online adaptation of the first half of UC Berkeley’s CS188: Introduction to Artificial Intelligence. The on–campus version of this upper division computer science course draws about 600 Berkeley students each year.

Artificial intelligence is already all around you, from web search to video games. AI methods plan your driving directions, filter your spam, and focus your cameras on faces. AI lets you guide your phone with your voice and read foreign newspapers in English. Beyond today’s applications, AI is at the core of many new technologies that will shape our future. From self–driving cars to household robots, advancements in AI help transform science fiction into real systems.

CS188.1x focuses on Behavior from Computation. It will introduce the basic ideas and techniques underlying the design of intelligent computer systems. A specific emphasis will be on the statistical and decision–theoretic modeling paradigm. By the end of this course, you will have built autonomous agents that efficiently make decisions in stochastic and in adversarial settings. CS188.2x (to follow CS188.1x, precise date to be determined) will cover Reasoning and Learning. With this additional machinery your agents will be able to draw inferences in uncertain environments and optimize actions for arbitrary reward structures. Your machine learning algorithms will classify handwritten digits and photographs. The techniques you learn in CS188x apply to a wide variety of artificial intelligence problems and will serve as the foundation for further study in any application area you choose to pursue.

COURSE STAFF

Dan Klein

Dan Klein (PhD Stanford, MSt Oxford, BA Cornell) is an associate professor of computer science at the University of California, Berkeley. His research focuses on natural language processing and using computational methods to automatically acquire models of human languages. Examples include large–scale systems for language understanding, information extraction, and machine translation, as well as computational linguistics projects, such as the reconstruction of ancient languages. One of his best–known results was to show that human grammars can be learned by statistical methods. He also led the development of the Overmind, a galaxy–dominating, tournament–winning agent for the game of Starcraft. Academic honors include a Marshall Fellowship, a Microsoft Faculty Fellowship, a Sloan Fellowship, an NSF CAREER award, the ACM Grace Murray Hopper award for his work on grammar induction, and best paper awards at the ACL, NAACL, and EMNLP conferences.

Pieter Abbeel

Pieter Abbeel (PhD Stanford, MS/BS KU Leuven) joined the faculty of the Department of Electrical Engineering and Computer Sciences at UC Berkeley in 2008. He regularly teaches CS188: Introduction to Artificial Intelligence and CS287: Advanced Robotics. His research focuses on robot learning. Some results include machine learning algorithms which have enabled advanced helicopter aerobatics, including maneuvers such as tic–tocs, chaos and auto–rotation, which only exceptional human pilots can perform, and the first end–to–end completion of reliably picking up a crumpled laundry article and folding it. Academic honors include best paper awards at ICML and ICRA, the Sloan Fellowship, the Air Force Office of Scientific Research Young Investigator Program (AFOSR–YIP) award, the Okawa Foundation award, the MIT TR35, the IEEE Robotics and Automation Society (RAS) Early Career Award, and the Dick Volz award for best PhD thesis in robotics and automation.

SYLLABUS

• Introduction
• Overview
• Agents: Perception, Decisions, and Actuation
• Search and Planning
• Uninformed Search (Depth-First, Breadth-First, Uniform-Cost)
• Informed Search (A*, Greedy Search)
• Heuristics and Optimality
• Constraint Satisfaction Problems
• Backtracking Search
• Constraint Propagation (Arc Consistency)
• Exploiting Graph Structure
• Game Trees and Tree-Structured Computation
• Minimax, Expectimax, Combinations
• Evaluation Functions and Approximations
• Alpha-Beta Pruning
• Decision Theory
• Preferences, Rationality, and Utilities
• Maximum Expected Utility
• Markov Decision Processes
• Policies, Rewards, and Values
• Value Iteration
• Policy Iteration
• Reinforcement Learning
• TD/Q Learning
• Exploration
• Approximation

PREREQUISITES

• Programming
• Object-Oriented Programming
• Recursion
• Python or ability to learn Python quickly (mini-tutorial provided)
• Data Structures
• Lists vs Sets (Arrays, Hashtables)
• Queuing (Stacks, Queues, Priority Queues)
• Trees vs Graphs (Traversal, Backpointers)
• Math
• Probability, Random Variables, and Expectations (Discrete)
• Basic Asymptotic Complexity (Big-O)
• Basic Counting (Combinations and Permutations)

Share with friends and family!

  

1. Course Number
   CS188.1x
2. Classes Start
   Sep 24, 2012
3. Classes End
   Nov 16, 2012
4. Estimated Effort
   15 hours/week
5. Prerequisites
   Yes

 Find Courses About Blog Jobs Contact

   

© 2012 edX, some rights reserved.

terms of service privacy policy honor code help

Conclusiones de la Tarea

Algunas variables son mudas, esto es, se pueden cambiar en todo el programa, y éste sigue haciendo lo mismo.

Ejemplo: Todas las que están entre tres comillas dobles ("""), o con un símbolo de gato #. Estos cambian de color, entre tres comillas dobles son verdes, y con gato son rojas.

Ejemplo: Hay otras que eran negras, y al cambiarlas, no pasó nada. por ejemplo name, pusimos nombre en todos lados donde estaba name, y dio lo mismo.

Nc

Este valor indica cuantos mostradores, o cajas hay. Se asocia a la variable resource, que quiere decir recurso. Entre más grande sea Nc, salen más rápido los clientes, y no se puede cambiar arbitrariamente, es necesario cambiar el programa, si ponemos Nc mayor.

Es necesario cambiar los programas, para entenderlos. Hay que seguir cambiándolos. Suponer qué va a pasar, y verificar que pasa. Por ejemplo, cuando se reduce Nc de 2 a 1, los clientes se tardaron más, porque hay menos cajeras en los mostradores para atender a los clientes.

El estudio de cómo asignar recursos para dar servicio, se llama Logística, y es lo que se estudia con esta modelación de un banco.

Tarea

Copiar todos los programas en el directorio que están, cambiándoles el nombre. Usar Save us, con un nuevo nombre, 001, etc.. Correr las copias y ver que hacen lo mismo. Cambiar partes del programa, y ver qué sucede, así entendemos mejor los programas.

Presentar un reporte en el blog de las conclusiones.

Esta tarea la hacemos para aprender más.

Así puede uno estudiar solo, sin necesidad de preguntarle al maestro. Si el programa no funciona es por error en el cambio que hicimos. Si sí funciona, y además produce lo que esperábamos, es porque entendemos el programa.

Resumen de los 24 Programas de SimPy

El primero tiene un sólo cliente, el segundo tiene más. El primero es determinado (no - azar), ya después son al azar. Random es azar, así como en La Lotería. Los tiempos que los clientes están en el banco, se distribuyen al azar, según una ley exponencial.

Así pues el tutorial va de lo sencillo, e.g. un cliente, a lo complicado, muchos clientes.Con más clientes puede haber interacción. Guido es un cliente distinguido, se refieren a Guido von Rossum.

SimPy ejecutable

Liga

pythonxy2.7.2.1

pythonxy2.7.2.0

Varias versiones aquí.

Tarea

Buscar los programas del tutorial del banco en su computadora.
En mi Ubuntu están en:
/usr/eduardo/Downloads/SimPy-2.2/docs/examples/BankTutorialModels

Solución de mi tarea:

Tarea

Leer bank01.py, y hacer un resumen en el blog.

Tarea

Abrir una sesion de Python, ejecutar algunas operaciones, e imprimir la pantalla. Publicar la foto en su blog.

Por ejemplo:

from math import *

Ejemplo

random()

Help(Random)

Python 3.1.2 (r312:79147, Sep 27 2010, 09:45:41) 
[GCC 4.4.3] on linux2
Type "copyright", "credits" or "license()" for more information.
==== No Subprocess ====
>>> from random import Random
>>> help(Random)
Help on class Random in module random:

class Random(_random.Random)
 |  Random number generator base class used by bound module functions.
 |  
 |  Used to instantiate instances of Random to get generators that don't
 |  share state.
 |  
 |  Class Random can also be subclassed if you want to use a different basic
 |  generator of your own devising: in that case, override the following
 |  methods:  random(), seed(), getstate(), and setstate().
 |  Optionally, implement a getrandbits() method so that randrange()
 |  can cover arbitrarily large ranges.
 |  
 |  Method resolution order:
 |      Random
 |      _random.Random
 |      builtins.object
 |  
 |  Methods defined here:
 |  
 |  __getstate__(self)
 |  
 |  __init__(self, x=None)
 |      Initialize an instance.
 |      
 |      Optional argument x controls seeding, as for Random.seed().
 |  
 |  __reduce__(self)
 |  
 |  __setstate__(self, state)
 |  
 |  betavariate(self, alpha, beta)
 |      Beta distribution.
 |      
 |      Conditions on the parameters are alpha > 0 and beta > 0.
 |      Returned values range between 0 and 1.
 |  
 |  choice(self, seq)
 |      Choose a random element from a non-empty sequence.
 |  
 |  expovariate(self, lambd)
 |      Exponential distribution.
 |      
 |      lambd is 1.0 divided by the desired mean.  It should be
 |      nonzero.  (The parameter would be called "lambda", but that is
 |      a reserved word in Python.)  Returned values range from 0 to
 |      positive infinity if lambd is positive, and from negative
 |      infinity to 0 if lambd is negative.
 |  
 |  gammavariate(self, alpha, beta)
 |      Gamma distribution.  Not the gamma function!
 |      
 |      Conditions on the parameters are alpha > 0 and beta > 0.
 |  
 |  gauss(self, mu, sigma)
 |      Gaussian distribution.
 |      
 |      mu is the mean, and sigma is the standard deviation.  This is
 |      slightly faster than the normalvariate() function.
 |      
 |      Not thread-safe without a lock around calls.
 |  
 |  getstate(self)
 |      Return internal state; can be passed to setstate() later.
 |  
 |  lognormvariate(self, mu, sigma)
 |      Log normal distribution.
 |      
 |      If you take the natural logarithm of this distribution, you'll get a
 |      normal distribution with mean mu and standard deviation sigma.
 |      mu can have any value, and sigma must be greater than zero.
 |  
 |  normalvariate(self, mu, sigma)
 |      Normal distribution.
 |      
 |      mu is the mean, and sigma is the standard deviation.
 |  
 |  paretovariate(self, alpha)
 |      Pareto distribution.  alpha is the shape parameter.
 |  
 |  randint(self, a, b)
 |      Return random integer in range [a, b], including both end points.
 |  
 |  randrange(self, start, stop=None, step=1, int=, default=None, maxwidth=9007199254740992)
 |      Choose a random item from range(start, stop[, step]).
 |      
 |      This fixes the problem with randint() which includes the
 |      endpoint; in Python this is usually not what you want.
 |      Do not supply the 'int', 'default', and 'maxwidth' arguments.
 |  
 |  sample(self, population, k)
 |      Chooses k unique random elements from a population sequence or set.
 |      
 |      Returns a new list containing elements from the population while
 |      leaving the original population unchanged.  The resulting list is
 |      in selection order so that all sub-slices will also be valid random
 |      samples.  This allows raffle winners (the sample) to be partitioned
 |      into grand prize and second place winners (the subslices).
 |      
 |      Members of the population need not be hashable or unique.  If the
 |      population contains repeats, then each occurrence is a possible
 |      selection in the sample.
 |      
 |      To choose a sample in a range of integers, use range as an argument.
 |      This is especially fast and space efficient for sampling from a
 |      large population:   sample(range(10000000), 60)
 |  
 |  seed(self, a=None)
 |      Initialize internal state from hashable object.
 |      
 |      None or no argument seeds from current time or from an operating
 |      system specific randomness source if available.
 |      
 |      If a is not None or an int, hash(a) is used instead.
 |  
 |  setstate(self, state)
 |      Restore internal state from object returned by getstate().
 |  
 |  shuffle(self, x, random=None, int=)
 |      x, random=random.random -> shuffle list x in place; return None.
 |      
 |      Optional arg random is a 0-argument function returning a random
 |      float in [0.0, 1.0); by default, the standard random.random.
 |  
 |  triangular(self, low=0.0, high=1.0, mode=None)
 |      Triangular distribution.
 |      
 |      Continuous distribution bounded by given lower and upper limits,
 |      and having a given mode value in-between.
 |      
 |      http://en.wikipedia.org/wiki/Triangular_distribution
 |  
 |  uniform(self, a, b)
 |      Get a random number in the range [a, b) or [a, b] depending on rounding.
 |  
 |  vonmisesvariate(self, mu, kappa)
 |      Circular data distribution.
 |      
 |      mu is the mean angle, expressed in radians between 0 and 2*pi, and
 |      kappa is the concentration parameter, which must be greater than or
 |      equal to zero.  If kappa is equal to zero, this distribution reduces
 |      to a uniform random angle over the range 0 to 2*pi.
 |  
 |  weibullvariate(self, alpha, beta)
 |      Weibull distribution.
 |      
 |      alpha is the scale parameter and beta is the shape parameter.
 |  
 |  ----------------------------------------------------------------------
 |  Data descriptors defined here:
 |  
 |  __dict__
 |      dictionary for instance variables (if defined)
 |  
 |  __weakref__
 |      list of weak references to the object (if defined)
 |  
 |  ----------------------------------------------------------------------
 |  Data and other attributes defined here:
 |  
 |  VERSION = 3
 |  
 |  ----------------------------------------------------------------------
 |  Methods inherited from _random.Random:
 |  
 |  __getattribute__(...)
 |      x.__getattribute__('name') <==> x.name
 |  
 |  getrandbits(...)
 |      getrandbits(k) -> x.  Generates a long int with k random bits.
 |  
 |  random(...)
 |      random() -> x in the interval [0, 1).
 |  
 |  ----------------------------------------------------------------------
 |  Data and other attributes inherited from _random.Random:
 |  
 |  __new__ = 
 |      T.__new__(S, ...) -> a new object with type S, a subtype of T

>>> 

Tarea

Genere un número al azar en Python. Usando el modulo random.

Tarea

Correr el programa del Banco en su computadora.

SimPy-2.3b1

SimPy
=====

SimPy is a process-based discrete-event simulation language based on standard
Python and released under the GNU LGPL.

It provides the modeller with components of a simulation model. These include
processes for active components like customers, messages and vehicles as well
as  resources for passive components that form limited capacity congestion
points (like servers, checkout counters and tunnels). It also provides monitor
variables to aid in gathering statistics. SimPy comes with extensive plotting
capabilities.

The distribution contains in-depth documentation, tutorials, and a large number
of simulation models.

Simulation model developers are encouraged to share their SimPy modeling
techniques with the SimPy community. Please post a message to the SimPy-Users
mailing list: http://lists.sourceforge.net/lists/listinfo/simpy-users

Software developers are also encouraged to interface SimPy with other Python-
accessible packages, such as GUI, database or mapping and to share these new
capabilities with the community under the GNU LGPL.


Installation
------------

SimPy requires Python 2.3 or above. Python 3 is not yet supported, but we are
working on it.

You can install SimPy easily via `PIP `_
(or ``easy_install``)::

    $ pip install SimPy
    $ # or:
    $ easy_install SimPy

You can also download and install SimPy manually::

    $ cd where/you/put/simpy/
    $ python setup.py install


If you want to upgrade an existing installation of SimPy, just add the ``-U``
option to *pip* or *easy_install*, e.g.::

    $ pip install -U SimPy


Getting started
---------------

Run one or more of the programs under *docs/examples/* to see whether Python
finds the SimPy module. If you get an error message like *ImportError: No
module named SimPy*, check if the SimPy packages exists in your site-packages
folder (like /Lib/site-packages).

The tutorial and manuals are in the *docs/html* folder. Many users have
commented that the Bank tutorials are valuable in getting users started on
building their own simple models. Even a few lines of Python and SimPy can
model significant real systems.

For more help, contact the `SimPy-Users mailing list
`_. SimPy users are pretty helpful.

Enjoy simulation programming in SimPy!

Autores de SimPy

SimPy was originally created by Klaus G. Müller and Tony Vignaux in 2002.

In 2008, Ontje Lünsdorf and Stefan Scherfke started to contribute to SimPy and
became active maintainers in 2011.

In 2011, Karen Turner came on board to generally help with all the bits and
pieces that may get forgotten :-)

We’d also like to thank:

- Johannes Koomer for a fix for Store._put.

Tarea

Del programa del Banco, escribir dudas en su blog.

Tarea

Escribir en el blog un resumen del ejercicio del banco que viene en las notas de la Universidad de Venezuela. Lean las notas [liga]

bank.py

#!/usr/bin python
""" bank11: Simulate customers arriving
    at random, using a Source, requesting service
    from two counters each with their own queue
    random servicetime.
    Uses a Monitor object to record waiting times

"""
from __future__ import generators   #(not needed in Python 2.3+)
from SimPy.Simulation  import *
from random import Random

class Source(Process):
    """ Source generates customers randomly"""
    def __init__(self,seed=333):
        Process.__init__(self)
        self.SEED = seed

    def generate(self,number,interval):       
        rv = Random(self.SEED)
        for i in range(number):
            c = Customer(name = "Customer%02d"%(i,))
            activate(c,c.visit(timeInBank=12.0))
            t = rv.expovariate(1.0/interval)
            yield hold,self,t

def NoInSystem(R):
    """ The number of customers in the resource R
    in waitQ and active Q"""
    return (len(R.waitQ)+len(R.activeQ))

class Customer(Process):
    """ Customer arrives, is served and leaves """
    def __init__(self,name):
        Process.__init__(self)
        self.name = name
        
    def visit(self,timeInBank=0):       
        arrive=now()
        Qlength = [NoInSystem(counter[i]) for i in range(Nc)]
        for i in range(Nc):
            if Qlength[i] ==0 or Qlength[i]==min(Qlength): join =i ; break
        yield request,self,counter[join]
        wait=now()-arrive
        waitMonitor.observe(wait)                                 
        tib = counterRV.expovariate(1.0/timeInBank)
        yield hold,self,tib
        yield release,self,counter[join]

def model(counterseed=393939):
    global Nc,counter,counterRV,waitMonitor                      
    Nc = 2
    counter = [Resource(name="Clerk0"),Resource(name="Clerk1")]
    counterRV = Random(counterseed)
    waitMonitor = Monitor()                                      
    initialize()
    sourceseed = 99999
    source = Source(seed = sourceseed)
    activate(source,source.generate(50,10.0),0.0)                
    simulate(until=2000.0)                                       
    return (waitMonitor.count(),waitMonitor.mean())              

result = model(393939)                                           
print ("Average wait for %4d was %6.2f"% result )                 

Tarea

Instalar Simpy en Windows y Ubuntu.

Bank11: A simple example using monitor.

#!/usr/bin python
""" bank11: Simulate customers arriving
at random, using a Source, requesting service
from two counters each with their own queue
random servicetime.
Uses a Monitor object to record waiting times
"""
from __future__ import generators #(not needed in Python 2.3+)
from SimPy.Simulation import *
from random import Random
class Source(Process):
""" Source generates customers randomly"""
def __init__(self,seed=333):
Process.__init__(self)
self.SEED = seed
def generate(self,number,interval):
rv = Random(self.SEED)
for i in range(number):
c = Customer(name = "Customer%02d"%(i,))
activate(c,c.visit(timeInBank=12.0))
t = rv.expovariate(1.0/interval)
yield hold,self,t
def NoInSystem(R):
""" The number of customers in the resource R
in waitQ and active Q"""
return (len(R.waitQ)+len(R.activeQ))
class Customer(Process):
""" Customer arrives, is served and leaves """
def __init__(self,name):
Process.__init__(self)
self.name = name
def visit(self,timeInBank=0):
arrive=now()
Qlength = [NoInSystem(counter[i]) for i in range(Nc)]
for i in range(Nc):
if Qlength[i] ==0 or Qlength[i]==min(Qlength): join =i ; break
yield request,self,counter[join]
wait=now()-arrive
waitMonitor.observe(wait)
tib = counterRV.expovariate(1.0/timeInBank)
yield hold,self,tib
yield release,self,counter[join]
def model(counterseed=393939):
global Nc,counter,counterRV,waitMonitor
Nc = 2
counter = [Resource(name="Clerk0"),Resource(name="Clerk1")]
counterRV = Random(counterseed)
waitMonitor = Monitor()
initialize()
sourceseed = 99999
source = Source(seed = sourceseed)
activate(source,source.generate(50,10.0),0.0)
simulate(until=2000.0)
return (waitMonitor.count(),waitMonitor.mean())
result = model(393939)
print ("Average wait for %4d was %6.2f")% result
Tomado de SimPy