Господа,

 

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

 

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

Большое спасибо.

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

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

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

 

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

 

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

 

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

 

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

 

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

 

 

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

 

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

 

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

 

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

 

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

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

struct item2 {
    int data;
    struct item2 *next;
};
struct item1 {
    struct item2 *head;
    struct item1 *next;
};
struct item1 *head;

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

 

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

1. Вставить элемент;

2. Извлечь максимальный элемент;

3. Проверить на пустоту;

причём первая и вторая операция выполняются за время O(log N), где N -- число элементов в куче. При реализации кучи данные хранятся в массиве A длины N таким образом, что для каждого i одновременно выполняются два условия:

1) если 2 * i + 1 < N, то A >= A[2 * i + 1];

2) если 2 * i + 2 < N, то A >= A[2 * i + 2].

При добавлении элемента он вставляется в конец и выполняется "просеивание наоборот", максимальный элемент забирается с верхушки кучи, меняется на последний и выполняется просеивание. См. пирамидальную сортировку.

Спасибо большое за помощь!

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

 

И что такое задачи с коммивояжером и т.п. ?:) Я, честно говоря, первый раз такое вижу :)

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

27. Классические переборные задачи. Задача коммивояжера.

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

 

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

 

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

 

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

 

---------------------------------------------------------

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

Т.е. в 26-м билете достаточно сказать то, что написали Вы,

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

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

int A[N][N]; // матрица смежности
int start; // начальная вершина
int bestpath[N + 1], bestlength = -1;
void salesman(int curr, int currlen, int count, int currpath[N]) // решение задачи коммивояжёра полным перебором
{ // curr -- номер текущей вершины, currlen -- длина текущего пути, count -- кол-во вершин в текущем пути, currpath -- текущий путь
    int i;
    if (count == N && A[curr][start] && (bestlength == -1 || currlen + A[curr][start] < bestlength))
    { // если все вершины пройдены, из текущей есть ребро до начальной и длина лучше всех, что были раньше
        for (i = 0; i < count; i++)
            bestpath[i] = currpath[i];
        bestpath[count] = start;
        bestlength = currlen;
        return;
    }
    if (bestlengh != -1 && currlength > bestlength) // если текущая длина уже стала хуже лучшей -- дальше искать нет смысла
        return;
    visited[curr] = 1;
    currpath[count] = curr;
    for (i = 0; i < N; i++) // стандартный цикл обхода в глубину
        if (!visited[i] && A[curr][i])
            salesman(i, currlen + A[curr][i], count + 1, currpath);
    visited[curr] = 0;
}

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

 

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

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

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

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

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

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

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

 

 

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

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