Комбинаторика и теория графов 2014 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Домашние задания)
(Практика)
Строка 10: Строка 10:
  
 
Четверг, 4 пара
 
Четверг, 4 пара
 +
 +
'''Формат заголовков''' писем с домашними работами у подгрупп '''Александра Кнопа''':
 +
* Комбинаторика:<!--
 +
--><p><Имя> <Фамилия> домашнее задание DM-MAU <дата занятия, когда задали в формате дд.мм.гггг></p>
 +
* Графы:<!--
 +
--><p><Имя> <Фамилия> домашнее задание GT-MAU <дата занятия, на котором задали, в формате дд.мм.гггг></p>
  
 
==== Комбинаторика ====
 
==== Комбинаторика ====

Версия 19:21, 9 октября 2014

Лекции

Омельченко Александр Владимирович

Четверг, 3 пара

Практика

Краско Евгений Сергеевич, Кноп Александр

Четверг, 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

Теория графов

Домашние задания
  • (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

Программы считывают данные из стандартного потока ввода, печатают результат в стандартный поток вывода (всё в оговорённом формате). Обе программы должны работать за линейное время. Программы должны быть взаимно-обратны в следующем смысле: при перенаправлении вывода одной на ввод другой, должно получаться исходное дерево/код. Проверять поступающие данные на правильность не надо: считайте, что вводимые данные корректны.