65. Почему задача о рюкзаке, являясь np-полной, имеет эффективные алгоритмы решения?

В п.2.1 уже отмечалось, что в качестве аргумента оценок эффективности следует использовать не расплывчатое понятие «размерность задачи», а четко определенное «длина описания задачи». Однако как связан параметр объема рюкзака B с длиной соответствующей задачи |z|? Поскольку B – целое число, а длина любой разумной кодировки числа пропорциональна логарифму этого числа, то при фиксированном n имеем: |z| = O(log(B)), откуда получаем: B = O(2|z|). Значит, полиномиальная относительно B оценка эффективности алгоритма Беллмана является на самом деле экспоненциальной относительно |z|. Но если алгоритм экспоненциальный, то почему он столь эффективен? Дело в том, что существенное замедление работы алгоритма будет ощущаться только при очень больших значениях B. Заметим, что увеличение длины описания задачи на каких-то 20 битов позволяет задать в 1000000 раз большее значение B! Конечно, такая задача будет за пределами практической разрешимости.

66. Что такое псевдополиномиальный алгоритм?

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

67. Что такое ориентированный и неориентированный граф?

Ориентированный-граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами

Неориентированный-граф G(V,E) для которого выполнены след условия:

1. V - это не пустое множество вершин

2.Е-это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

68. Что такое матрица смежности графа? Сколько в ней строк и сколько столбцов?

матрица смежности n*n содержит 0 и 1(там где есть связь)

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ijравно числу ребёр из i-й вершины графа в j-ю вершину.

69. Чем отличается матрица смежности ориентированного графа от неориентированного?

Для неор. графа она симметричная

70. Что такое матрица инцидентности графа? Сколько в ней строк и сколько столбцов?

Размерность (n*m) в каждом столбце только 2 единицы, каждый столбец – ребро, единица – вершина инцидентная ему(это неудобная форма=> не используется) m – кол-во ребер, n – кол-во вершин

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

Для редких графов, потому что они разреженные (мало связей)

72. Что такое дерево? Сколько ребер имеет дерево?

Связный граф без циклов. Кол-во ребер m=(n-1)

73. Чем отличается поиск по графу в глубину от обхода дерева?

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

74. Что такое остовное дерево? В каких случаях оно содержит все вершины графа?

Дерево включающее все вершины графа, подмн-во ребер (это подмножество ребер, которое образует дерево,включает все его вершины)

75. Как можно проверить связность графа?

Поиском в глубину: Если при обходе в глубину, запущенным из любой вершины графа будут отмечены как пройденные все вершины графа - граф связный.

76. Что такое ациклический ориентированный граф и чем он отличается от дерева?

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

77. В чем заключается алгоритм проверки ацикличности ориентированного графа?

Пускаем обход в глубину по каждой компонетне связности - если мы хоть раз пришли в ту же вершину, в которой уже были - цикл.

78. Что такое топологическая сортировка? К каким графам она применима?

Возьмем классическую задачу на топологическую сортировку. Есть студент, ему нужно обойти для вселения в общагу кучу врачей, при этмо для каждого врача ему известен список справок, который нужен этому врачу от других врачей. Собственно получается граф, где вершина - врач, а связь из А в Б - необходимость наличия справки одному Б от врача А. Таким образом, студент может “войти в вершину” Х только тогда, когда уже обошел все вершины, из которых в Х ведет связь. Задача - найти такой порядок вершин, в котором студент может обойти всех врачей. Этот порядок - и есть топологически отсортированный граф.

Другой вариант - нужно так расположить вершины графа в одну линию, чтобы все связи вели слева направо.

Применима - к ориентированным ациклическим.

ациклический ориентированный граф топологически отсортирован, если вершина пронумерованы от меньшей к большему слева направо

79. В чем заключается алгоритм топологической сортировки?

Заходим в вершины -> рекурсия всех потомков -> выходим из вершины и считаем условное время выхода из нее

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

80. Для чего может быть полезна топологическая сортировка?

Для нахождения минимального пути Т(n,m)=O(n+m)

81. Что такое сильно связный граф? К каким графам применимо это понятие – ориентированным или неориентированным?

Орграф сильно связный, если из любой его вершины имеется ор. путь из одной вершины в другую

82. Что такое поиск по графу в ширину и чем он отличается от поиска в глубину?

При поиске в ширину мы рассматриваем все вершины смежные с данной и для запоминания используем очередь вместо массива посещенных вершин

83. Какую задачу решает алгоритм Прима и в чем идея этого алгоритма?

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

84. Какую задачу решает алгоритм Крускала и в чем идея этого алгоритма?

задача построение кратчайшего остовного дерева. на каждом шаге включаем одно ребро, но не обязательно связное, из принциа “жадности” минимально динное (но не замыкаем цикл, сяитаем, что из n-1 ребра не получили цикл=> связность=>дерево). выполним сортировку и берем ребро (но чтобы не было цикла - просо пропускаем ребра замыкающие цикл и не будем возвращаться)

85. В каких случаях алгоритм Крускала предпочтительнее, чем алгоритм Прима?

лучше для числа ребер ограничено => n пропорционально m(если много вершин но мало ребер используем алг крускала)

86. Какую задачу решает алгоритм Флойда и в чем идея этого алгоритма?

поиск кратчайшего пути между вершинами. ВСЕМИ ПАРАМИ ВЕРШИН (Я НЕ ПРОВЕРЯЛ ЧТО НАПИСАНО ДАЛЬШЕ :)

дан орграф (ограничение - нет ребер отриц длины), дана матрица длин ребер, если ребра нет то на его месте бесконечность {bij} требуется построить матрицу кратчайших путей {lij}

1) lij=bij для любых ij

2) lij:=min(lij, lik+lkj)

87. Какую задачу решает алгоритм Дейкстры и в чем идея этого алгоритма?

поиск кратчайшего пути между вершинами. ИЗ ОДНОЙ ВЕРШИНЫ ВО ВСЕ ОСТАЛЬНЫЕЯ НЕ ПРОВЕРЯЛ ЧТО НАПИСАНО ДАЛЬШЕ :)

дан орграф (ограничение - нет ребер отриц длины), дана матрица длин ребер, если ребра нет то на его месте бесконечность {bij}даны вершины А и В найти l(A,B) (b>=0)

изначально считаем. что вершины бесконечно далеки от А(пока точное не известно). на каждом шаге добавляем 1 окончательное расстояние до некоторой вершины если это В то заканчиваем.

88. Какова трудоемкость алгоритмов Флойда и Дейкстры?

Флойда:O(n³)=T(n*m); Дейкстры: O(n²)=T(n*m) ДЕЙКСТРУ МОЖНО УЛУЧШИТЬ ДО МlogN в среднем, но об этом знать не обязательно

89. Для какого типа графов задача поиска самого длинного пути имеет эффективное решение?

для ациклических

90. Что такое критический путь в ациклическом графе?

Путь максимальной длины

91. Что такое поток в сети?(см алгоритм Форда-Фалкерсона) смотрим википедию

Потоком в сети называется некоторая функция, которая ставит в соответствие дуге некоторое число-вес дуги.

92. Чем отличаются источник и сток от остальных вершин?

Любая другая вершина сети лежит на пути из S в T. Дивиргенцией

93. Каков смысл уравнений сохранения потока? Поток между любыми двумя вершинами кроме источника и стока должен быть равен нулю.

{сумма xij - сумма xki= v если i=s

-v если i=t

0

{0<=xij<=qij

94. Что такое величина потока?

Величина потока - сумма потоков из источника. Она же равна сумме потоков в сток.

95. Что такое аугментальная цепь?

Это такая последовательность ориентированных рёбер(такой неориентированный путь из источника в сток), в котром выполнены след. условия:

1. S=>T: qij=xij=bij>0;

2. S<=T: xij=bij>0;

3. b=min bij

96. Как можно увеличить поток, если имеется аугментальная цепь?

ищем минимальную че еще за сигма блеа сигму по цепи. если существует аугментальная цепь с сигма больше 0 то поток не максимален и его можно увеличить на сигма, если не можем найти аугментальную цепь то поток оптимален

97. В чем идея алгоритма поиска аугментальной цепи?

по алгоритму распространения пометок смотрим на изначально допустимый поток и заданную пропускную способность

98. Как определить, что поток является максимальным?

если не можем найти аугментальную цепь то поток оптимален

99. Как решать задачу о максимальном потоке при нескольких источниках?

просто вводим дополнительную вершину - наш новый источник. пропускная способность дуг идущих к реальным источникам бесконечность

100. Как решать задачу о максимальном потоке при ограниченном источнике?

введем фиктивный источник чтоб он был не ограничен и наш источник станет 1 вершиной

101. Как решать задачу о максимальном потоке при ограниченной пропускной способности вершин?

разобьем нашу вершину на 2 и дадим полученной дуге ее пропускную способность

102. Как решаются задачи о максимальном числе непересекающихся путей?

эйлеровым циклом

103. Что такое паросочетание? К каким графам применимо это понятие – ориентированным или неориентированным?

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

104. Что такое двудольный граф?

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

105. Что такое чередующаяся цепь? Что можно сказать о числе ребер такой цепи?

Чередующаяся цепь – такая последовательность ребер, которая начинается в непарной вершине одной доли и заканчивается в непарной вершине второй доли. Количество ребер в цепи нечётное,первое ребро непарное,последнее ребро непарное.

106. Как связаны задачи о максимальном потоке и о максимальном паросочетании?

задача о максимальном паросочетании в двудольном графе сводится к задаче и максимальном потоке (но этот путь не оптимален)

107. Как можно увеличить паросочетание, если известна чередующаяся цепь?

поменять местами парные и непарные

108. В чем идея алгоритма поиска чередующейся цепи в двудольном графе?

начальный шаг: построим все непарные вершины

нечетный наг:строим меожество вершин не включенных в предидущее

четный шаг:

завершение:

109. Что такое эйлеров цикл и эйлерова цепь?

эйлерова цепь - незамкнутый путь по всем ребрам между 2 заданными вершинами

эйлеров цикл - цикл ровно 1 раз проходящий каждое ребро

110. При каких условиях в графе существует эйлеров цикл или эйлерова цепь?

эйлеров цикл , если вершины связного графа четной степени

эйлерова цепь, то же только 2 конечные вершины нечетной стпени

111. В чем идея алгоритма поиска эйлерова пути?

Рекурсивный обход графа, удаляя пройденные ребра.При попадании в вершину без ребер делаем возврат из рекурсии и вкл в список цикла данную вершину

112. Что такое гамильтонов цикл и гамильтонова цепь?

цикл-(и для ор и для неор)цикл проходит в связ графе 1 раз через каждую вершину

цепь-незамкнутый путь,проходящий через все вершины 1 раз

113. Какова трудоемкость поиска эйлерова цикла и гамильтонова цикла?

T(n,m)=O(n+m)

114. Что такое хроматическое число графа?

минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета

115. Каковы максимально и минимально возможное значения хроматического числа графа?

минимальное=1, макс=N для полного графа

116. Какое максимальное хроматическое число может быть у планарного графа?

5(хроматическое число планарного графа меньше или равно 5)

117. Назовите какие-либо жадные алгоритмы раскраски графа.

118. В чем идея алгоритма неявного перебора для раскраски графа?

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

Во время второй фазы, если это возможно, получается лучшая раскраска, использующая меньшее число цветов. На первом шаге второй фазы отыскивается первая по номеру вершина, окрашенная в цвет, от которого мы хотим избавиться. И из нее осуществляется так называемый шаг возвращения, а именно:

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

А если какая-то вершина потребует — осуществим шаг возвращения из нее. В ситуации, когда та самая х-ая вершина не может быть перекрашена в другой допустимый цвет — сразу же делаем шаг возвращения из нее. Алгоритм завершает работу, если на шаге возвращения достигается первая вершина.

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

119. Что такое энтропия сообщения и как она связана с количеством информации?

Энтропия-количественная мера неопределенности потока, который попадает на кодер. Количество информации в сообщении равно его энтропии.

120. Чему равна энтропия выбора из N равновероятных возможностей?

121. Как вычисляется энтропия выбора из N неравновероятных возможностей?

122. В каком случае энтропия выбора из N возможностей максимальна? Чему она равна при этом?

Если все исходы равновероятны, P_i=1/n

123. Как влияет на энтропию сообщения наличие корреляций между соседними буквами?

124. Что такое 1 бит информации?

• единица количества данных(один двоичный разряд);

• единица количества информации.

125. Что такое префиксный код?

код, к котором не одно кодовое слово не является префиксом другого кодового слова

126. В чем преимущество префиксных кодов над непрефиксными?

127. В чем заключается неравенство Крафта?

Пусть заданы кодируемый и кодирующий алфавиты, состоящие из n и d символов, соответственно, и заданы желаемые длины кодовых слов: . Тогда необходимым и достаточным условием существования разделимого и префиксного кодов, обладающих заданным набором длин кодовых слов является выполнение неравенства:

128. В чем идея построения кодов Хаффмена?

Алгоритм Хаффмана — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 годуаспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m₂ с более чем двумя символами.

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности, что позволяет однозначно их декодировать.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). [1]

Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.

Выбираются два свободных узла дерева с наименьшими весами.

Создается их родитель с весом, равным их суммарному весу.

Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.

Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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

129. Как связана средняя длина кодовых слов Хаффмена с энтропией букв кодируемого алфавита?

130. Чем различается статическое кодирование с фиксированной моделью и с передачей модели?

аналогичны только во 2 случае сначала передаются параметры модели

131. Что такое адаптивное кодирование?

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

132. В чем идея арифметического кодирования?

Арифметическое кодирование — один из алгоритмов энтропийного сжатия.

В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов — группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов.

Немного превосходит алгоритм Хаффмана качеством сжатия, но некоторые версии имеют патентные ограничения от компании IBM

133. Как связана длина кодирующего отрезка с вероятностью кодируемого сообщения?

134. Почему более длинным кодирующим отрезкам соответствуют более короткие коды?

135. В каких случаях выполняется масштабирование отрезка при арифметическом кодировании?

136. В каких случаях выдается очередная цифра кода при арифметическом кодировании?

137. В чем общая идея алгоритмов словарного кодирования?

Сущность их состоит в том, что фразы в сжимаемом тексте заменяются указателем на то место, где они в этом тексте уже pанее появлялись.

138. В чем идея алгоритма LZSS?

139. Из каких величин состоит код, полученный по алгоритму LZSS?

140. В чем идея алгоритма LZW?

LZW - один из самых изящных алгоритмов, не использующий глубокую математическую модель и работающий в один проход. Алгоритм уступает по степени сжатия алгоритму Хаффмана и другим математическим алгортмам, но значительно превосходит RLE и аналоги. И сама идея алгоритма очень занимательна

141. Из каких величин состоит код, полученный по алгоритму LZW?

1 Чтобы избежать двусмысленности, более привычное слово «решение» используется только в смысле «процесс решения», а слово «план» – в смысле «результат решения».

2 Не пытайтесь найти глубокий смысл в названии метода. Его нет. В 50-е годы слово «программирование» означало не то, что сейчас.