Course group - TB1-PRPD
In his professional capacity every engineer will be confronted by the design and implementation of problem solving methods related for example to Management and Resource Allocation, Planning, Organisation, Scheduling .., in other words numerous problems of a discrete nature, i.e. able to be modelled by finite structures and which are encountered in fields as varied as Healthcare, the Environment, Production management, ..and of course in Computer Science.
In general these problems can be solved by several different methods but cost assessments must be made. In addition, the sought for algorithms should ideally be the most economical in terms of means, of time … The programme has thus been designed to provide some clarifications and possible pathways for processing and concretely solving this type of problem, while being able to measure the effectiveness of algorithms and their limitations.
The idea therefore is to undertake a reasoned overview of numerous possible classical strategies for problem solving; Algorithmic Paradigms. Secondly the aim is to present the essential results concerning a classification of problems based on the “difficulty” (complexity) involved in solving them by algorithms: i.e. an initiation into the “Theory of Complexity”. Finally, while not always being able to solve a problem exactly and efficiently, some methods of approximation solution calculations will be examined, along with the issues raised by such an approach.
The course consists of two units, one dealing specifically with different possible strategies that might be envisaged for an algorithmic solution to a problem, either exactly or approximately, and the other with presenting in a rigorous fashion the fundamental results related to the classification of problems ((Classes P, NP, NP Problems NP - Complete, ...):
· Problem solving paradigms (24h)
· Theory of Complexity (15h)
The course can be considered as an extension of the “Algorithms” unit of the Common curriculum course in Computer Science and of the Operational Research unit in the core curriculum course in Mathematics.
Obviously it is closely linked to the Computer Science major since it aims to provide an algorithmic and methodological basis for all computing approaches to the effective solving of concrete problems.
The solution techniques presented in the “High performance computing” course, in particular with regard to parallel programming, can be seen as additional problem solving paradigms and form therefore a natural and useful extension of the course.
It is complementary to the “Artificial Intelligence” Toolbox which deals with other approaches for problem solving, and opens up the topic towards other more up-dated fields of computer science.
The Toolbox is also a natural and complementary extension of the “Operational Research and Decision Support Tools” Toolbox, which doesn’t deal directly with the complexity aspects of algorithms but presents several other conceptual and methodological approaches to discrete problems (modelling, optimisation, simulation, multi-criteria analysis, ..)