Господа,

Приближается очередная сессия, и я снова (как обычно) готов отвечать на ваши вопросы как по моему любимому курсу методов программирования, так и по другим "околопрограммерским" или математическим курсам (в меру своей испорченностикомпетенции). Вот ссылка на аналогичную тему прошлого семестра: http://forum.academ.org/index.php?showtopic=201872

Не бойтесь, спрашивайте, если что-то непонятно. Экзамены обычно показывают, что непонятно бывает многое, к сожалению.

Вот вопрос по организационной части наверно. Вот по информационным технологиям как примерно будет оцениваться сайт который мы пишем будет оцениваться идея и дальнейшее его продвижение или всё таки больше програмная часть.?

На этот вопрос я, к сожалению, ответить не могу -- не в курсе, "не мой" предмет. Если тут есть преподаватели ИТ, они вам ответят.

Если базовый проект по "ИТ", то и то, и другое.
Если курс "ИТ", который ведёт уважаемый Мерзляков М.М., то лучше всё-таки у него лично спросить.

Не Мерзляков М.М. а Мерзляков М.А.
Вот ещё сегодня писали контрольную которую вы придумали по методам. Там 2-ое задание 1-ый пункт типо: обойти графф с помощью остовного леса. Не могли бы вы изложить алгоритм и если не трудно с примером.
Буду очень признателен!

Скорее всё-таки "построить остовный лес для данного ориентированного графа методом обхода в глубину, начиная от вершины 1"

Рассмотрим обычный обход графа в глубину (рекурсивно) с пометкой вершин в массиве int visited[N]:



Нажмите для просмотра прикрепленного файла

Скажем, на графе на первом рисунке функция dfs(1), начав обход в вершине 1 и пометив её как пройденную, перейдёт в вершину 6, пометит её и завершится (больше ни до какой вершины дойти не получится). Чтобы в конечном итоге перебрать все вершины графа, можно написать примерно такой цикл:



Тогда следующим шагом после завершения dfs(1) будет найдена следующая непосещённая вершина: 2. Из неё мы попадём в вершину 3. Пойти в 6 из 3 мы не можем, т.к. 6 уже посещена, так что этот обход здесь тоже завершается. Следующим шагом будет посещена вершина 4 (из неё мы никуда не можем пойти, всё посещено) и в самом конце -- вершина 5. На втором рисунке изображён полученный остовный лес (набор остовных деревьев).

Нажмите для просмотра прикрепленного файла

Дык вот, про "традицинно-предсессионное" как раз... У кого есть вопросы к экзаменам?!*^.^* На NT2/books воопще фиг чё найдёшь!:(

Выложил вопросы на сайте: вот они. Заодно пробежался по ним глазами и выяснил, что несколько тем забыл разобрать на лекциях; на субботней лекции все эти пробелы будут закрыты.

Ну ничего ужасного в вопросах я не заметил. Штук пять мы не разбирали, это правда, но обо всём остальном вы нам рассказывали.

Ну это понятно. Вот сделали вы обход в глубину, обошли все 6 вершин, а как остовный лес-то построился?) Я немного не понял :-(
в visited записались же вершины 1,2,3,4,5 и 6 ?

И осветите, пожалуйста, 34 35 и 36 вопросы. Лекция у нас была полное _ .=\

В остовный лес попадают рёбра, по которым мы проходим. То есть, если идёт рекурсивный вызов dfs(i), то ребро (curr, i) попадает в остовный лес.

34. Эйлеровы циклы.

Сначала определения. Эйлеров путь -- путь в графе, который проходит по каждому ребру графа ровно один раз. Эйлеров цикл -- замкнутый эйлеров путь.

Существует простой способ определить, есть ли в данном графе эйлеров цикл или эйлеров путь. Для неориентированного графа назовём степенью вершины количество инцидентных ей рёбер (т.е. сколько рёбер с ней связано). Если в связном графе степени всех вершин чётны, то в нём есть эйлеров цикл, если есть ровно две вершины с нечётными степенями -- в графе существует эйлеров путь, который начинается и заканчивается в этих двух вершинах. Для ориентированного графа для вершин определяются полустепени входа и полустепени выхода (количество вершин, входящих и выходящих в данную вершину соответственно) и утверждается, что эйлеров цикл существует, если для каждой вершины полустепень входа совпадает с полустепенью выхода (это, конечно, более сильное утверждение, чем просто чётность степени).

Существует несколько алгоритмов построения эйлерова цикла (если известно, что он существует).

Алгоритм Флёри. Мост -- ребро, при удалении которого из графа в нём увеличивается количество компонент связности.



Алгоритм со стеком. Используется стек, в который кладутся рёбра графа.

35. Гамильтоновы циклы.

Гамильтонов цикл -- цикл, который проходит по каждой вершине графа ровно один раз.

Гамильтонов цикл в графе ищется при помощи обхода в глубину с возвратом, т.е. по сути полным перебором всех путей.

Тут ещё можно сказать, что задача поиска гамильтонова цикла наименьшей стоимости во взвешенном (помеченном) графе называется задачей коммивояжёра.

36. Динамическое программирование. Кратко можно прочитать здесь.

Расскажите пожалуйста транзитивное замыкание, а то я что то в нем запуталась

Транзитивное замыкание графа G = (V, E) -- это граф G' = (V, E') такой, что (i, j) принадлежит E' тогда и только тогда, когда в G есть путь из i в j. Если по-русски, то если в графе можно каким-либо образом пройти из одной вершины в другую, то в замыкании будет ребро между этими двумя вершинами.

Пример: для ориентированного графа, состоящего из вершин 1, 2, 3 и рёбер (3, 1) и (1, 2), транзитивным замыканием будет граф из тех же вершин 1, 2, 3 и рёбер (3, 1), (1, 2) и (3, 2) (последнее ребро -- "новое", появилось, т.к. из 3 в 2 можно пройти в исходном графе).

Строгий алгоритм построения транзитивного замыкания по сути ничем не отличается от алгоритма Флойда:


Порядок перебора вершин важен! (первой перебирается вершина, через которую мы прокладываем путь).

На тесте пользоваться этим алгоритмом не нужно, для такого маленького графа, как там, замыкание делается просто "глазами": перебираем пары вершин и смотрим, можно ли пройти из одной в другую. Если можно, рисуем (дорисовываем) ребро.

Большое спасибо.
Задачи сложные будут? Я лошара, на 16 всего написал %( А переписать на 18 сказали не дадут, чтобы от задач освободили.

Да нет, не очень сложные. Правда, бывают иногда громоздкие задачи.

Вот у меня появилось пару вопросов по второй части экзаменационных вопросов:

1)Сразу стало непонятно, что нужно рассказывать в вопросах №1 и №2.

2)В лекциях не нашёл определение иерархических списков. В связи с этим возник вопрос о реализации топологической сортировки с помощью этих списков.

3)Незнакома мне структура данных под названием «куча».

p.s. на какую часть экзам. вопросов (№1 или №2) экзаменаторы будут больше обращать внимание?

Заранее спасибо!

1. Статическое и динамическое распределение памяти. Способы доступа к данным (прямой, последовательный, индексный, косвенный). Работа с динамической памятью в Си.

Если "на пальцах", то здесь нужно сказать о том, что под определённые в программе переменные (как глобальные, так и локальные -- так называемые автоматические) память выделяется компилятором автоматически. Время жизни переменной, определённой после открывающей фигурной скобки, начинающей некоторый блок -- до конца этого блока. Если это нас не устраивает, необходимо выделять и освобождать память вручную при помощи функций malloc/realloc и затем освобождать её при помощи функции free. Память, выделенная таким образом, будет жить и после выхода из блока, в котором произошло выделение.

По поводу способов доступа к данным: здесь имеется в виду примерно следующее. Прямой доступ -- обращение к ячейке памяти, когда мы чётко знаем её адрес, например, когда мы обращаемся к обычной переменной. Косвенный доступ -- доступ через указатель, т.е. разыменование указателя: в переменной-указателе находится адрес нужного нам значения в памяти. Индексный доступ -- обращение к элементу массива a[i], когда адрес нужного значения вычисляется как сдвиг на i элементов от начала массива. Последовательный доступ -- доступ к элементам списка, когда чтобы дойти до 20го элемента, мы должны перебрать 19 предыдущих.

2. Динамические типы данных в языках программирования: организация, описание, доступ. Указатели.

Здесь нужно рассказать в общем про структуру и создание одно- и двусвязных списков, иерархических списков, деревьев, описать, как производится вставка и удаление элементов, перебор элементов.

Собственно, что касается иерархических списков -- это такой список, в каждом элементе которого хранится голова списка. Например, так:

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

По поводу кучи: куча (heap) -- структура данных, с которой вы неявно встречались в топологической сортировке. Определяется она как структура данных со следующими операциями:
1. Вставить элемент;
2. Извлечь максимальный элемент;
3. Проверить на пустоту;
причём первая и вторая операция выполняются за время O(log N), где N -- число элементов в куче. При реализации кучи данные хранятся в массиве A длины N таким образом, что для каждого i одновременно выполняются два условия:
1) если 2 * i + 1 < N, то A[i] >= A[2 * i + 1];
2) если 2 * i + 2 < N, то A[i] >= A[2 * i + 2].
При добавлении элемента он вставляется в конец и выполняется "просеивание наоборот", максимальный элемент забирается с верхушки кучи, меняется на последний и выполняется просеивание. См. пирамидальную сортировку.

Спасибо большое за помощь!
А можно просто сказать, что куча - это и есть динамическая память? Или это неправильно?

И что такое задачи с коммивояжером и т.п. ? Я, честно говоря, первый раз такое вижу
26. Классические переборные задачи. Коммивояжер, рюкзак, устойчивые бракосочетания. Способы их решения (обзорно).
27. Классические переборные задачи. Задача коммивояжера.

Не путайте две разные кучи. Куча как часть памяти, доступной программе для выделения блоков (malloc, realloc, calloc) и освобождения (free) -- это одно. Куча как структура данных (стек, очередь, дек, куча) -- это другое (то, что я описал выше).

Теперь по классическим задачам. Задача коммивояжёра -- задача поиска гамильтонова цикла наименьшей длины во взвешенном неориенированном графе. Традиционно формулируется так: есть набор городов и указаны стоимости перелёта между городами. Коммивояжёру необходимо объехать все города ровно по одному разу и вернуться, затратив при этом минимально возможное количество денег. Точное решение задачи коммивояжёра можно найти только перебором с откатом.

Задача о ранце или о рюкзаке обычно формулируется так. Есть набор предметов, каждый из которых имеет массу и стоимость. Нужно выбрать из этого набора несколько предметов, суммарная масса которых не превосходит M, так, чтобы суммарная стоимость их была максимальной. Решается либо перебором (простая рекурсия), либо (заметно быстрее) динамическим программированием (таблица заполняется по увеличению массы и количества предметов).

Задача об устойчивых браках -- задача о поиске максимального паросочетания в двудольном графе. Граф называется двудольным, если его можно правильно раскрасить в два цвета. Другими словами, если множество вершин делится на две части (доли) так, что любое ребро соединяет вершину из одной доли с вершиной из другой доли. Паросочетанием в двудольном графе называется множество рёбер, не имеющих общих вершин.* Так вот, в задаче требуется найти максимальное по количеству рёбер паросочетание в данном двудольном графе. Это можно понимать так (задача об устойчивых браках, или задача об игре "Любовь с первого взгляда", если угодно): есть несколько мужчин и несколько женщин, у каждого есть некоторые предпочтения по поводу противоположного пола (один или несколько человек). Какое максимальное количество пар можно выделить, уважая предпочтения каждого участника? Задача легко решается перебором, плюс есть более простой алгоритм (сложности N^3), который вам на лекциях не рассказывали (и на экзамене спрашивать его не будут).

---------------------------------------------------------
* Вообще говоря, понятие паросочетания можно аналогичным образом ввести для произвольного графа.

Т.е. в 26-м билете достаточно сказать то, что написали Вы,
а в 27-м нужно первую задачу еще и решить этим самым "перебором с откатом"? Хы.

Не вполне: я тут не полные ответы на экзамене пишу, а только указываю направление, в котором надо развиваться мысли Хотя меня самого такие ответы бы удовлетворили (как многие знают, я вообще с небольшим интересом отношусь к ответу по билету). А что касается перебора с откатом -- это же обычный dfs (см. выше), в котором в конце добавлена одна строчка visited[curr] = 0. Тем самым перебор всех достижимых вершин сразу превращается в перебор всех возможных путей (ничего сложного также нет в сохранении текущего пути), а из перебора всех путей сделать поиск гамильтонова цикла наименьшей длины тоже ничего сложного. Как-то примерно так:

(писал прямо тут, не компилировал и не запускал, но идея должна быть понятна)

Но по умолчанию должно быть достаточно уметь описать алгоритм, а код писать уже по требованию экзаменатора.

Хм, нам Куртов сегодня на консультации сказал ,что задач про коммивояжеров и всякие браки нету в программе обучения, а значит и не будет на экзамене О_о

Может, и не будет. Знать-то всё равно надо. Я исходил из предположения, что билеты не менялись с прошлого года (если они менялись, то как-то мимо меня )

Как реализовать с помощью иерархических списков топологическую сортировку? часть два, вопрос 6.

А в чём проблема? Граф храним как список смежности, в каждой вершине для удобства можно также хранить количество входящих в неё рёбер.

В этом билете надо про вагончики рассказать? Типо такого?

Нажмите для просмотра прикрепленного файла

Это, наверное, еще и в 8м билете можно рассказать, там где "Динамическая структура со списками дуг."

Да-да-да-да. Да там многие билеты так или иначе пересекаются.

ну тогда гуд лак нам завтра :cry:

все было не так уж и страшно

Мде, меня прогнали почти по всему курсу... Успела даже испугаться, что плакала моя пятерка Хорошо хоть, двусвязных компонент не спросили, я так и не поняла алгоритм их поиска О_о

Советую-таки разобраться по теории -- там на самом деле весьма красивый алгоритм. Радует, что из года в год несколько один-два человека в группе его таки понимают

Ну и хочется отдельно поздравить "своих" с получением именно тех оценок, которые вы должны были получить

Ага, я, кстати. целый час до экзамена искала человека, который его понимал бы... не получилось
Кстати, по теории с твоего сайта я разобраться тоже не смогла. Хотя честно пыталась несколько раз

А насчет оценок... кажется, Сашка на тебя теперь очень злая ;)

Я только могу повторить про получение тех оценок, которые вы должны были получить. Я специально обе ведомости (А1 и А2) посмотрел и был приятно удивлён адекватностью оценок. Так что обижаться недовольным студентам надо в первую очередь на себя: мне кажется, оценки замечательно отражают работу в семестре и знания. Я же тоже разговаривал с экзаменаторами и знаю, кто как отвечал

Что касается точек сочленения, Сергей Нестеров, думаю, может тебе всё объяснить при желании.