Courses:

Engineering and Applied Sciences >> Computer Science


For Course Instructors

  • Advertise your course for free
  • Feature your course listing
  • Create course discussion group
  • Link to your course page
  • Increase student enrollment

More Info...>>


Course Info

  • Course Number / Code:
  • 18.400J (Spring 2005) 
  • Course Title:
  • Automata, Computability, and Complexity 
  • Course Level:
  • Undergraduate 
  • Offered by :
  • Massachusetts Institute of Technology (MIT)
    Massachusetts, United States  
  • Department:
  • Electrical Engineering and Computer Science 
  • Course Instructor(s):
  • Prof. Nancy Lynch 
  • Course Introduction:
  •  


  • 6.045J / 18.400J Automata, Computability, and Complexity



    Spring 2005




    Course Highlights


    This course features a full set of homework assignments. In addition, the recitation section includes many practice problems. 6.045J is a course in the department's "Theoretical Computer Science" concentration.


    Course Description


    This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. The course is slower paced than 6.840J/18.404J. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems.

    *Some translations represent previous versions of courses.

     

ACKNOWLEDGEMENT:
This course content is a redistribution of MIT Open Courses. Access to the course materials is free to all users.






© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.