AU3012 Computational and Visualization Theory Syllabus:
AU3012 Computational and Visualization Theory Syllabus – Anna University Regulation 2021
COURSE OBJECTIVES:
The objective of this course is to provide the students a comprehensive insight into theory of computation by understanding grammar, languages and other elements of modern language design to develop capabilities to design and develop formulations for computing models
UNIT I AUTOMATA THEORY
Defining Automaton, Finite Automaton, Transitions and Its properties, Acceptability by Finite Automaton, Nondeterministic Finite State Machines, DFA and NDFA equivalence, Mealy and Moore Machines, Minimizing Automata.
UNIT II REGULAR GRAMMAR & CONTEXT FREE LANGUAGES AND PUSHDOWN AUTOMATA
Regular Grammar, Regular Expressions, Finite automata and Regular Expressions, Pumping Lemma and its Applications, Closure Properties, Regular Sets and Regular Grammar Context Free Languages: Context-free Languages, Derivation Tree, Ambiguity of Grammar, CFG simplification, Normal Forms, Pumping Lemma for CFG Pushdown Automata: Definitions, Acceptance by PDA, PDA and CFG
UNIT III TURING MACHINES & UNDECIDABILITY
Turing Machine Definition, Representations, Acceptability by Turing Machines, Designing and Description of Turing Machines, Turing Machine Construction, Variants of Turing Machine, Undecidability: The Church-Turing thesis, Universal Turing Machine, Halting Problem, Introduction to Unsolvable Problems
UNIT IV FOUNDATIONS FOR DATA VISUALIZATION
Introduction to Visualization – Visualization stages – Experimental Semiotics based on Perception – Gibson‘s Affordance theory – A Model of Perceptual Processing – Costs and Benefits of Visualization – Types of Data.
UNIT V MULTIDIMENSIONAL VISUALIZATION
1D, 2D, 3D – Multiple Dimensions – Trees – Web Works – Data Mapping: Document Visualization – Workspaces.
TOTAL: 45 PERIODS
COURSE OUTCOMES:
At the end of the course, the student will be able to
1. Understand Grammar and Languages
2. Learn about Automata theory and its application in Language Design
3. Learn about Turing Machines and Pushdown Automata
4. Describe the stages of visualization
5. Understand Information and Scientific visualization techniques
TEXT BOOKS:
1. Hopcroft E. J., Ullman D. J. and Motwani R., Introduction to Automata Theory, Languages and Computation, Pearson Education (2007) 3rd ed.
2. Martin C. J., Introduction to Languages and the Theory of Computation, McGraw-Hill Higher Education (2011) 4th ed.
3. Colin Ware “Information Visualization Perception for Design”,3 rd edition, Morgan Kaufman 2012.
4. Stuart.K.Card, Jock.D.Mackinlay and Ben Shneiderman, “Readings in Information Visualization Using Vision to think”, Morgan Kaufmann Publishers, 1999.
REFERENCES:
1. Theory of Computation, Kavi Mahesh, Wiley India
2. Elements of the Theory of Computation, Lewis, Papadimitriou, PHI
3. Introduction to Languages and the Theory of Computation, John E Martin, McGraw-Hill Education
4. Introduction to Theory of Computation, Michel Sipser, Thomson
5. Chaomei Chan, “Information Visualization”,Beyond the horizon, 2nd edition, Springer Verlag, 2004.
6. Pauline Wills, “Visualisation: A Beginner’s Guide”, Hodder and Stoughlon, 1999.