martes, 25 de diciembre de 2012

Teoría de la Computación - NPTEL

NPTEL >> Courses
NPTEL is an acronym for National Programme on Technology Enhanced Learning which is an initiative by seven Indian Institutes of Technology (IIT Bombay, Delhi, Guwahati, Kanpur, Kharagpur, Madras and Roorkee) and Indian Institute of Science (IISc) for creating course contents in engineering and science.

COURSE OUTLINE

The objective of the course is to provide an exposition first to the notion of computability, then to the notion of computational feasibility or tractability.
We first convince ourselves that for our purpose it suffices to consider only language recognition problems instead of general computational problems.
We then provide a thorough account of finite state automata and regular languages, not only because these capture the simplest language class of interest and are useful in many diverse domains.
But also because many fundamental notions like nondeterminism, proofs of impossibility, etc. get discussed at a conceptually very simple level. We then consider context grammars and languages, and their properties.
Next, we consider Turing machines (TMs), show that as a model it is very robust, and the reasonableness of the Church-Turing hypothesis. After we realize TMs can work with (codes of) TMs as inputs, we obtain a universal TM.
We then obtain the separation of the classes r.e., and recursive. A number of TM related problems are shown to be undecidable. Next,Post’s correspondence problem (PCP) is shown undecidable.
Finally, we introduce the notion of feasible or tractable computation. Classes NP, co-NP are defined and we discuss why these are important. We discuss the extended Church-Turing hypothesis.
After we discuss polynomial time many-one reducibility and prove Cook-Levin theorem, a number of natural problems from different domains are shown NP-complete.
The treatment is informal but rigorous. Emphasis is on appreciating that the naturalness and the connectedness of all the different notions and the results that we see in the course.
COURSE DETAIL
Module
Topics
No.of Hours
Regular languages
  • Introduction: Scope of study as limits to compubality and tractability.
  • Why it suffices to consider only decision problems, equivalently, set membership problems. Notion of a formal language.
1
  • DFAs and notion for their acceptance, informal and then formal definitions. Class of regular languages.
  • Closure of the class under complementation, union and intersection. Strategy for designing DFAs.
3
  • Pumping lemma for regular languages. Its use as an adversarial game.
  • Generalized version. Converses of lemmas do not hold.
2
  • NFAs. Notion of computation trees. Definition of languages accepted. Construction of equivalent DFAs of NFAs. NFAs with epsilon transitions. Guess and check paradigm for design of NFAs.
4
  • Regular expressions. Proof that they capture precisely class of regular languages. Closure properties of and decision problems for regular languages.
3
  • Myhill-Nerode theorem as characterization of regular languages.States minimization of DFAs.
2
Context free languages
  • Notion of grammars and languages generated by grammars. Equivalence of regular grammars and finite automata. Context free grammars and their parse trees. Context free languages. Ambiguity.
2
  • Pushdown automata (PDAs): deterministic and nondeterministic. Instantaneous descriptions of PDAs.Language acceptance by final states and by empty stack. Equivalence of these two.
2
  • PDAs and CFGs capture precisely the same language class.
1
  • Elimination of useless symbols, epsilon productions, unit productions from CFGs. Chomsky normal form.
2
  • Pumping lemma for CFLs and its use. Closure properties of CFLs. Decision problems for CFLs.
3
Turing machines, r.e. languages, undecidability
  • Informal proofs that some computational problems cannot be solved.
1
  • Turing machines (TMs), their instantaneous descriptions. Language acceptance by TMs. Hennie convention for TM transition diagrams.Robustness of the model-- equivalence of natural generalizations as well as restrictions equivalent to basic model. Church-Turing hypothesis and its foundational implications.
5
  • Codes for TMs. Recursively enumerable (r.e.) and recursive languages. Existence of non-r.e. languages. Notion of undecidable problems. Universal language and universal TM. Separation of recursive and r.e. classes. Notion of reduction. Some undecidable problems of TMs. Rice's theorem.
5
  • Undecidability of Post's correspondence problem (PCP), some simple applications of undecidability of PCP.
3
Intractability
  • Notion of tractability/feasibility. The classes NP and co-NP, their importance. Polynomial time many-one reduction.
  • Completeness under this reduction. Cook-Levin theorem: NP-completeness of propositional satisfiability, other variants of satisfiability.
  • NP-complete problems from other domains: graphs (clique, vertex cover, independent sets, Hamiltonian cycle), number problem (partition), set cover.
6
PREREQUISITES
1.- Discrete Mathematics.
2.- Introductory Algorithms course.
References:
1. John E. Hopcroft, Rajeev Motwani and Jeffery D. Ullman, Automata Theory, Languages, and Computation (3rd. Edition), Pearson Education, 2008.
2. Michael Sipser, Introduction to the Theory of Computation, Books/Cole Thomson Learning, 2001.
3. JE Hopcroft and JD Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
Prof. Somenath Biswas  IIT Kanpur
Professor: Somenath Biswas  Computer Science and EngineeringIndian Institute of Technology, Kanpur

Areas of Interest: Randomized algorithms, computational biology, computational complexity, logic in computer science.
Current Teaching: 2011-12 First Semester: Applications of Markov Chains in Computing
Current Research: Recent Papers  - Projects 

VIDEOS youtube

Mod-01 Lec-01 Lecture-01-Theory of Computation Theory of Computation by Prof. Somenath Biswas, Department of Computer Science & Engineering,IIT Kanpur.For more details on NPTEL visit http://nptel.iitm.ac.in/courses/106104028/
<iframe width="640" height="480" src="http://www.youtube.com/embed/1m64d32RcSI?rel=0" frameborder="0" allowfullscreen></iframe>
Mod-01 Lec-02 Lecture-02-Theory of Computation 48:40  de nptelhrd 3274 reproducciones
Mod-01 Lec-03 Lecture-03-Theory of Computation 1:03:58  de nptelhrd 2352 reproducciones
Mod-01 Lec-04 Lecture-04-Theory of Computation 55:21  de nptelhrd 2282 reproducciones
Mod-01 Lec-05 Lecture-05-Theory of Computation 57:23  de nptelhrd 1573 reproducciones
Mod-01 Lec-06 Lecture-06-Theory of Computation 1:01:35  de nptelhrd 1075 reproducciones
Mod-01 Lec-07 Lecture-07-Theory of Computation 55:05  de nptelhrd 935 reproducciones
Mod-01 Lec-08 Lecture-08-Theory of Computation 53:51  de nptelhrd 798 reproducciones
Mod-01 Lec-09 Lecture-09-Theory of Computation 1:03:28  de nptelhrd 754 reproducciones
Mod-01 Lec-10 Lecture-10-Theory of Computation 59:34  de nptelhrd 889 reproducciones
Mod-01 Lec-11 Lecture-11-Theory of Computation 54:53  de nptelhrd 776 reproducciones
Mod-01 Lec-12 Lecture-12-Theory of Computation 1:01:08  de nptelhrd 643 reproducciones
Mod-01 Lec-13 Lecture-13-Theory of Computation 46:08  de nptelhrd 851 reproducciones
Mod-01 Lec-14 Lecture-14-Theory of Computation 55:31  de nptelhrd 589 reproducciones
Mod-01 Lec-15 Lecture-15-Theory of Computation 49:01  de nptelhrd 611 reproduccione
Mod-01 Lec-16 Lecture-16-Theory of Computation 55:08  de nptelhrd 694 reproducciones
Mod-01 Lec-17 Lecture-17-Theory of Computation1:00:00  de nptelhrd 550 reproducciones
Mod-01 Lec-18 Lecture-18-Theory of Computation57:07  de nptelhrd 620 reproduccioneMod-01 Lec-19 Lecture-19-Theory of Computation 55:50  de nptelhrd 516 reproducciones
Mod-01 Lec-20 Lecture-20-Theory of Computation56:12  de nptelhrd 587 reproducciones
Mod-01 Lec-21 Lecture-21-Theory of Computation52:32  de nptelhrd 503 reproducciones
Mod-01 Lec-22 Lecture-22-Theory of Computation55:27  de nptelhrd 490 reproducciones
Mod-01 Lec-23 Lecture-23-Theory of Computation1:07:17  de nptelhrd 465 reproducciones
Mod-01 Lec-24 Lecture-24-Theory of Computation51:55  de nptelhrd 458 reproducciones
Mod-01 Lec-25 Lecture-25-Theory of Computation55:33  de nptelhrd 441 reproducciones
Mod-01 Lec-26 Lecture-26-Theory of Computation55:02  de nptelhrd 437 reproducciones
Mod-01 Lec-27 Lecture-27-Theory of Computation 52:52  de nptelhrd 437 reproduccione
Mod-01 Lec-28 Lecture-28-Theory of Computation55:32  de nptelhrd 401 reproducciones
Mod-01 Lec-29 Lecture-29-Theory of Computation45:31  de nptelhrd 408 reproducciones
Mod-01 Lec-30 Lecture-30-Theory of Computation53:18  de nptelhrd 410 reproducciones
Mod-01 Lec-31 Lecture-31-Theory of Computation56:03  de nptelhrd 435 reproducciones
Mod-01 Lec-32 Lecture-32-Theory of Computation56:06  de nptelhrd 474 reproducciones
Mod-01 Lec-33 Lecture-33-Theory of Computation48:09  de nptelhrd 609 reproducciones

lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll



llllllllllllllllllllllllllllllllllll

Computer Sc - Theory of Computation

IIT Madras - Prof.Kamala Krithivasan
nptelhrd    11042 vídeos 135260 suscriptores

http://www.youtube.com/course?list=EC85CF9F4A047C7BF7
Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in/
Acerca de este curso
Vídeos: 42 Duración:38 horas


<iframe width="640" height="360" src="http://www.youtube.com/embed/-aIRqNnUvEg?list=EC85CF9F4A047C7BF7" frameborder="0" allowfullscreen></iframe>
http://www.youtube.com/watch?v=-aIRqNnUvEg&list=EC85CF9F4A047C7BF7 
http://www.youtube.com/watch?v=-aIRqNnUvEg&feature=share&list=EC85CF9F4A047C7BF7

Subido el 05/10/2011

Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in

Clases de este curso (42)

Mod-01 Lec-01 GRAMMARS AND NATURAL LANGUAGE PROCESSING

Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
53:26  de Prof.Kamala Kr | Visto 28561 veces
Mod-01 Lec-02 GRAMMARS AND LANGUAGES GENERATED
  49:35  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 13549 veces
Mod-01 Lec-03 GRAMMARS AND LANGUAGES GENERATED (Contd)
  49:27  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 8840 veces
Mod-01 Lec-04 AMBIGUITY IN CFG
  57:10  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 6747 veces
Mod-01 Lec-05 SIMPLICATION OF CFG
  56:03  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 8939 veces
Mod-01 Lec-06 REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG
  55:11  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 8403 veces
Mod-01 Lec-07 GREIBACH NORMAL FORM FOR CFG
  50:12  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 6340 veces
Mod-02 Lec-08 FINAL STATE AUTOMATA
  56:05  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 13141 veces
Mod-02 Lec-09 NON-DETERMINISTIC FSA
  53:53  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 4963 veces
Mod-02 Lec-10 NON DETERMINISTIC FSA (Contd)
  45:15  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 3517 veces
Mod-02 Lec-11 NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES
  45:47  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 4639 veces
Mod-02 Lec-12 EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS
  58:35  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 3346 veces
Mod-02 Lec-13 REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA
  1:03:50  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 7784 veces
Mod-02 Lec-14 DFSA TO REGULAR EXPRESSIONS
  57:29  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 3832 veces
Mod-02 Lec-15 PROBLEMS AND SOLUTIONS
  51:55   Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 3709 veces
Mod-02 Lec-16 PUMPING LEMMAS FOR REGULAR SETS AND CFL
  59:50   Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 9800 veces
Mod-02 Lec-17 MYHILL-NERODE THEOREM
  50:13  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 4999 veces
Mod-02 Lec-18 MINIMIZATION OF DFSA
  55:17  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 3693 veces
Mod-02 Lec-19 FSA WITH OUTPUT MOORE AND MEALY MACHINES
  51:43  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 5006 veces
Mod-03 Lec-20 PUSHDOWN AUTOMATA
  45:43  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 12897 veces
Mod-03 Lec-21 PUSHDOWN AUTOMATA,EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE
  49:42  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 6901 veces
Mod-03 Lec-22 PUSHDOWN AUTOMATA CFG TO PDA
  50:39  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 8387 veces
Mod-04 Lec-23 PUSHDOWN AUTOMATA PDA TO CFG
  58:25   Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 5445 veces
Mod-04 Lec-24 PROBLEMS AND SOLUTIONS-I
  50:04  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 3106 veces
Mod-04 Lec-25 PROBLEMS AND SOLUTIONS - III
  1:04:03   Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 2773 veces
Mod-05 Lec-26 TURING MACHINES
  58:41 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 19792 veces
Mod-05 Lec-27 TURING MACHINES (Contd)
  52:53Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 6064 veces
Mod-05 Lec-28 TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION
  57:05 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 5234 veces
Mod-05 Lec-29 GENERALIZED VERSIONS OF TURING MACHINES
  57:35 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 3001 veces
Mod-05 Lec-30 TURING MACHINE AS A GENERATING DEVICE
  1:00:09 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 3125 veces
Mod-06 Lec-31 RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM
  57:22 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 3523 veces
Mod-06 Lec-33 RICE'S THEOREM,LINEAR BOUNDED AUTOMATA,PROPERTIES OF TM
  54:17 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 2975 veces
Mod-06 Lec-32 PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY
  59:03 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 2770 veces
Mod-09 Lec-41 DNA COMPUTING
  1:02:00 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 1832 veces
Mod-08 Lec-40 GRAMMAR SYSTEMS
  56:21 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 1758 veces
Mod-08 Lec-39 L - SYSTEMS
  55:05  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 1156 veces
Mod-07 Lec-35 POST'S CORRESPONDENCE PROBLEMS (Contd) TIME AND TAPE COMPLEXITY OT TM
  53:51  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 2019 veces
Mod-07 Lec-36 NP - COMPLETE PROBLEMS , COOK'S THEOREM
  1:10:06  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 5992 veces
Mod-06 Lec-34 POST'S CORRESPONDENCE PROBLEMS
  50:49  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 2297 veces
Mod-08 Lec-38 REGULATED REWRITING

Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
  59:59 de Prof.Kamala Kr | Visto 1043 veces
Mod-09 Lec-42 MEMBRANE COMPUTING
  56:28 Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 1126 veces
Mod-07 Lec-37 NP - COMPLETE PROBLEMS (Contd)
  1:01:20  Theory of Computation by Prof.Kamala Krithivasan,Department of Computer Science and Engineering,IIT Madras. For more details on NPTEL visit http://nptel.iitm.ac.in
de Prof.Kamala Kr | Visto 2127 veces








No hay comentarios:

Publicar un comentario