AGD :: Aplicatiu de Guies Docents v2.1

Arxiu en format PDF

2022/2023

Algorithmics and Combinatorics in Graphs. Heuristic Methods

Code: 104388 ECTS Credits: 6

Degree	Type	Year	Semester
2503740 Computational Mathematics and Data Analytics	FB	1	2

Contact

Name:: Lluís Alseda Soler
Email:: lluis.alseda@uab.cat

Use of Languages

Principal working language:: catalan (cat)
Some groups entirely in English:: No
Some groups entirely in Catalan:: Yes
Some groups entirely in Spanish:: No

Teachers

: Lluís Alseda Soler
: Albert Ruiz Cirera

Prerequisites

It is necessary that the student has taken Mathematics in the two baccalaureate courses and has examined this matter in the PAU.

[Translated from the Catalan version by Google translator]

Objectives and Contextualisation

Know the combinatorial graphs and their terminology
Know the different search algorithms and movement in graphs
Know the types of dynamic data for representation of graphs and their implemtation in C
Know the basic algorithms of optimal searches in graphs and their complexity
[Translated from the Catalan version by Google translator]

Competences

Apply a critical spirit and rigour for the validation or rejection of your own arguments and those of others.
Demonstrate a high capacity for abstraction and translation of phenomena and behaviors to mathematical formulations.
Formulate hypotheses and think up strategies to confirm or refute them.
Make effective use of bibliographical resources and electronic resources to obtain information.
Relate new mathematical objects with other known objects and deduce their properties.
Students must be capable of collecting and interpreting relevant data (usually within their area of study) in order to make statements that reflect social, scientific or ethical relevant issues.
Students must be capable of communicating information, ideas, problems and solutions to both specialised and non-specialised audiences.
Students must have and understand knowledge of an area of study built on the basis of general secondary education, and while it relies on some advanced textbooks it also includes some aspects coming from the forefront of its field of study.
Using criteria of quality, critically evaluate the work carried out.
Work cooperatively in a multidisciplinary context assuming and respecting the role of the different members of the team.

Learning Outcomes

"Explain ideas and mathematical concepts pertinent to the course; additionally, communicate personal reasonings to third parties."
Apply a critical spirit and rigour for the validation or rejection of your own arguments and those of others.
Contrast, if possible, the use of calculation with the use of abstraction in solving a problem.
Describe the concepts and mathematical objects pertaining to the subject.
Develop autonomous strategies for solving problems such as identifying the ambit of problems within the course, discriminate routine from non-routine problems, design an a priori strategy to solve a problem, evaluate this strategy.
Evaluate the advantages and disadvantages of using calculation and abstraction.
Identify the essential ideas in the demonstration of ceratin basic theorems and know how to adapt these to obtain other results.
In an orderly and accurately manner, draft brief mathematical texts (exercises, resolution of theoretical questions, etc.).
Make effective use of bibliographical resources and electronic resources to obtain information.
Read and understand a mathematical text at the current level of the course.
Students must be capable of collecting and interpreting relevant data (usually within their area of study) in order to make statements that reflect social, scientific or ethical relevant issues.
Students must be capable of communicating information, ideas, problems and solutions to both specialised and non-specialised audiences.
Students must have and understand knowledge of an area of study built on the basis of general secondary education, and while it relies on some advanced textbooks it also includes some aspects coming from the forefront of its field of study.
Using criteria of quality, critically evaluate the work carried out.
Work cooperatively in a multidisciplinary context, taking on and respecting the role of the distinct members in the team.

Content

Combinatorial algorithms for graphics
Combined graphs and graph searches
Theory of graphs: introduction
Search in graphs: Depth-first and Breadth-first
Greedy Algorithms
Recursion
Abstract data types and object-oriented programming: Dynamic lists and trees
Graphic representation algorithms. Avantatgews disadvantages of each of the options.
Abstract and dynamic data types for graphs and their implementation in C.
Basic algorithms for optimal search graphs and their complexity
Calculation of distances from latitude and longitude
Algorithm of Dijkstra for optimal routes in graphs
Algorithm A *: heuristic search for optimal paths in graphs
[Translated from the Catalan version by Google translator]

Methodology

The weekly sessions of the subject will be divided, usually, in two parts:
a) A theoretical part in which the teacher will introduce the concepts, methods and examples related to the syllabus of the subject.

b) A practical part in which students will be proposed a series of problems or exercises in which they will be shown and a concrete work will be worked on that which has been seen in the theoretical part. These sessions will be held in one of the faculty's computer rooms. Each practice will have a different statement, which will be published on the Virtual Campus and will involve the delivery of the answers to some questions raised. The delivery will be during the day the practice is performed.

Complementary exercises will also be proposed as an autonomous activity to help them understand the applied part of the subject.

[Translated from the Catalan version by Google translator]

Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.

Activities

Title	Hours	ECTS	Learning Outcomes
Type: Directed
Attend the theoretical and practical classes	56	2.24	2, 1, 10, 8, 9
Type: Supervised
Completion of the practices	55	2.2	2, 14, 6, 3, 1, 10, 12, 11, 8, 15, 9
Type: Autonomous
Resolution of complementary exercises	30	1.2	2, 14, 6, 3, 1, 10, 12, 11, 8, 15, 9

Assessment

The evaluation will consist of the following activities:

A final exam, which accounts for 40% of the note.
An individual practical work with a delivery period where it will be necessary to develop and implement algorithms, which account for 35% of the note.
Delivery, during practical sessions, of practical exercises that will be carried out in groups of two. They count 25% of the note. This is a continuous evaluation activity and is not recoverable.
The minimum grade in each of the three evaluation activities to be able to pass the subject is 3.5 points out of 10.

Final exam and individual practical work are recoverable for those studients who have participated in the three items of the evaluation but have not passed the subject.