Понятие сложности алгоритма

Понятие сложности алгоритма Сложность ­ это количественная оценка ресурсов, затрачиваемых алгоритмом. Ресурсы:  Человеческие (создание и понимание алгоритма). Оценивает интеллектуальная  сложность. Единого критерия оценки не существует.  Вычислительные (на выполнение алгоритма):  Память. Оценивает пространственная сложность ­ количество памяти,  требующееся для выполнения алгоритма.  Процессорное время. Оценивает временная сложность ­ количество времени, необходимое на выполнение алгоритма. Если пространственная сложность поддается количественной оценке, то со временной  сложностью не все так просто ­ оценка алгоритма зависит от аппаратуры. Можно  сравнивать 2 алгоритма на одинаковой аппаратуре, но чтобы избавиться от аппаратной  зависимости используется оценка в виду функции T(n) от количества обрабатываемых  данных. Эта оценка применяется к отдельным частям алгоритма, затем комбинируется в  общую оценку. Для конкретизации этой функции используется несколько подходов. В  частности О­оценка. Оценка сложности алгоритмов Алгоритмы* Не так давно мне предложили вести курс основ теории алгоритмов в одном московском  лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на  которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю,  что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по  крайней мере интересной. Существует несколько способов измерения сложности алгоритма. Программисты обычно  сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели  – требования к объёму памяти, свободному месте на диске. Использование быстрого  алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится  больше памяти, чем есть у компьютера. Память или время Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно  решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём. Типичным примером в данном случае служит алгоритм поиска кратчайшего пути.  Представив кару города в виде сети, можно написать алгоритм для определения  кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния  между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать  кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое  расстояние из таблицы. Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта  большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица,  должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие  алгоритма, необходимо использовать дополнительные 10 Гб памяти. Из этой зависимости проистекает идея объёмно­временной сложности. При таком подходе  алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения  потреблённой памяти. Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти. Оценка порядка При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма  входных данных. Допустим, при сортировке одним методом обработка тысячи чисел  занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма  может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно  сказать, какой алгоритм лучше. В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм  имеет сложность O(f(n)), если при увеличении размерности входных данных N, время  выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим  код, который для матрицы A[NxN] находит максимальный элемент в каждой строке. for i:=1 to N do begin max:=A[i,1]; for j:=1 to N do begin if A[i,j]>max then max:=A[i,j] end; writeln(max); end; В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j  тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это  определяет сложность алгоритма O(N^2). Оценивая порядок сложности алгоритма, необходимо использовать только ту часть,  которая возрастает быстрее всего. Предположим, что рабочий цикл описывается  выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение  быстро растущей части функции позволяет оценить поведение алгоритма при увеличении  N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего  лишь 100, что составляет 0,01%. При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с  рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения  O(N) от изменения размера задачи более очевидной. Определение сложности Наиболее сложными частями программы обычно является выполнение циклов и вызов  процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов. Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на  печать), то на оценку сложности это практически не влияет. Если же в вызываемой  процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм.  Если же процедура вызывается внутри цикла, то влияние может быть намного больше. В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со  сложностью O(N^2). procedure Slow; var i,j,k: integer; begin for i:=1 to N do for j:=1 to N do for k:=1 to N do {какое­то действие} end; procedure Fast; var i,j: integer; begin for i:=1 to N do for j:=1 to N do Slow; end; procedure Both; begin Fast; end; Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то  сложности процедур перемножаются. В данном случае сложность алгоритма составляет  O(N^2 )*O(N^3 )=O(N^5). Если же основная программа вызывает процедуры по очереди, то их сложности  складываются: O(N^2 )+O(N^3 )=O(N^3). Следующий фрагмент имеет именно такую  сложность: procedure Slow; var i,j,k: integer; begin for i:=1 to N do for j:=1 to N do for k:=1 to N do {какое­то действие} end; procedure Fast; var i,j: integer; begin for i:=1 to N do for j:=1 to N do {какое­то действие} end; procedure Both; begin Fast; Slow; end; Сложность рекурсивных алгоритмов Простая рекурсия Напомним, что рекурсивными процедурами называются процедуры, которые вызывают  сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов  зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно  усложнить программу, многократно вызывая себя. Рассмотрим рекурсивную реализацию вычисления факториала: function Factorial(n: Word): integer; begin if n > 1 then Factorial:=n*Factorial(n­1) else Factorial:=1; end; Эта процедура выполняется N раз, таким образом, вычислительная сложность этого  алгоритма равна O(N). Многократная рекурсия Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной  рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут  сделать алгоритм гораздо сложнее. Рассмотрим такую процедуру: procedure DoubleRecursive(N: integer); begin if N>0 then begin DoubleRecursive(N­1); DoubleRecursive(N­1); end; end; Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий  цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если  внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна  O(2^(N+1)­1)=O(2^N). Всегда надо помнить, что анализ сложности рекурсивных  алгоритмов весьма нетривиальная задача. Объёмная сложность рекурсивных алгоритмов Для всех рекурсивных алгоритмов очень важно понятие объёмной сложности. При каждом  вызове процедура запрашивает небольшой объём памяти, но этот объём может значительно  увеличиваться в процессе рекурсивных вызовов. По этой причине всегда необходимо  проводить хотя бы поверхностный анализ объёмной сложности рекурсивных процедур. Средний и наихудший случай Оценка сложности алгоритма до порядка является верхней границей сложности  алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных  выполнение алгоритма занимает намного меньше времени, чем можно предположить на  основе их сложности. Например, рассмотрим код, который ищет заданный элемент в  векторе A. function Locate(data: integer): integer; var i: integer; fl: boolean; begin fl:=false; i:=1; while (not fl) and (i<=N) do begin if A[i]=data then fl:=true else i:=i+1; end; if not fl then i:=0; Locate:=I; end; Если искомый элемент находится в конце списка, то программе придётся выполнить N  шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае  время работы алгоритма будем максимальным. С другой стороны, искомый элемент может находится в списке на первой позиции.  Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его  сложность можно оценить, как O(1). Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если  элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться  в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти  требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N). В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов  наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой  сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как  ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее. Общие функции оценки сложности Сейчас мы перечислим некоторые функции, которые чаще всего используются для  вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой  оценкой. 1. C – константа 2. log(log(N)) 3. log(N) 4. N^C, 01 8. C^N, C>1 9. N! Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит  несколько этих функций, то уравнение можно сократить до функции, расположенной ниже  в таблице. Например, O(log(N)+N!)=O(N!). Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно  считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда  достаточно производительности O(N). Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная  сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика,  поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма  данных. В заключение приведём таблицу, которая показывает, как долго компьютер,  осуществляющий миллион операций в секунду, будет выполнять некоторые медленные  алгоритмы. 5.6. Сложность алгоритмов Традиционно принято оценивать степень сложности алгоритма по объему используемых им основных ресурсов компьютера: процессорного времени и оперативной памяти. В связи с  этим вводятся такие понятия, как временная сложность алгоритма и объемная сложность  алгоритма. Параметр временной сложности становится особенно важным для задач,  предусматривающих интерактивный режим работы программы, или для задач управления в режиме реального времени. Часто программисту, составляющему программу управления  каким­нибудь техническим устройством, приходится искать компромисс между точностью вычислений и временем работы программы. Как правило, повышение точности ведет к  увеличению времени. Объемная сложность программы становится критической, когда объем обрабатываемых  данных оказывается на пределе объема оперативной памяти ЭВМ. На современных  компьютерах острота этой проблемы снижается благодаря как росту объема ОЗУ, так и  эффективному использованию многоуровневой системы запоминающих устройств.  Программе оказывается доступной очень большая, практически неограниченная область  памяти (виртуальная память). Недостаток основной памяти приводит лишь к некоторому  замедлению работы из­за обменов с диском. Используются приемы, позволяющие  минимизировать потери времени при таком обмене. Это использование кэш­памяти и  аппаратного просмотра команд программы на требуемое число ходов вперед, что  позволяет заблаговременно переносить с диска в основную память нужные значения.  Исходя из сказанного можно заключить, что минимизация емкостной сложности не  является первоочередной задачей. Поэтому в дальнейшем мы будем интересоваться в  основном временной сложностью алгоритмов. Время выполнения программы пропорционально числу исполняемых операций. Разумеется, в размерных единицах времени (секундах) оно зависит еще и от скорости работы  процессора (тактовой частоты). Для того чтобы показатель временной сложности  алгоритма был инвариантен относительно технических характеристик компьютера, его  измеряют в относительных единицах. Обычно временная сложность оценивается числом  выполняемых операций. Как правило, временная сложность алгоритма зависит от исходных данных. Это может  быть зависимость как от величины исходных данных, так и от их объема. Если обозначить  значение параметра временной сложности алгоритма  обозначить некоторый числовой параметр, характеризующий исходные данные, то временную сложность можно представить как функцию Tα(V). Выбор параметра V зависит от решаемой задачи или от вида используемого алгоритма для решения данной задачи.  α символом Tα, а буквой V Пример 1. Оценим временную сложность алгоритма вычисления факториала целого  положительного числа. Function Factorial(x:Integer): Integer; Var m,i: Integer; Begin m:=l; For i:=2 To x Do m:=ro*i; Factorial:=m End; Подсчитаем общее число операций, выполняемых программой при данном значении x.  Один раз выполняется оператор m:=1; тело цикла (в котором две операции: умножение и  присваивание) выполняется х — 1 раз; один раз выполняется присваивание Factorial:=m.  Если каждую из операций принять за единицу сложности, то временная сложность всего  алгоритма будет 1 + 2 (x — 1) + 1 = 2х Отсюда понятно, что в качестве параметра следует  принять значение х. Функция временной сложности получилась следующей: α T (V)=2V. В этом случае можно сказать, что временная сложность зависит линейно от параметра  данных — величины аргумента функции факториал. Пример 2. Вычисление скалярного произведения двух векторов А = (a1, a2, …, ak), В = (b1, b2, …, bk). АВ:=0; For i:=l To k Do AB:=AB+A[i]*B[i]; В этой задаче объем входных данных п = 2k. Количество выполняемых операций 1 + 3k = 1  + 3(n/2). Здесь можно взять V= k= п/2. Зависимости сложности алгоритма от значений  элементов векторов А и В нет. Как и в предыдущем примере, здесь можно говорить о  линейной зависимости временной сложности от параметра данных. С параметром временной сложности алгоритма обычно связывают две теоретические  проблемы. Первая состоит в поиске ответа на вопрос: до какого предела значения  временной сложности можно дойти, совершенствуя алгоритм решения задачи? Этот предел зависит от самой задачи и, следовательно, является ее собственной характеристикой. α Вторая проблема связана с классификацией алгоритмов по временной сложности. Функция α T (V) обычно растет с ростом V. Как быстро она растет? Существуют алгоритмы с  линейной зависимостью Т  от V (как это было в рассмотренных нами примерах), с  квадратичной зависимостью и с зависимостью более высоких степеней. Такие алгоритмы  называются полиномиальными. А существуют алгоритмы, сложность которых растет  быстрее любого полинома. Проблема, которую часто решают теоретики — исследователи  алгоритмов, заключается в следующем вопросе: возможен ли для данной задачи  полиномиальный алгоритм? 1. Цели изучения дисциплины: Цели: Цель преподавания дисциплины – ознакомление  студентов с основными часто используемыми алгоритмами в процессе практического  решения задач на ЭВМ и привитие навыков эффективного программирования. Задачи:  Задача изучения дисциплины – получить теоретические знания и практические навыки в  следующих областях: методы разработки эффективных алгоритмов, сортировка и поиск,  алгоритмы на графах, кодирование информации и шифрование. Место учебной  дисциплины в структуре основной образовательной программы. Данная дисциплина  относится к вариативной части профессионального цикла. Она является неотъемлемой  частью профессионального образования студента. Для освоения данной дисциплины  требуются математические знания, полученные в ходе изучения следующих дисциплин:  «Вводный курс математики», «Математика». Дисциплины, для успешного усвоения  которых требуется изучение дисциплины «Алгоритмы и структуры данных»:  «Интеллектуальные системы и технологии», «Исследование операций», «Компьютерное  моделирование». 3. Требования к уровню освоения содержания дисциплины Компетенции,  формируемые в рамках дисциплины «алгоритмы и структуры данных»: владение культурой мышления, способность к обобщению, анализу, восприятию информации, постановке цели  и выбору путей ее достижения, умение логически верно, аргументированно и ясно строить  устную и письменную речь (ОК­1); понимание социальной значимости своей будущей  профессии, обладание высокой мотивацией к выполнению профессиональной деятельности (ОК­3); владение широкой общей подготовкой (базовыми знаниями) для решения  практических задач в области информационных систем и технологий (ОК­6); умение  критически оценивать свои достоинства и недостатки, наметить пути и выбрать средства  развития достоинств и устранения недостатков (ОК­7); готовность использовать основные  законы естественно­научных дисциплин в профессиональной деятельности, применять  методы математического анализа и моделирования, теоретического и экспериментального  исследования (ОК­10); способность проводить моделирование процессов и систем (ПК­5);  способность разрабатывать средства реализации информационных технологий  (методические, информационные, математические, алгоритмические, технические и  программные) (ПК­12); готовность участвовать в работах по доводке и освоению  информационных технологий в ходе внедрения и эксплуатации информационных систем  (ПК­15); способность проводить сбор, анализ научно­технической информации,  отечественного и зарубежного опыта по тематике исследования (ПК­23); готовность  использовать математические методы обработки, анализа и синтеза результатов  профессиональных исследований (ПК­26); способность к инсталляции, отладке  программных и настройке технических средств для ввода информационных систем в  опытную эксплуатацию (ПК­29); В результате изучения дисциплины студент должен знать  основные алгоритмы ; уметь применять их в практической деятельности; владеть методами разработки эффективных алгоритмов 4. Общая трудоемкость дисциплины 10 зачётных  единиц и виды учебной работы. Вид учебной работы Трудоемкость (в соответствии с  учебным планом) (час) Распределение по семестрам (в соответствии с учебным планом)  (час) 360 5 6 Аудиторные занятия 171 (в том числе в интера. – 18) 95 (в том числе в интера. – 10) 76 (в том числе в интера. – 8) Лекции 95 57 38 Практические занятия Семинары  Лабораторные работы 76 38 38 Другие виды аудиторных работ Другие виды работы  Самостоятельная работа 135 75 60 Курсовой проект (работа) Реферат Расчетно­ графические работы Формы текущего контроля Формы промежуточной аттестации в  соответствии с учебным планом 54 экзамен экзамен 5. Содержание учебной дисциплины  5.1. Разделы учебной дисциплины № п/п Наименование раздела дисциплины (темы)  Аудиторные часы Всего Лекции Практ. (семинары) Лабор. работы В т.ч. интерактивные  формы обучения (не менее 10%) Сам. работа 1 Методы разработки эффективных  алгоритмов 28 16 12 8 20 2. Структуры данных 22 12 10 4 20 3. Сортировка и поиск. 26 14  12 20 4. Элементы теории информации и криптографии 19 15 4 15 5. Рекурсивные  алгоритмы 32 12 20 20 6. Алгоритмы на графах 30 12 18 20 7. Элементы теории принятия  решений 14 14 6 20 ИТОГО: 171/ 4,75 зач.ед. 95 76 18 / 10,5% 135 5.2. Содержание  разделов учебной дисциплины 1. Методы разработки эффективных алгоритмов. Понятие  алгоритмов, их основные свойства. Элементарный шаг, временная сложность алгоритма,  емкостная сложность, основные классы алгоритмов. Способы представления алгоритма,  понятие алгоритмического языка, алгоритмический язык – обобщенный Паскаль. Понятие  рекурсии.  Задача и алгоритм, сложность задачи. Верификация – аналитическое  доказательство истинности алгоритмов, применения метода математической индукции,  метод инварианта. Основные методы разработки эффективных алгоритмов: использование  нужных структур данных, метод балансировки, принцип “разделяй и властвуй”. 2.  Структуры данных. Понятие о структурах данных. Структурное программирование.  Простые и составные структуры данных. Динамические структуры. Линейные списки.  Деревья. Накопители данных: стеки и очереди. Строки. Задача поиска подстроки в строке.  Алгоритм Бауэра­Мура и метод Кнута­Морриса­Пратта. 3.  Сортировка и поиск. Внешние  и внутренние сортировки. Простые методы сортировки массивов: простое включение,  простой выбор, метод пузырька. Улучшенные методы сортировки массивов: сортировка  Шелла, пирамидальная сортировка, быстрая сортировка Хоара. Внешние сортировки:  сортировка слиянием, естественное слияние Вирта, многофазная сортировка и ее анализ.  Цифровая сортировка. Поиск элемента: в упорядоченном массиве, хеширование, деревья.  4. Элементы теории информации и криптографии. Понятие информации. Отсутствие  формального определения информации. Понятие информационных процессов и  информационных технологий. Непрерывная и дискретная форма представления  информации. ЭВМ, как универсальное средство обработки информации. Дискретный характер ЭВМ. Основы теории информации по Шеннону: понятия источника и адресата,  количество и единицы измерения информации, энтропия. Подход Каллбека. Шифрование  данных. Простые методы. Принципы шифрования с секретным ключом. Односторонние  функции и методы шифрования с открытым ключом. Методы Ферма и Эйлера. Метод RSA. Электронная подпись. 5. Рекурсивные алгоритмы. Понятие рекурсии. Внутренний  механизм организации рекурсии. Поиск с возвратом (backtracking) . Метод ветвей и границ  для решения оптимизационных задач. Применение рекурсии для решения простейших  комбинаторных задач. Задача о восьми ферзях. Задача о стабильных браках. Поиск  оптимального пути в лабиринте. 6. Алгоритмы на графах. Понятие графа, основные задачи  теории графов. Представление графов в ЭВМ. Графы и бинарные отношения. Деревья.  Обходы графов. Поиск в глубину и поиск в ширину. Эйлеров и гамильтонов пути. Поиск  компонент связности и бикомпонентов. Оптимизационные задачи на графах. Минимальный  остов (алгоритмы Краскала, Прима), минимальное паросочетание (венгерский алгоритм).  Поск кратчайшего пути (алгоритм Дейкстры). Задача коммивояжера. Точное и  приближенное решения. 7. Элементы теории принятия решений. Понятие  системы,  свойства систем. Понятие модели, адекватность модели.  Виды моделей: Модели черного  ящика, модели состава, модели структуры. Анализ и синтез, как методы научного  познания. Понятие проблемной ситуации и методы ее разрешения. Задача операционного  исследования. Многокритериальный и коллективный выбор. Принятие решений у условиях  риска. Лотерии и их оценки. Теория полезности Неймана­Монгенштерна. Функция  полезности денег. Введение в теории игорного и страхового бизнесов. Принятие решений в  условиях неопределенности. Принципы (критерии) оптимальности. Смешанные решения.  Принятие решений в условиях противодействия. Антогонистические и  неантогонистические игры. Игры в матричной форме. Игры с Седловой точкой. Теорема о  минимаксе. Игрф в позиционной форме. Совместные стратегии. Арбитражная схема Нэша.  5.3.  Лабораторный практикум № п/п № раздела дисциплины Наименование лабораторных  работ 1 2 Организация стека с помощью динамического списка. 2 2 Организация очереди и  стека на массиве. 3 2 Организация односвязного динамического списка. 4 2 Алгоритм  Бауэра­Мура. 5 2 КМП­метод. 6 2 Поиск по бинарному дереву. 7 3 Простые алгоритмы  сортировки. 8 3 Эффективные алгоритмы сортировки. 9 3 Алгоритмы поиска. 10 4  Простейшие методы шифрования. 11 4 Метод «исключающего или». 12 5 Поиск в  лабиринте. 13 5 Задача о восьми ферзях. 14 5 Задача о стабильных браках. 15 6  Представление графа в ЭВМ в виде матрицы смежности и списка ребер. 16 6 Поиск остова  графа. 17 6 Поиск транзитивного замыкания графа (алгоритм Уоршалла). 18 6 Поиск в  ширину на графе. 19 6 Поиск в глубину на графе. 20 6 Поиск компонент связности графа.  21 6 Представление взвешенного графа в ЭВМ. 22 6 Поиск кратчайших путей в графе  (алгоритм Дейкстры). 23 6 Поиск минимального остова (алгоритм Краскала). 6. Учебно­ методическое  обеспечение  дисциплины 6.1. Основная литература по дисциплине:  Акулов  О.А., Медведев М.В. Информатика. Базовый курс, Ж Омега­Л , 2009  Ахо А, Хопкрафт  Дж., Ульман Дж. Структуры данных и алгоритмы, ­М:Вильямс, 2007.  Вирт Н. Алгоритмы  и структуры данных, Спб: Невский диалект, 2007. 6.2. Дополнительная литература:  Карпов Ю. Г. Теория автоматов, языков и вычислений, ­ М.: «Вильямс», 2002.  Новиков Ф.  Дискретная математика для программистов, ­ Питер, 2000.  Хопкрафт Дж., Мотвани,  Ульман Дж. Введение в теорию автоматов, языков и вычислений, ­ М.: ВИЛЬЯМС, 2002.  6.3. Средства обеспечения освоения дисциплины В процессе изучения дисциплины, студент работает с многочисленными информационными источникам в сети Интернет. В качестве  примеров ссылок на интернет­источники можно привести: http://intuit.ru http://lib.ru 6.4.  Материально­техническое обеспечение дисциплины № п/п Наименование раздела (темы)  учебной дисциплины Наименование материалов обучения, пакетов программного  обеспечения Наименование технических и аудиовизуальных средств, используемых с целью демонстрации материалов 1 1, 2, 3,4,5, 6 Free Pascal, Free Pascal Lazarus, Borland Delphi или иной компилятор с языков Паскаль или C Мультимедийный компьютерный класс,  интерактивная доска, наличие локальной и глобальной сети. 7. Методические  рекомендации по организации изучения дисциплины 7.1. Методические рекомендации  преподавателю Данный курс реализуется посредством чтения лекций, проведения  практических занятий и консультаций. С целью выработки у студентов навыков  самостоятельной работы с литературой, некоторые вопросы излагаются в обзорном  порядке. Предполагается, что отдельные выводы и доказательства будут проведены  самостоятельно, с последующим отчетом на консультации. Согласно существующему  федеральному государственному образовательному стандарту специальности и других  нормативных документов целесообразно разработать матрицу наиболее предпочтительных  методов обучения и форм самостоятельной работы студентов, адекватных видам  лекционных и лабораторных занятий. Необходимо предусмотреть развитие форм  самостоятельной работы, выводя студентов к завершению изучения учебной дисциплины на её высший уровень. Пакет заданий для самостоятельной работы следует выдавать в начале  семестра, определив предельные сроки их выполнения и сдачи. Организуя  самостоятельную работу, необходимо постоянно обучать студентов методам такой работы. Вузовская лекция — главное звено дидактического цикла обучения. Её цель —  формирование у студентов ориентировочной основы для последующего усвоения  материала методом самостоятельной работы. Содержание лекции должно отвечать  следующим дидактическим требованиям:  изложение материала от простого к сложному,  от известного к неизвестному;  логичность, четкость и ясность в изложении материала;  возможность проблемного изложения, дискуссии, диалога с целью активизации  деятельности студентов;  опора смысловой части лекции на подлинные факты, события, явления, статистические данные;  тесная связь теоретических положений и выводов с  практикой и будущей профессиональной деятельностью студентов. Преподаватель,  читающий лекционные курсы в вузе, должен знать существующие в педагогической науке и  используемые на практике варианты лекций, их дидактические и воспитывающие  возможности, а также их методическое место в структуре процесса обучения.  Лабораторные работы сопровождают и поддерживают лекционный курс. При проведении  промежуточной и итоговой аттестации студентов важно всегда помнить, что  систематичность, объективность, аргументированность — главные принципы, на которых  основаны контроль и оценка знаний студентов. Проверка, контроль и оценка знаний  студента, требуют учета его индивидуального стиля в осуществлении учебной  деятельности. Знание критериев оценки знаний обязательно для преподавателя и студента.  В данной дисциплине, наиболее сложными, как правило, являются 4­й, 6­й и 7­й разделы.  Лектор должен постоянно поддерживать обратную связь с аудиторией, реагировать на  вопросы студентов, стимулировать студентов к их постановке. В случае необходимости,  преподаватель должен быть готов оказать дополнительную помощь студенту. 7.2.  Методические рекомендации для студентов На лекциях преподаватель рассматривает  вопросы программы курса, составленной в соответствии с государственным  образовательным стандартом. Преподаватель, по своему усмотрению, некоторые вопросы  выносит на самостоятельную работу студентов, в этом случае студенту выдается список  литературы или материалы, включенные в учебно­методический комплекс дисциплины.  Необходимо ответственно отнестись к выполнению самостоятельной работы. В случае  затруднений, необходимо повторить материал дисциплин «математическая логика и теория алгоритмов», «технологии программирования». На экзамене необходимо показать не  только формулировки основных определений, но и способность к применению полученных  знаний при решение практических задач. В перечень экзаменационных вопросов также  включены и вопросы по дисциплине «математическая логика и теория алгоритмов»,  которые студент должен повторить в процессе подготовки к экзамену. Данные знания  будут необходимы при изучении дисциплин «трансляция с языка высокого уровня»,  «представление знаний в информационных системах» и других. 8. Формы текущего  контроля успеваемости и промежуточной аттестации обучающихся. 8.1. Вопросы и задания для самостоятельной работы.  Реализация определенных алгоритмов на графах.  Решение  задач с помощью рекурсивных методов.  Реализация алгоритмов внутренней и внешней  сортировки.  Реализация алгоритмов поиска (хеширование, бинарные деревья, B­деревья).  Реализация алгоритма Хаффмана.  Реализация алгоритмов Хемминга (помехоустойчивое  кодирование)  Реализация алгоритмов задачи  коммивояжера: точные и приближенные  алгоритмы.  Реализация алгоритмов задачи почтальона.  Моделирование машины Тьюринга.  Моделирование машины с неограниченными регистрами. 8.2. Перечень вопросов для промежуточной аттестации (к экзамену). 5 семестр  Интуитивное определение алгоритма и  его временной и емкостной трудоемкости.  Формы представления алгоритмов. Методы  разработки эффективных алгоритмов.  Реально­выполнимые и реально­невыполнимые  алгоритмы.  Оценка трудоемкости. Рекуррентные теоремы.  Алгоритмы объединения  множеств и их сравнение.  Верификация алгоритмов. Метод инварианта.  Задача  сортировки и ее формы. Нижняя оценка трудоемкости методов, основанных на сравнениях.  Простые методы сортировки.  Сортировка Шелла.  Пирамидальная сортировка.  Быстрая  сортировка Хоара. Поиск порядковых статистик.  Прямое слияние.  Естественное слияние.  Многофазная (фибонначива) сортировка.  Цифровая сортировка и ее применение при  лексикографическом упорядочивании строк.  Поиск в упорядоченном массиве.  Информация и сообщения. Понятие кол­ва информации.  Понятие об энтропии и ее связь с информацией.  Двоичное кодирование. Теорема Шеннона для случая двоичного  кодирования.  Код Шеннона­Фано.  Простейшие методы шифрования (код Цезаря,  подстановки, перестановки).  Метод исключающего Или и основные принципы шифрования с секретным ключом.  Односторонние функции и простейшие методы шифрования с  открытым ключом. Метод Ферма.  Метод RSA. Его применение для шифрования и для  идентификации (электронная подпись). 6 семестр  Поиск с возвратом (на примере поиска в лабиринте).  Задача расстановки ферзей.  Метод ветвей и границ задач (на примере поиска  оптимального пути в лабиринте).  Понятие графа. Виды графов, их изображения. Части  графа.  Представление графов (в том числе  взвешенных ) в ЭВМ.  Остов графа. Алгоритм  построения остова.  Деревья. Свойства деревьев.  Графы и бинарные отношения. Понятие и поиск транзитивного замыкания графа.  Обходы графа. Поиск в глубину и поиск в ширину.  Эйлеровы пути. Поиск эйлерового цикла в ориентированном графе.  Гамильтоновы пути.  Поиск гамильтонова цикла.  Компоненты связности и алгоритм их поиска.  Компоненты  двусвязности и алгоритм их поиска.  Раскраска графов.  Взвешенные графы. Понятие об  оптимизационных задачах.Поиск минимального остова. Алгоритм Краскала.  Кратчайшие  пути в графе. Алгоритм Дейкстры.  Матроиды.  Жадные алгоритмы решения  оптимизационных задач. Теорема Радо­Эдмондса.  Понятие рекурсии. Ее внутреннее  устройство.  Свойства систем.  Модели. Модели черного ящика. Модели состава, модели  структуры.  Понятие проблемной ситуации и методы ее смягчения. Метод проб и ошибок.  Многокритериальный выбор: паретовские альтернативы, принятие решений на  паретовском множестве.  Коллективный выбор.  Задачи операционного исследования.  Классификация.  Постановка задачи принятия решений при риске. Понятие лотереи.  Теория полезности Неймана­Монгенштерна.  Понятие функции полезности денег и  детерминированного (денежного) эквивалента лотереи.  Применение функции полезности  денег для анализа лотерей.  Обоснование игорного и  страхового бизнеса с помощью теории лотерей.  Постановка задачи принятия решений при неопределенности. Выделение паретовских альтернатив.  Принципы (критерии) оптимальности при  принятие решений в  условиях неопределенности.  Смешанные решения. Диверсификация и рандомизация.  Графическая интерпретация критериев оптимальности.  Подход Кульбака к измерению  информации и понятие о статистических решающих функций.  Постановка задачи теории  игр. Антогонистические и неантогонистические игры.  Принципы принятия решений в  антогонистических играх.  Последовательность решения игры в чистых стратегиях.  Применение смешанных стратегий в задаче теории антогонистических игр.  Игры в  позиционной форме.  Игры с нестрогим соперничеством. Некооперативный вариант.  Игры  с нестрогим соперничеством. Коперативный вариант.  Совместные стратегии. Арбитражная схема Нэша.  Понятие формального языка и формальной грамматике.  Классификация  языков и грамматик по Хомскому.  Конечные автоматы.  Таблица переходов и граф  переходов КА. Построение КА по автоматной грамматике.  Устранение  недетерминированности КА.   Моделирование НКА (случай бинарного алфавита).    Регулярные выражения и регулярные множества. Эквивалентность понятий автоматного и  регулярного языков.   Магазинный автомат.  Построение МА для нисходящего анализа.  Построение МА для восходящего анализа.  Запись синтаксиса языков в форме Бэкуса­ Науэра.  Задача коммивояжера и ее приближенное решение.  Классы алгоритмов и задач P  и P­space. Понятие НМТ. Классы NP и NP­space.  Запись недетерминированного алгоритма  на обобщенном паскале. Моделирование недетерминированного алгоритма  детерминированным.  Соотношения между различными классами в теории алгоритмов и  теории формальных языков. Связь между языками и алгоритмами.  NP­question. Основные  возможности разрешения данной проблемы.  Трудно­решаемые задачи. Задача  коммивояжера (в оптимизационной постановке),  как пример.  Приближенные методы  решения задачи коммивояжера.  Понятие полиномиальной сводимости и NP­полноты.  Схеме доказательства NP­полноты. Задача b­коммивояжера, как пример NP­полной  задачи. 8.3. Тематика курсовых работ  Эффективные алгоритмы на графах.  Эффективные  алгоритмы сортировки и поиска.  Алгоритм Бауэра­Мура.  Алгоритм Кнута­Морриса­ Пратта.  Разработка электронного учебного пособия по дисциплине «математическая  логика и теория алгоритмов».  Разработка электронного учебника по теме «измерение  информации».  Решение задач теории игр.  Решение задач теории принятия решений в  условиях риска.  Поиск с возвратом.  Метод ветвей и границ. Рабочая программа учебной  дисциплины составлена в соответствии с учебным планом, федеральным государственным  образовательным стандартом высшего профессионального образования по направлению  подготовки: 230400.62 – Информационные системы и технологии. Рабочая программа  учебной дисциплины составлена: Кандидат технических наук, доцент кафедры  информатики  _______________ А.Н. Стась Рабочая программа учебной дисциплины  утверждена на заседании кафедры информатики протокол  №______________ от  «_____» _______________ 2013 г.   Зав. кафедрой информатики  _______________ А.Н. Стась  Рабочая программа учебной дисциплины одобрена методической комиссией физико­ математического факультета протокол  №______________ от  «_____» _______________  2013 г. Председатель методической  комиссии  ____________ З.А. Скрипко   Другие  интересные документы: . Создание условий для практического применения изученной  лексики и , Сказки красивого сердца Положение Третий Международный конкурс детского творчества Сказки Кра, .А.Конопляник Фонд развития энергетической и инвестиционной  политики и проектного финансирования Осно., , 201 года., Об утверждении  тарифноквалификационных характеристик по общеотраслевым профессиям ра.,  пространственные структуры От генерального плана к стратегической программе  Управление городом может б, I. РОССИЙСКАЯ ФЕДЕРАЦИЯ ПОСЛЕ ОКОНЧАНИЯ  ХОЛОДНОЙ ВОЙНЫ I., 2002 гг. количество детей со школьными проблемами в начальных классах массовой школы колеблется от 20 до 60., Источник: http://fullref.ru/job_f3adc1ea57266e5b547e26c6045086fe.html