Basic algorithms for Artificial Intelligence

Know and know how to apply the main artificial intelligence strategies for solving search problems in different scenarios (informed, uninformed and adversarial search), constraint satisfaction and planning.

T1: Historical perspective of AI
T2: Problem solving by means of state-space search
T3: Uninformed and informed search strategies
T4: Constraint satisfaction problems
T5: Adversarial search and games
T6: Automatic planning

Basic bibliography:
1. J. Palma, R. Marín (eds.). Artificial Intelligence. Methods, techniques and applications. McGrawHill (2008). ISBN: 9788448156183
Fernández Galán, S., González Boticario, J., Mira Mira, J. Solved Problems of Applied Artificial Intelligence. Search and Representation. Addison Wesley (1998). ISBN: 9788478290178
3. Russell, S., Norvig, P. Artificial Intelligence (A Modern Approach), (4th Edition Global Edition, 2022). ISBN: 9781292401133. (2nd edition also in Spanish).
4. Handbook of Artificial Intelligence. Springer-Verlag, 2015. ISBN 978-3-662-43505-2.
Supplementary Bibliography
5. Rossi, Van Beek, Walsh (2006) Handbook of Constraint Programming, Elsevier.
Joseph Y-T. Leung (2004) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman and Hall/CRC.
7. Artificial intelligence for developers. Virginie Mathivet. ENI Editions, 2015.
8. Artificial Intelligence Course. Fernando Sancho Caparrini. http://www.cs.us.es/~fsancho

Contribute to achieve the competences included in the memory of the degree in Artificial Intelligence, especially:

BASIC AND GENERAL
CG3 - Ability to design and create quality AI-based models and solutions that are efficient, robust, transparent and accountable.
CG4 - Ability to select and justify the appropriate methods and techniques to solve a specific problem, or to develop and propose new methods based on artificial intelligence.
CG5 - Ability to conceive new computational systems and/or evaluate the performance of existing systems, integrating artificial intelligence models and techniques.
CB2 - That students know how to apply their knowledge to their work or vocation in a professional manner and possess the competencies that are usually demonstrated through the elaboration and defense of arguments and problem solving within their area of study.
CB4 - Students are able to convey information, ideas, problems and solutions to both specialized and non-specialized audiences.

CROSSCUTTING
TR1 - Ability to communicate and transmit knowledge, skills and abilities.
TR3 - Ability to create new models and solutions autonomously and creatively, adapting to new situations. Initiative and entrepreneurial spirit.
TR5 - Ability to develop models, techniques and solutions based on artificial intelligence that are ethical, non-discriminatory and reliable.

SPECIFIC
CE12 - Know the basics of artificial intelligence algorithms and models for solving problems of certain complexity, understand their computational complexity and have the ability to design new models.

Once the student has passed the course:
- They will be able to apply and implement search methods with informed and uninformed strategies in problems represented in state spaces.
- You will be able to solve adversarial search problems.
- You will be able to solve search and optimisation problems with constraints.
- You will learn different problem-solving algorithms based on searching a space of possible configurations.
- Know and be able to model and solve basic planning or scheduling problems.

The didactic methodology will be based on individual work -although sometimes in groups-, discussion with the teacher in class and individual tutorials.

For each topic or thematic block of the lectures, the teacher will prepare the contents, explain the objectives of the topic to the students in class, suggest bibliography, provide them with additional work material, etc. In the lecture classes, students will work on the competences CG3, CG4, CG5, CE12. In addition, the lecturers will propose a set of activities to be carried out individually or in groups (assignments, presentations, readings, practicals, etc.), with the aim of facilitating learning. Some of these activities will be assessable and will therefore be compulsory as indicated in the learning assessment system. The practicals and part of the interactive sessions will take place in the School's IT classroom, using different software tools for each of the thematic blocks. These activities will allow the development of the competences CG5, CB2, CB4, TR1-3, CE12.

Students will work individually or in small groups, with the constant support of the faculty. There will be scripts of practices, seminars and other activities to be carried out individually or in small groups.

Teaching will be supported by the USC virtual platform in the following way: repository of documentation related to the subject (texts, presentations, recommended readings...) and virtual tutoring of students (e-mail, forums).

The learning evaluation considers both the theoretical part (40%), the practical part (50%) and other activities (10%). In order to pass the subject an overall grade of 5 or higher must be obtained, out of a maximum score of 10 points, according to the following criteria:

- Theoretical part (40%): this will be assessed in a single exam to be taken on the official date. The grade of the exam must be equal to or higher than 4 out of a maximum score of 10 points in order to pass the subject as a whole. Otherwise, it will have to be repeated at the make-up exam.

- Practical part (50%): evaluation of all the compulsory practical activities proposed by the lecturers, according to the following schedule:
• P1. State space search (deliverable after interactive session 3; weight 20% of the practical part).
• P2. Informed searches (deliverable after interactive session 6; weight 20% of the practical part).
• P3. Constraint satisfaction problems (deliverable after interactive session 8; weight 20% of the practical part).
• P4. Search problems with adversary (deliverable after interactive session 10; weight 20% of the practical part).
• P5. Automatic planning (deliverable after interactive session 12; weight 20% of the practical part).
The evaluation of interactive practices does not end with the delivery of the same but may include the completion of a self-assessment questionnaire and / or a session of presentation and face-to-face discussion of the same. These evaluation activities will be compulsory and may be carried out in interactive class, so that, for the purposes of the provisions of Art.1 of the "Regulamento de asistencia a clase nas ensinanzas oficiais de grao e máster da Universidade de Santiago de Compostela (25/11/2024)", attendance at the sessions where these activities are scheduled will be mandatory, being a requirement the completion of the same that, if not met, will mean a grade of 0.0 in the corresponding deliverable. Except as indicated in this section, class attendance will not be assessed in the assessment system, although attendance at the different teaching activities helps to improve understanding of the subject and the acquisition of the competences .

All the deliveries will have the same weight in the practical part of the course. The grade for this part must be equal to or higher than 4 out of a maximum of 10 points in order to pass the whole subject. Those practicals with a grade lower than 3 points must be assessed at the second opportunity.

- Other Activities (10%): evaluation of other compulsory interactive activities proposed by the teacher:
Completion of a paper on current issues in AI, presentation of the paper and peer review. The work will be done in groups of 2 and will consist of a short joint oral presentation, the production of a single supporting slide and answering questions posed by other peers. It will also be required to elaborate and ask a question about another paper (peer review). Technical visit to an entity (company, technology centre, research centre) that applies AI in its projects, with the aim of learning about the use of different AI paradigms in real applications. The visit will be evaluable by means of a questionnaire.
The two activities in this part are weighted 80% (work) and 20% (visit). The grade for this part must be equal to or higher than 4 out of a maximum score of 10 points in order to pass the subject as a whole, with a minimum threshold in each part of 3 points out of 10 in each one . None of these activities can be recovered at the second opportunity.

The final grade for the subject will be the arithmetic mean weighted by the percentages indicated above for the theoretical and practical parts and complementary activities, unless the established minimum thresholds are not reached in any assessment item. In the event that the minimum mark required to pass the subject overall is not achieved in one or more parts, the final mark for the opportunity will be the minimum of the marks obtained in those parts.

Students who have not sat the examination or have not submitted to the assessment of any other compulsory activity will be marked as "no-shows".

In order to pass the subject at the second opportunity, students must undergo the assessment of all the compulsory parts pending, in accordance with the above. For the rest, the grades obtained during the course will be retained. Repeating students must follow the same evaluation system as the rest of the students.

In the case of fraudulent performance of exercises or tests, the provisions of the regulations on the evaluation of the academic performance of students and the review of grades will apply (https://www.xunta.gal/dog/Publicados/2011/20110721/AnuncioG2018-190711-…). In application of the ETSE regulations on plagiarism (approved by the Xunta da ETSE on 19/12/2019), the total or partial copying of any practical or theory exercise will result in the failure of the two opportunities of the course, with a grade of 0.0 in both cases (https://www.usc.es/etse/files/u1/NormativaPlagioETSE2019.pdf).

Classroom work time: 51 total hours, divided into 20h (lectures), 30h (seminars and practicals), 1h (tutorials).
Personal work time: 99h (total), divided into 39h (autonomous study of theory and practices) and 60h (work, projects and other activities).

It is recommended not to take the subject without having previously passed the subjects Mathematical Optimisation, "Programming I", "Programming II" and "Algorithms".
The course will be taught in Spanish and Galician, but the bibliography, references and notes may contain content in English.

It is recommended to have passed the subjects "Mathematical Optimization", "Programming I", "Programming II" and "Algorithms".
The course will be taught in Spanish and Galician, but part of the contents, bibliography or other references may be in English.