1. Intensywny miniwykład prowadzony przez prof. Andrzeja Pelca z Université du Québec en Outaouais,
2. w terminie 20.04-30.04.2020. Przedmiot polecany dla studentów II stopnia i doktorantów.
3.  
4. Wykład odbędzie się w języku polskim, chyba że słuchacze zażyczą sobie inaczej.
5. Uwaga: zapisy na ten przedmiot będą otwarte do 30.04, tzn. że do tego czasu można dowolnie wypisywać/dopisywać się.
6.  
7. The subject of this lecture is the design and analysis of algorithms working with incomplete knowledge of the environment.
8. Typical examples of algorithmic domains where this occurs are distributed algorithms,
9. where incompleteness of knowledge comes from the fact that the input is distributed among processors,
10. and on-line algorithms where lack of knowledge concerns future events.
11. Data available to processing units executing the algorithm may also be unreliable,
12. due to possible faults of environment components.
13. We will investigate the impact of unreliable or incomplete information processed by algorithms on their performance,
14. and design algorithms working efficiently in the presence of faults, or in spite of incomplete knowledge of the environment.
15. In order to show diverse scenarios in which processing of incomplete information can occur,
16. we will focus on the following topics: algorithms with advice, algorithms for mobile agents,
17. and players strategies in the Iterated Prisonner's Dilemma.
18.  
19.  
20. In the first topic,we establish trade-offs between the amount of information about the environment (called advice) supplied to nodes of a network or to mobile agents, and the efficiency of performing a given task, such as communication, leader election, graph coloring, network exploration, or gathering of agents. The advice paradigm permits to measure the minimum amount of information sufficient for a given task, regardless of the type of this information, which can concern numerical parameters of the network, such as the diameter or the number of nodes, or provide knowledge about network topology or other features of the environment.
21.  
22. In the second topic, we investigate efficient algorithms for such tasks as exploration and mapping of a (partially) unknown environment (network or terrain) by mobile agents, gathering all agents in one location, finding a target by a mobile agent, and others, under various restrictions on perceptive and moving capabilities of the agents, on their communication capabilities and on their memory size. In applications, mobile agents can be either mobile robots navigating through corridors of a building or of a contaminated mine, or software agents operating in a computer network. We will investigate the impact of various degrees of asynchrony in the moves of mobile agents and the impact of possible faults in their functioning on the feasibility and performance of tasks that they have to accomplish.
23.  
24. The third topic concerns the design of good strategies for the Iterated Prisonner's Dilemma that models the problem of creating cooperation among rational agents that ignore the behavior of other agents.
25.  
26. In all three topics we will present various models and results concerning diverse tasks, and we will propose avenues of further research and many open problems. The significance of the domain of this lecture is in showing efficient ways of coping with incomplete information and of handling faults, while processing data in various computing environments.
27.