The lecture discusses computational problems and their complexity with applications in the analysis of networks. It has has three mostly self-contained parts.
In the first part, the problem of finding network modules is discussed in some detail. A module is a group of nodes with many links among group members and relatively few links with others. In a social network, for example, modules may represent groups of people with similar interests. An optimal partition of a network into modules is an example of a difficult optimization problem, for which no efficient algorithm is known. The meaning of efficient is that the maximum (worst case) time for finding an exact solution is bounded by a polynomial in the size of the graph.
The second part deals with problems that can be solved efficiently (in polynomial time) and some solution strategies. Greedy, dynamic programming, local search and other fundamental types of algorithms are outlined.
Finally, we take a glance at computational complexity theory, sketching the importance of the "P versus NP" problem. P is the set of problems that can be solved efficiently. NP contains all those for which a proposed solution can be checked efficiently. P is a subset of NP. It is an open question whether the inclusion is proper: Are there any problems for which finding a solution is qualitatively more difficult than checking it? The answer would have many implications, theoretical (e.g. automatic mathematical proof construction) as well as practical (safety of cryptography). "P versus NP" is one of the seven Millenium Problems named by the Clay Mathematics Institute. http://www.claymath.org/millennium/P_vs_NP/
Esta web utiliza cookies para la recolección de datos con un propósito estadístico. Si continúas navegando, significa que aceptas la instalación de las cookies.