Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Самарский государственный архитектурно-строительный университет Факультет информационных систем и технологий Кафедра прикладной математики и вычислительной техники

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ. Часть 2.

Курс лекций для студентов специальности 230400 – «Информационные системы и технологии»

Прохорова О.В.

01.01.2013

Рассматриваются общие требования к методологии и проектированию ПО. Приводятся основные положения алгоритмизации на примерах работы с перестановками. Разбираются аспекты применения рекурсии. Изучаются основные информационные структуры ПО. Разбираются алгоритмы и программы генерирования случайных последовательностей. Приводятся примеры конструирования программ на языке С++.

Оглавление

1. Алгоритмы на перестановках 3

2. Информационные структуры 14

3. Алгоритмы на графах 35

Литература 66

1. Алгоритмы на перестановках

   1. Введение

Понятие алгоритма является основным для всей области компьютерного программирования. Истоки понятия «алгоритм» ассоциируются с процессом нахождения наибольшего общего делителя двух чисел [3].

Алгоритм Евклида (Е). Даны два целых положительных числа m и n. Требуется найти их наибольший делитель, т.е. наибольшее целое число, которое нацело делит оба числа m и n.

Е1. [Нахождение остатка]. Разделим m на n и, пусть остаток от деления будет равен

r (где 0  r < n).

E2. [Сравнение с нулем]. Если r = 0, то выполнение алгоритма прекращается: n —

искомое значение.

Е3. [Замещение]. Присвоить m  n, n  r и вернуться к шагу Е1.

Каждый шаг любого алгоритма начинается заключенной в квадратные скобки фразой, которая как можно более кратко выражает содержание

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

В алгоритмах “” обозначает операцию замещения, например, n  n+1 (n+1  n противоречит стандартным соглашениям).

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

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

1. конечность. Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов;

2. определенность. Каждый шаг алгоритма должен быть определен;

3. ввод. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных, т.е. величин, которые задаются до начала его работы или определяются динамически во время его работы;

4. вывод. У алгоритма есть одно или несколько выходных данных, т.е. величин, имеющих вполне определенную связь с входными данными.

5. эффективность. Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени.

В дальнейшем перейдем к рассмотрению принципов, методов и алгоритмов, используемых при программировании.

2. Перестановки. Произведение перестановок

Перестановкой n объектов называется способ последовательного расположения n различных объектов с учетом порядка [1].

Например, для трех объектов {a, b, c} существует шесть перестановок

abc, acb, bac, bca, cab, cba. (1.1)

Свойства перестановок играют важную роль в анализе алгоритмов.

Поставим задачу сосчитать перестановки для n объектов. Существует n способов выбора крайнего объекта слева (первого); после того как этот выбор сделан, существует n-1 способ выбора следующего за ним объекта. Таким образом, получаем общее число перестановок равное n (n – 1) … (1).

Обозначим через количество способов выбораk объектов из n с учетом порядка.

Для прикладных целей важное значение имеет процесс построения всех перестановок из n объектов методом индукции в предположении, что все перестановки из n-1 объектов уже построены. Перепишем (1.1), заменив буквы {a, b, c} цифрами {1, 2, 3}, тогда получим следующие перестановки: 123, 132, 213, 231, 312, 321.

Зададим вопрос, как с использованием этого набора получить все возможные перестановки из четырех цифр {1, 2, 3, 4} и т.д.

Метод. Для каждой перестановки a₁ a₂ … a_n-1 из {1, 2, … n-1} объектов построим еще n перестановок, помещая число n на всевозможные места, в результате получим:

n a₁ a₂ … a_n-1 ; a₁ n a₂ … a_n-1 ; … a₁ a₂ … n a_n-1 ; a₁ a₂ … a_n-1 n

Например, для перестановки 231 получим 4231 2431 2341 2314 и т.д.

Очевидно, этот метод дает все возможные перестановки из n объектов, причем ни одна из них не повторяется. Отметим, что P_n = = n (n – 1) … (1) является очень важной математической величиной, ее называют n-факториалом и записывают

n! = 1  2  …  n = .

Отметим важные свойства факториала 0! = 1; n! = (n – 1)!  n.

В дальнейшем нам понадобится формула определения _. Приведем ее известный вид:

_.

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

(1.2)

С точки зрения переупорядочения это означает, что объект с переходит на место, которое ранее занимал объект а. А если это рассматривать как переименование, то можно считать, что объект а переименован в с. При использовании двух строчной записи изменение порядка столбцов в перестановке никакой роли не играет. Например, перестановку (1.2) можно записать в виде

,

а также еще 718 способами [1].

В связи с описанной интерпретацией часто используют циклическую запись. Перестановку (1.2) можно записать в виде

(a c f) (b d) (1.3)

Запись перестановки в виде цикла не является единственной. Например, записи

(b d) (a c f) ; (c f a)(b d) ; (d b) (f a c)

эквивалентны (1.3), а перестановка (a f c) (b d) им не эквивалентна.

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

Например, чтобы переупорядочить (1.2), т.е. присвоить

(a, b, c, d, e, f)  (c, d, f, b, e, a),

будем следовать циклической структуре (1.3) и последовательно присваивать t  a, a  c, c  f, f  t, t  b, b  d, d  t . То есть (c f a) (d b)

Замечание. Любое подобное преобразование характерно только для непересекающихся циклов.

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

(1.4)

Замечание. Произведение перестановок не обладает свойством коммутативности, т.е. , гдеи— перестановки.

Пользуясь циклической записью, запишем равенство (1.4) следующим образом:

(a c f) (b d)* (a b d) (e f) = (a c e f b) (1.5)

Рассмотрим следующий подход к перемножению перестановок, представленных в виде циклов.

Например, вычисляя произведение перестановок

(a c f g) (b c d) (a e d) (f a d e) (b g f a e) (1.6)

находим (двигаясь слева направо), что a переходит в с, d  c, a  d, d  a и d остается без изменений. Т.о. конечным результатом первого прохода формулы (1.6) является то, что d  a и мы запишем “( a d” в качестве частичного ответа. Теперь выясним, что происходит с d: b  d, g  b. Следовательно, имеем частичный результат “( a d g”.

Рассмотрев, что происходит с g, находим, что a  f  e  a  g, т.о. первый цикл заканчивается: “(a d g)”.

Теперь выберем новый элемент, который еще не встречался, например, с. Находим, что e  c … и т.д.

Окончательный ответ: (a d g) (c e b).