Languages, Computing and Intelligent Systems26021
- Centre
- Faculty of Informatics
- Degree
- Bachelor's Degree in Informatics Engineering
- Academic course
- 2023/24
- Academic year
- 2
- No. of credits
- 6
- Languages
- Spanish
- Basque
- English
- Code
- 26021
TeachingToggle Navigation
Teaching guideToggle Navigation
Description and Contextualization of the SubjectToggle Navigation
This subject is an introduction to the Computation Speciality and its goal is to deepen fundamental principles and models of computation and programming languages, in order to apply them in new computer systems, in the assessment of the complexity of problems and in the design of algorithmic strategies to solve them, independently of the equipment or software it is used.
Algorithmic problem solving has been studied in previous subjects (Principles of Programming, Modular Programming and Object Orientation, and Data Structures and Algorithms), using several methodologies and concrete programming languages. In this subject we will instead address which problems can be solved algorithmically, regardless of the equipment or software.
We will cover topics ranging from basic contents of formal languages and automata to basic principles of computability and complexity, including steps towards Artificial Intelligence. These topics are further elaborated in other subjects of the speciality such as Abstract Models of Computation, Compilation, Design of Algorithms, Data Mining, and Artificial Intelligence. Some of the topics can be also studied in more detail in subjects offered in this degree, such as Advanced Tools in Artificial Intelligence, Machine Learning and Neural Networks, Natural Language Processing, Knowledge Based Systems, Search Heuristics, Logic Programming, and Functional Programming.
Applications of models studied in this subject can be found through all the computer engineering professional scope. Languages enable human-machine and machine-machine communication. Without them, current application such as network communication protocols, markup languages, etc. would never exist. For example:
- the design and implementation of modern programming languages is based on grammars;
- text processors and natural language processing base some of their techniques on the models seen in the subject;
- communication protocols, vending machines, and many games are described in terms of finite state automata.
Finally, the results of complexity are the basis of cryptography.
Skills/Learning outcomes of the subjectToggle Navigation
- Identifying and resolving problems that can be approached using restricted computational models (automata) or alternative computational models (intelligent systems).
- Designing automata, grammars, and regular expressions to define formal languages.
- Using pattern recognizing and processing software.
- Being aware of the existence of intrinsic limits in the computational processes and of their consequences.
- Analysing problems and their computational solutions using verbal, mathematical, and graphic languages.
Theoretical and practical contentToggle Navigation
1. Introduction. Strings and languages.
2. Computation without memory.
2.1 Finite automata and transducers. Equivalences and transformations.
2.2 Regular expressions. Equivalences and transformations.
2.3 Limits.
3. Computation with restricted memory.
3.1 Context-free grammars. Ambiguity.
3.2 Pushdown automata.
3.3 Limits.
4. General model of computers.
4.1 Turing automata.
4.2 Turing machines and diagrams.
4.3 The Church-Turing Thesis.
4.4 Limits. Uncomputability.
5. Intelligent Systems.
5.1 Introduction to computational complexity. Need for approaches.
5.2 Non-functional specifications.
5.3 Example: Decision trees.
MethodologyToggle Navigation
The lessons will be presented in class, along with complementary reading material. In the class sessions the following activities will take place on a regular basis: the course concepts will be presented systematically, followed by exercises to assimilate the learnt techniques.
A large collection of problem statements will be made available, to get used to fluently and appropriately expressing oneself regarding problems according to each context: informal (usually natural language), text-based formal (logic and mathematics), and graphic-based formal (automata diagram, decision tree).
Collaborative study will be enhanced through the use of eGela forums to present organized solutions to the problems from the collections of proposed statements. To share those solutions quickly and comprehensively, graphic tools will be used, which will allow viewing the behaviour of the theoretical models and facilitate understanding how they function.
Assessment systemsToggle Navigation
- Continuous Assessment System
- Final Assessment System
- Tools and qualification percentages:
- The percentages and types of evaluation are specified in the following sections (%): 100
Ordinary Call: Orientations and DisclaimerToggle Navigation
The subject has two assessment options: end-of-course (or overall) assessment and continuous assessment.
CONTINUOUS ASSESSMENT: This modality of assessment is opt-in, as students will be required to dedicate time during the semester to studying and solving exercises in order to pass the subject.
The various assessment activities will be weighted in the following way:
1) Written tests (80%)
2) Exercises/problems delivery assessment (20%)
There will be three written tests, with weights of 35%, 30% and 15%, which make up 80% of the final grade of the subject indicated above for the written tests. Each of the written tests will require a minimum grade of 30% for students to remain in continuous assessment mode. No minimum grade will be required for the delivery of exercises/problems.
Students will be considered for continuous assessment unless they explicitly renounce. Those students who meet the requirements of continuous assessment but decide to choose the end-of-course evaluation, will have to notify to the teachers in charge of the subject about that decision before the last week of classes via eGela. If a student does not renounce continuous evaluation by the aforementioned date, it will be assumed that this is confirmation of continuous assessment.
END-OF-COURSE ASSESSMENT: This option will be applied both to students who do not wish to choose the continuous assessment and to those who do not pass the requirements. The assessment method will be a written exam that will cover 100% of the subject content, which will take place as specified in the official schedule of exams of the Faculty.
During all written tests (continuous or overall) the use of books, notes, phones, computers, or other electronic devices is strictly prohibited.
Extraordinary Call: Orientations and DisclaimerToggle Navigation
The test will be a written exam that will cover 100% of the subject content, which will take place as specified in the official schedule of exams of the Faculty.
During the written exam, the use of books, notes, phones, computers, or other electronic devices is strictly prohibited.
Compulsory materialsToggle Navigation
The slides used by the lecturers to present the subject, as well as the problems and exercises, are considered compulsory material and will be made available in eGela.
The use of the following resources is also necessary to follow the subject:
- eGela
- Corporate email address
- JFLAP
BibliographyToggle Navigation
Basic bibliography
- INTRODUCTION TO AUTOMATA THEORY, LANGUAGES AND COMPUTATION: J.E. Hopcroft, R. Motwani & J.D. Ullman. Addison-Wesley, 3rd edition, 2006.
- AUTÓMATAS Y LENGUAJES. UN ENFOQUE DE DISEÑO: R. Brena. Instituto Tecnológico de Monterrey, 2003. (https://lenguajesformalesyautomatas.files.wordpress.com/2017/11/automatas-y-lenguajes.pdf)
- JFLAP: AN INTERACTIVE FORMAL LANGUAGES AND AUTOMATA PACKAGE: S.H. Rodger eta T.W. Finley. Jones & Bartlett, 2006. (https://www.jflap.org/jflapbook/jflapbook2006.pdf)
- ARTIFICIAL INTELLIGENCE: A MODERN APPROACH: S. Russell and P. Norvig. Prentice Hall, 3rd edition, 2009
In-depth bibliography
- AUTOMATA, COMPUTABILITY AND COMPLEXITY: E. Rich. Pearson Education, 2008.
- INTRODUCCIÓN A LA TEORÍA DE AUTÓMATAS, GRAMÁTICAS Y LENGUAJES. E. Gaudioso & T. García. Editorial Universitaria Ramón Areces. 2017. (contains exercises and solutions)
Web addresses
- Visual and interactive tools (JFLAP): http://www.jflap.org
- Alan Turing: http://www.turing.org.uk
Examining board of the 5th, 6th and exceptional callToggle Navigation
- BERGES GONZALEZ, IDOIA
- IBAÑEZ ANFURRUTIA, FELIPE
- PEREZ FERNANDEZ, TOMAS ANTONIO
GroupsToggle Navigation
01 Teórico (Spanish - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 09:00-10:30 (1) | 10:30-12:00 (2) |
Teaching staff
01 Applied laboratory-based groups-1 (Spanish - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 12:00-13:30 (1) |
Teaching staff
01 Applied laboratory-based groups-2 (Spanish - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 12:00-13:30 (1) |
Teaching staff
46 Teórico (Basque - Tarde)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 14:00-15:30 (1) | 15:30-17:00 (2) |
Teaching staff
46 Applied laboratory-based groups-1 (Basque - Tarde)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 17:00-18:30 (1) |
Teaching staff
46 Applied laboratory-based groups-2 (Basque - Tarde)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 17:00-18:30 (1) |
Teaching staff
61 Teórico (English - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 09:00-10:30 (1) | 10:30-12:00 (2) |
Teaching staff
61 Applied laboratory-based groups-1 (English - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 12:00-13:30 (1) |
Teaching staff
61 Applied laboratory-based groups-2 (English - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 12:00-13:30 (1) |