Математическая логика и теория алгоритмов. Стенюшкина В.А. - 85 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

Различие между жадными алгоритмами и динамическим программиро-
ванием состоит в том, что жадный алгоритм учитывает на каждом шаге только
имеющуюся ситуацию, а алгоритм динамического программирования прежде,
чем сделать выбор, просчитывает продолжение всех вариантов.
A
9 11
C 10 E
4 5
1 2
D
F 6 7 G
8 3
B
Рисунок 4.5
Если задача порождает множество подзадач, то, как правило, необходимо
динамическое программирование. Например, непрерывная задача о рюкзаке
решается с помощью жадного алгоритма, а дискретная
− динамического про-
граммирования. Напомним дискретную задачу о рюкзаке: имеется n вещей сто-
имостями c
i
и весами v
i
, i=1..n. Требуется отобрать вещи с наибольшей общей
стоимостью и общим весом
≤ V. В случае непрерывной задачи вес v
i
произво-
лен для каждого i=1..n.
4.6.1 Равномерные и неравномерные коды
Допустим, строится посимвольный двоичный код, то есть каждый символ
кодируется конечный битовой последовательностью, называемый кодовым
словом. Если все кодовые слова имеют одинаковую длину, код называется рав-
номерным. Например, если длина кода 4, то можно закодировать 16 различных
символов. Для файла длина 1000 символов длина кода будет 4000. Общую дли-
ну кода файла можно сократить, если использовать неравномерный код, то есть
часто встречающиеся символы закодировать короткими битовыми последова-
тельностями, а редко встречающиеся – более длинными. Каждому двоичному
коду – равномерному и неравномерному соответствует двоичное дерево.
Пример – задана таблица кодов (таблица 4.2)
Соответствующие деревья изображены на рисунке 4.6.
Таблица 4.2
Символ a b c d e f 
      Различие между жадными алгоритмами и динамическим программиро-
ванием состоит в том, что жадный алгоритм учитывает на каждом шаге только
имеющуюся ситуацию, а алгоритм динамического программирования прежде,
чем сделать выбор, просчитывает продолжение всех вариантов.

                                       A

                          9                         11
                     C                 10                E
                          4                          5
                     1                                   2
                                       D
                     F         6            7            G

                           8                        3


                                                B

                          Рисунок 4.5

      Если задача порождает множество подзадач, то, как правило, необходимо
динамическое программирование. Например, непрерывная задача о рюкзаке
решается с помощью жадного алгоритма, а дискретная − динамического про-
граммирования. Напомним дискретную задачу о рюкзаке: имеется n вещей сто-
имостями ci и весами vi, i=1..n. Требуется отобрать вещи с наибольшей общей
стоимостью и общим весом ≤ V. В случае непрерывной задачи вес vi произво-
лен для каждого i=1..n.

                4.6.1 Равномерные и неравномерные коды

      Допустим, строится посимвольный двоичный код, то есть каждый символ
кодируется конечный битовой последовательностью, называемый кодовым
словом. Если все кодовые слова имеют одинаковую длину, код называется рав-
номерным. Например, если длина кода 4, то можно закодировать 16 различных
символов. Для файла длина 1000 символов длина кода будет 4000. Общую дли-
ну кода файла можно сократить, если использовать неравномерный код, то есть
часто встречающиеся символы закодировать короткими битовыми последова-
тельностями, а редко встречающиеся – более длинными. Каждому двоичному
коду – равномерному и неравномерному соответствует двоичное дерево.
      Пример – задана таблица кодов (таблица 4.2)
      Соответствующие деревья изображены на рисунке 4.6.
      Таблица 4.2
     Символ           a            b            c            d   e      f

Страницы