День 7. Локальные оптимимизации, отжиг, перебор (4 января)

Лектор: [Сережа.K]
1. C++: use algorithm, -std=c++11
1. Структуры: list initialization
2. lambda, передача функций, функции в функциях
3. auto, foreach
4. set, map, unordered_set, unordered_map
5. count, accumulate, min_element, max_element, count_if, find, find_if
6. sort, unique, merge, set_intersection, set_union, set_difference
2. Локальные оптимизации
1. timus : 1128 Все степени не более 3. Разбить вершины на два подмножества так, чтобы у каждого было не более одного врага.
2. Алгоритм поиска паросочетания максимального размера
3. Приближенноё решение задачи коммивояжёра (2-приближение через MST и локальные оптимизации, устранение точек пересечения)
4. Найти трисочетание минимального веса в трехдольном графе
5. timus : 1130 Выбрать для каждого вектора ориентацию так, чтобы суммарная длина была не более L*sqrt(2)
3. Метод отжига
1. Дана функция, давайте попробуем найти локальный минимум (локальные оптимизации, несколько точек начала процесса, отжиг)
2. А функция бывает от нескольких переменных, давайте найдём локальный минимум (локальные оптимизации, несколько точек начала процесса, отжиг)
3. Задача про ферзей
4. Перебор: гамильтонов путь, решение на простых тестах
1. Шахматная доска, правило Warnsdorff'а
2. Рекурсивный перебор, перебор вершин в порядке возрастания степени
3. Идти в одну из двух первых вершин, запускаться несколько раз
4. Отсечение запоминанием, отсечение по связности, отсечение по времени