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 DETAILWe 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.
Module
|
Topics
|
No.of Hours
|
| Regular languages |
|
1
|
|
3
|
|
|
2
|
|
|
4
|
|
|
3
|
|
|
2
|
|
| Context free languages |
|
2
|
|
2
|
|
|
1
|
|
|
2
|
|
|
3
|
|
| Turing machines, r.e. languages, undecidability |
|
1
|
|
5
|
|
|
5
|
|
|
3
|
|
| Intractability |
|
6
|
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 Engineering - Indian 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 Computations
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 Computations
Mod-01 Lec-21 Lecture-21-Theory of Computations
Mod-01 Lec-22 Lecture-22-Theory of Computations
Mod-01 Lec-23 Lecture-23-Theory of Computations
Mod-01 Lec-24 Lecture-24-Theory of Computations
Mod-01 Lec-25 Lecture-25-Theory of Computations
Mod-01 Lec-26 Lecture-26-Theory of Computations
Mod-01 Lec-27 Lecture-27-Theory of Computation 52:52 de nptelhrd 437 reproduccione
Mod-01 Lec-28 Lecture-28-Theory of Computations
Mod-01 Lec-29 Lecture-29-Theory of Computations
Mod-01 Lec-30 Lecture-30-Theory of Computations
Mod-01 Lec-31 Lecture-31-Theory of Computations
Mod-01 Lec-32 Lecture-32-Theory of Computations
Mod-01 Lec-33 Lecture-33-Theory of Computations
lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
llllllllllllllllllllllllllllllllllll
Computer Sc - Theory of Computation
IIT Madras - Prof.Kamala Krithivasannptelhrd 11042 vídeos 135260 suscriptores
http://www.youtube.com/course?list=EC85CF9F4A047C7BF7Theory 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
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 PROCESSINGMod-01 Lec-02 GRAMMARS AND LANGUAGES GENERATED
Mod-01 Lec-03 GRAMMARS AND LANGUAGES GENERATED (Contd)
Mod-01 Lec-04 AMBIGUITY IN CFG
Mod-01 Lec-05 SIMPLICATION OF CFG
Mod-01 Lec-06 REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG
Mod-01 Lec-07 GREIBACH NORMAL FORM FOR CFG
Mod-02 Lec-08 FINAL STATE AUTOMATA
Mod-02 Lec-09 NON-DETERMINISTIC FSA
Mod-02 Lec-10 NON DETERMINISTIC FSA (Contd)
Mod-02 Lec-11 NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES
Mod-02 Lec-12 EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS
Mod-02 Lec-13 REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA
Mod-02 Lec-14 DFSA TO REGULAR EXPRESSIONS
Mod-02 Lec-15 PROBLEMS AND SOLUTIONS
Mod-02 Lec-16 PUMPING LEMMAS FOR REGULAR SETS AND CFL
Mod-02 Lec-17 MYHILL-NERODE THEOREM
Mod-02 Lec-18 MINIMIZATION OF DFSA
Mod-02 Lec-19 FSA WITH OUTPUT MOORE AND MEALY MACHINES
Mod-03 Lec-20 PUSHDOWN AUTOMATA
Mod-03 Lec-21 PUSHDOWN AUTOMATA,EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE
Mod-03 Lec-22 PUSHDOWN AUTOMATA CFG TO PDA
Mod-04 Lec-23 PUSHDOWN AUTOMATA PDA TO CFG
Mod-04 Lec-24 PROBLEMS AND SOLUTIONS-I
Mod-04 Lec-25 PROBLEMS AND SOLUTIONS - III
Mod-05 Lec-26 TURING MACHINES
Mod-05 Lec-27 TURING MACHINES (Contd)
Mod-05 Lec-28 TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION
Mod-05 Lec-29 GENERALIZED VERSIONS OF TURING MACHINES
Mod-05 Lec-30 TURING MACHINE AS A GENERATING DEVICE
Mod-06 Lec-31 RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM
Mod-06 Lec-33 RICE'S THEOREM,LINEAR BOUNDED AUTOMATA,PROPERTIES OF TM
Mod-06 Lec-32 PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY
Mod-09 Lec-41 DNA COMPUTING
Mod-08 Lec-40 GRAMMAR SYSTEMS
Mod-08 Lec-39 L - SYSTEMS
Mod-07 Lec-35 POST'S CORRESPONDENCE PROBLEMS (Contd) TIME AND TAPE COMPLEXITY OT TM
Mod-07 Lec-36 NP - COMPLETE PROBLEMS , COOK'S THEOREM
Mod-06 Lec-34 POST'S CORRESPONDENCE PROBLEMS
Mod-08 Lec-38 REGULATED REWRITING
Mod-09 Lec-42 MEMBRANE COMPUTING
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