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

Материал из SEWiki
Перейти к: навигация, поиск
м
 
(не показано 27 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
== Лекции ==
 
== Лекции ==
Омельченко Александр Владимирович
+
Омельченко Александр Владимирович (<b>avo.travel@gmail.com</b>)
 +
 
 
Четверг, 3 пара
 
Четверг, 3 пара
  
==== Комбинаторика ====
+
*[https://drive.google.com/folderview?id=0B-4BALGaSccuX3BFRUFISE42Vkk&usp=sharing| Папка с лекциями]
*[https://drive.google.com/file/d/0B-4BALGaSccuYXlxZ2YzTHg0dlE/edit?usp=sharing| Лекция 4.09.14]
+
==== Теория графов ====
+
*[https://drive.google.com/file/d/0B-4BALGaSccucmVMb3lNeUVFb0k/edit?usp=sharing| Лекция 11.09.14]
+
  
 
== Практика ==
 
== Практика ==
Краско Евгений Сергеевич, Кноп Александр
+
Краско Евгений Сергеевич (<b>krasko.evgeniy@gmail.com</b>), Кноп Александр (<b>aaknop@gmail.com</b>)
 +
 
 
Четверг, 4 пара
 
Четверг, 4 пара
 +
 +
'''Формат заголовков''' писем с домашними работами у подгрупп '''Александра Кнопа''':
 +
* Комбинаторика:<!--
 +
--><p><Имя> <Фамилия> домашнее задание DM-MAU <дата занятия, когда задали в формате дд.мм.гггг></p>
 +
* Графы:<!--
 +
--><p><Имя> <Фамилия> домашнее задание GT-MAU <дата занятия, на котором задали, в формате дд.мм.гггг></p>
  
 
==== Комбинаторика ====
 
==== Комбинаторика ====
===== Результаты =====
 
 
* [https://docs.google.com/spreadsheets/d/1qPA6dPa_Sz249A1NwvfYDhrwdLDdvmqdLM4mLgpN6Dw/edit#gid=0| Результаты (комбинаторика)]
 
* [https://docs.google.com/spreadsheets/d/1qPA6dPa_Sz249A1NwvfYDhrwdLDdvmqdLM4mLgpN6Dw/edit#gid=0| Результаты (комбинаторика)]
 +
Для получения зачета (допуска) надо набрать от 45 баллов и решить ряд задач из пока не заданного домашнего задания.
 +
===== Домашние задания  =====
  
===== Домашнее задание 1 (4.09.14) =====
+
* (4.09.14) [https://drive.google.com/file/d/0B-4BALGaSccuTkhIaFpweHcyd28/edit?usp=sharing| Задачи]
[https://drive.google.com/file/d/0B-4BALGaSccuTkhIaFpweHcyd28/edit?usp=sharing| Задачи]
+
* (18.09.14) Упражнения 2.7, 2.9, 3.6, 3.7, 3.8, 3.9, 3.10
===== Домашнее задание 2 (18.09.14) =====
+
* (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
 +
* Упражнения 8.3, 8.8
 +
* (18.11.2014) 9.7, 9.9, 10.1, 10.5, 10.7, 10.9, 10.10
 +
* (15.12.14) 11.6, 11.8, 11.9
  
 
==== Теория графов ====
 
==== Теория графов ====
 
* [https://docs.google.com/spreadsheets/d/1IiuE9cxeZ9QF17CpT0a0n0H7bq0U6M6SNm7fyiEsKDs/edit#gid=0| Результаты (теория графов)]
 
* [https://docs.google.com/spreadsheets/d/1IiuE9cxeZ9QF17CpT0a0n0H7bq0U6M6SNm7fyiEsKDs/edit#gid=0| Результаты (теория графов)]
 +
Для получения зачета (допуска) необходимо набрать более 30 баллов.
 +
 +
===== Домашние задания =====
 +
* (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 и задачи на программирование, которые нужно отправлять Евгению Краско
 +
<p style="margin-left:3em">Условие: Первая программа преобразует дерево в код Прюфера. Вторая — восстанавливает по коду дерево.<br/>
 +
Формат описания дерева такой: в первой строке записано число вершин n; далее, каждая следующая строка содержит список смежности очередной вершины — последовательность номеров её соседей, разделённых пробелами. Вершины нумеруются с 0 до n-1. Например:<br/>
 +
4<br/>
 +
1<br/>
 +
0 2<br/>
 +
1 3<br/>
 +
2<br/>
 +
Формат описания кода Прюфера: в первой строке число вершин n, во второй — код, состоящий из n-2 позиций, разделённых пробелами. Для вышеприведённого дерева описание кода выглядит так:<br/>
 +
4<br/>
 +
1 2<br/>
 +
Программы считывают данные из стандартного потока ввода, печатают результат в стандартный поток вывода (всё в оговорённом формате). Обе программы должны работать за линейное время. Программы должны быть взаимно-обратны в следующем смысле: при перенаправлении вывода одной на ввод другой, должно получаться исходное дерево/код. Проверять поступающие данные на правильность не надо: считайте, что вводимые данные корректны.
 +
</p>
 +
* (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 выберите то, которое вы не решали в своей
 +
группе на практике, и решите его.
 +
* (13.11.2014) 4.20 – 4.22. Пользуйтесь результатом упражнения 4.19.
 +
* (25.11.2014) 5.13, 5.14, 5.15, 5.16, 5.17, 5.19
 +
* (15.12.14) 6.8, 6.9, 6.10
 +
  
===== Домашнее задание 1 (11.09.14) =====
+
[[Category:5 курс. Осень 2014]]
Упражнения 1.10, 1.11, 1.12, 1.13, 1.14 и 1.17
+

Текущая версия на 12:30, 15 февраля 2015

Лекции

Омельченко Александр Владимирович (avo.travel@gmail.com)

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

Практика

Краско Евгений Сергеевич (krasko.evgeniy@gmail.com), Кноп Александр (aaknop@gmail.com)

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

Формат заголовков писем с домашними работами у подгрупп Александра Кнопа:

  • Комбинаторика:

    <Имя> <Фамилия> домашнее задание DM-MAU <дата занятия, когда задали в формате дд.мм.гггг>

  • Графы:

    <Имя> <Фамилия> домашнее задание GT-MAU <дата занятия, на котором задали, в формате дд.мм.гггг>

Комбинаторика

Для получения зачета (допуска) надо набрать от 45 баллов и решить ряд задач из пока не заданного домашнего задания.

Домашние задания
  • (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
  • Упражнения 8.3, 8.8
  • (18.11.2014) 9.7, 9.9, 10.1, 10.5, 10.7, 10.9, 10.10
  • (15.12.14) 11.6, 11.8, 11.9

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

Для получения зачета (допуска) необходимо набрать более 30 баллов.

Домашние задания
  • (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 выберите то, которое вы не решали в своей

группе на практике, и решите его.

  • (13.11.2014) 4.20 – 4.22. Пользуйтесь результатом упражнения 4.19.
  • (25.11.2014) 5.13, 5.14, 5.15, 5.16, 5.17, 5.19
  • (15.12.14) 6.8, 6.9, 6.10