Degree | Informatics Engineering
Introduction to Computer Science
Scientific Field
Computer Science
Duration
Semester
ECTS
6
Contact Hours Theoretical Practices
60h
LEARNING OBJECTIVES
To complete this unit, students must acquire the following knowledge and skills:
1. Understand the theoretical importance of computer science;
2. Acquire the mathematical knowledge required to approach the theoretical foundations of computer science;
3. Master the fundamental notions of automata theory and formal languages;
4. Understand the concept of a Turing machine;
5. Understand the relevance of the Turing machine relative to computer system analysis;
6. Analyse the concept of language decidability;
7. Understand the theoretical foundations of computability problems;
8. Understand the theoretical foundations to analyse the complexity of computer algorithms.
PROGRAM
1. Introduction to computer logic
2. Mathematical fundamentals
2.1. Sets, Relations, and Functions
2.2. Graphs and trees
2.3. Mathematical induction principle
3. Automata Theory
3.1. Automaton concept
3.2. Description of finite automata
3.3. Finite State Machines
4. Formal Languages
4.1. Concept
4.2. Grammar
4.3. Grammar-Generated languages
4.4. Operations in Languages
4.5. Languages and Automatons
5. Regular Sets and Grammars
5.1. Regular Expression
5.2. Finite Automata and Regular Expressions
5.3. Regular Grammars
6. Turing Machines
6.1. Turing Machine Model.
6.2. Turing machine representation
6.3. Turing Machines and Languages
7. Decidability
7.1. Algorithms
7.2. Decidable Languages
7.3. Undecidable languages
8. Computability
8.1. Fundamental concepts
8.2. Computability analysis
9. Computational complexity
9.1. Growth Functions
9.2. P and NP Classes
9.3. Analysis of algorithms complexity
DEMONSTRATION OF COHERENCE BETWEEN SYLLABUS AND LEARNING RESULTS
This curricular unit was defined to allow students to acquire knowledge and understanding, starting from basic concepts. This will give them an understanding of conceptual building that sustains the theory of computer science, concerning computability and the spatial and temporal complexity of algorithms.
TEACHING METHODOLOGY AND ASSESSMENT
This unit has a theoretical-practical nature. In total 60 hours are planned for classroom teaching. The student’s total study time should be 162 hours. As this unit has a high level of abstraction, it is fundamental that the concepts be immediately illustrated with practical examples. This allows students to test their understanding of the subjects.
Under ISTEC’s Regulation of Functioning, students are evaluated through a mandatory individual written exam. The student’s final classification may be positively affected by elements resulting from a continuous assessment process, such as tests, individual or group academic work, individual initiatives to participate in classes and learning resources provided by e-learning systems.
DEMONSTRATION OF CONSISTENCY BETWEEN TEACHING METHODOLOGIES AND LEARNING RESULTS
The methodology used consists of theoretical expositions, practical examples and exercises solved in class, this allows students to assimilate concepts necessary to understand the theoretical foundations of computer science, the theory of automata, formal languages, computability and complexity computing.
BIBLIOGRAPHY
Fundamental:
N. Chandrasekaran, Theory of Computer Science: Automata, Languages and Computation
Michael Sipser, Introduction to the Theory of Computation 3rd Edition
Complementary:
Shyamalendu Kandar, Introduction to Automata Theory, Formal Languages and Computation
Krithivasan, Kamala and R Rama, Introduction to Formal Languages, Automata Theory and Computation
INTERNET:
Access to specialist publications, free of charge, through the SPRINGER network:
https://link.springer.com/