Комбинаторика и теория графов 2014 — различия между версиями
AKramar (обсуждение | вклад) (→Домашние задания) |
(→Домашние задания) |
||
| Строка 33: | Строка 33: | ||
* (11.09.14) Упражнения 1.10, 1.11, 1.12, 1.13, 1.14 и 1.17 | * (11.09.14) Упражнения 1.10, 1.11, 1.12, 1.13, 1.14 и 1.17 | ||
* (25.09.14) Упражнения 2.6, 2.7, 2.8, 2.9, 3.4 и задачи на программирование, которые нужно отправлять Евгению Краско | * (25.09.14) Упражнения 2.6, 2.7, 2.8, 2.9, 3.4 и задачи на программирование, которые нужно отправлять Евгению Краско | ||
| − | Условие: Первая программа преобразует дерево в код Прюфера. Вторая — восстанавливает по коду дерево. | + | <p style="margin-left:3em">Условие: Первая программа преобразует дерево в код Прюфера. Вторая — восстанавливает по коду дерево.<br/> |
| − | + | Формат описания дерева такой: в первой строке записано число вершин n; далее, каждая следующая строка содержит список смежности очередной вершины — последовательность номеров её соседей, разделённых пробелами. Вершины нумеруются с 0 до n-1. Например:<br/> | |
| − | Формат описания дерева такой: в первой строке записано число вершин n; далее, каждая следующая строка содержит список смежности очередной вершины — последовательность номеров её соседей, разделённых пробелами. Вершины нумеруются с 0 до n-1. Например: | + | 4<br/> |
| − | + | 1<br/> | |
| − | 4 | + | 0 2<br/> |
| − | + | 1 3<br/> | |
| − | 1 | + | 2<br/> |
| − | + | Формат описания кода Прюфера: в первой строке число вершин n, во второй — код, состоящий из n-2 позиций, разделённых пробелами. Для вышеприведённого дерева описание кода выглядит так:<br/> | |
| − | 0 2 | + | 4<br/> |
| − | + | 1 2<br/> | |
| − | 1 3 | + | |
| − | + | ||
| − | 2 | + | |
| − | + | ||
| − | Формат описания кода Прюфера: в первой строке число вершин n, во второй — код, состоящий из n-2 позиций, разделённых пробелами. Для вышеприведённого дерева описание кода выглядит так: | + | |
| − | + | ||
| − | 4 | + | |
| − | + | ||
| − | 1 2 | + | |
| − | + | ||
Программы считывают данные из стандартного потока ввода, печатают результат в стандартный поток вывода (всё в оговорённом формате). Обе программы должны работать за линейное время. Программы должны быть взаимно-обратны в следующем смысле: при перенаправлении вывода одной на ввод другой, должно получаться исходное дерево/код. Проверять поступающие данные на правильность не надо: считайте, что вводимые данные корректны. | Программы считывают данные из стандартного потока ввода, печатают результат в стандартный поток вывода (всё в оговорённом формате). Обе программы должны работать за линейное время. Программы должны быть взаимно-обратны в следующем смысле: при перенаправлении вывода одной на ввод другой, должно получаться исходное дерево/код. Проверять поступающие данные на правильность не надо: считайте, что вводимые данные корректны. | ||
| − | + | </p> | |
* (9.10.14) Упражнения 3.14, 3.15, 3.16, 3.17, 3.18, 3.19. Рекомендуется доказать 3.14 с помощью 3.17 | * (9.10.14) Упражнения 3.14, 3.15, 3.16, 3.17, 3.18, 3.19. Рекомендуется доказать 3.14 с помощью 3.17 | ||
* (17.10.14) Упражнения 4.4, 4.9, 4.10, 4.11, 4.15. Также из двух похожих упражнений 4.13 и 4.14 выберите то, которое вы не решали в своей группе на практике, и решите его. | * (17.10.14) Упражнения 4.4, 4.9, 4.10, 4.11, 4.15. Также из двух похожих упражнений 4.13 и 4.14 выберите то, которое вы не решали в своей группе на практике, и решите его. | ||
Версия 12:40, 21 октября 2014
Содержание
Лекции
Омельченко Александр Владимирович (avo.travel@gmail.com)
Четверг, 3 пара
Практика
Краско Евгений Сергеевич (krasko.evgeniy@gmail.com), Кноп Александр (aaknop@gmail.com)
Четверг, 4 пара
Формат заголовков писем с домашними работами у подгрупп Александра Кнопа:
- Комбинаторика:
<Имя> <Фамилия> домашнее задание DM-MAU <дата занятия, когда задали в формате дд.мм.гггг>
- Графы:
<Имя> <Фамилия> домашнее задание GT-MAU <дата занятия, на котором задали, в формате дд.мм.гггг>
Комбинаторика
Домашние задания
- (4.09.14) Задачи
- (18.09.14) Упражнения 2.7, 2.9, 3.6, 3.7, 3.8, 3.9, 3.10
- (2.10.14) Упражнения 5.2, 5.10, 5.11, 5.12
- (16.10.14) Упражнения 6.1, 6.2, 6.3, 6.5, 6.6, 6.8, 6.10
Теория графов
Домашние задания
- (11.09.14) Упражнения 1.10, 1.11, 1.12, 1.13, 1.14 и 1.17
- (25.09.14) Упражнения 2.6, 2.7, 2.8, 2.9, 3.4 и задачи на программирование, которые нужно отправлять Евгению Краско
Условие: Первая программа преобразует дерево в код Прюфера. Вторая — восстанавливает по коду дерево.
Формат описания дерева такой: в первой строке записано число вершин n; далее, каждая следующая строка содержит список смежности очередной вершины — последовательность номеров её соседей, разделённых пробелами. Вершины нумеруются с 0 до n-1. Например:
4
1
0 2
1 3
2
Формат описания кода Прюфера: в первой строке число вершин n, во второй — код, состоящий из n-2 позиций, разделённых пробелами. Для вышеприведённого дерева описание кода выглядит так:
4
1 2
Программы считывают данные из стандартного потока ввода, печатают результат в стандартный поток вывода (всё в оговорённом формате). Обе программы должны работать за линейное время. Программы должны быть взаимно-обратны в следующем смысле: при перенаправлении вывода одной на ввод другой, должно получаться исходное дерево/код. Проверять поступающие данные на правильность не надо: считайте, что вводимые данные корректны.
- (9.10.14) Упражнения 3.14, 3.15, 3.16, 3.17, 3.18, 3.19. Рекомендуется доказать 3.14 с помощью 3.17
- (17.10.14) Упражнения 4.4, 4.9, 4.10, 4.11, 4.15. Также из двух похожих упражнений 4.13 и 4.14 выберите то, которое вы не решали в своей группе на практике, и решите его.
