Учебно-методический комплекс по дисциплине теория алгоритмов






Скачать 261.81 Kb.
НазваниеУчебно-методический комплекс по дисциплине теория алгоритмов
Дата публикации12.01.2015
Размер261.81 Kb.
ТипУчебно-методический комплекс
top-bal.ru > Информатика > Учебно-методический комплекс


Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Армавирская государственная педагогическая академия»

факультет прикладной информатики и информационных технологий

института прикладной информатики, математики и физики

кафедра информатики и информационных технологий обучения
Утверждено на заседании кафедры

информатики и ИТО АГПА

Протокол ___ от ”__”_______ 2011

Зав. кафедрой___________________

(Бельченко В.Е.)




УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

по дисциплине
^
ТЕОРИЯ АЛГОРИТМОВ

(факультет прикладной информатики и информационных технологий

института прикладной информатики, математики и физики)

для специальности

«учитель физики»

Форма отчетности:

Зачет: 2 курс, 3 семестр
^

УМК подготовлен


доцентом кафедры информатики и ИТО

Егизарьянц А.А.

Армавир - 2011



АННОТАЦИЯ

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

Цели курса:

  • формирование представления о необходимости точного определения понятия алгоритм и о вариантах такого рода определений;

  • формирование представления о вычислимых функциях;

  • формирование представлений о рекурсивно-перечислимых и рекурсивных языках, их соотношении, проблеме останова;

  • формирование представлений о возможности существования неразрешимых и неперечислимых множеств, невычислимых функций;

  • формирование представлений о грамматиках, иерархиях языков по Хомскому;

  • формирование представлений о проблеме сложности вычислений, о теории NР- полноты.

Исходным пунктом курса служит недостаточность интуитивного определения алгоритма. Рассматривается описание вычислительного процесса, принимаемого в качестве формального определения понятия алгоритма, в терминах частично-рекурсивных функций и вычислительных устройств (машины Тьюринга и Поста).

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

Введение в рассмотрение контекстно-свободных грамматик и языков позволяет выстроить иерархию языков по Хомскому.

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

Хопкрофт Д.Э., Р. Мотвани, Ульман Д. Введение в теорию автоматов, языков и вычислений. М-СПб-К, “Вильямс”, 2002.

Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М-СПб-К, “Вильямс”, 2001.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦМНО, 2001.

^

1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА.


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

Цели курса:

  • формирование представления о необходимости точного определения понятия алгоритм и о вариантах такого рода определений;

  • формирование представления о вычислимых функциях;

  • формирование представлений о кодировании машин Тьюринга;

  • формирование представлений о рекурсивно-перечислимых и рекурсивных языках, их соотношении, проблеме останова;

  • формирование представлений о детерминированных и недетерминированных конечных автоматах;

  • формирование представлений о возможности существования неразрешимых и неперечислимых множеств, невычислимых функций;

  • формирование представлений о грамматиках, иерархиях языков по Хомскому;

  • формирование представлений о проблеме сложности вычислений, о теории NР- полноты.

Исходным пунктом курса служит недостаточность интуитивного определения алгоритма. Далее, приводятся различные версии уточнений этого понятия, связанные с именами К. Геделя, А. Тьюринга, Э. Поста, А. Черча, Дж. фон Неймана, А. Маркова, С. Клини, А. Колмогорова, В. Успенского.

Рассматривается описание вычислительного процесса, принимаемого в качестве формального определения понятия алгоритма, в терминах частично-рекурсивных функций и вычислительных устройств (машины Тьюринга и Поста).

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

Введение в рассмотрение контекстно-свободных грамматик и языков позволяет выстроить иерархию языков по Хомскому.

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

Хопкрофт Д.Э., Р. Мотвани, Ульман Д. Введение в теорию автоматов, языков и вычислений. М-СПб-К, “Вильямс”, 2002.

Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М-СПб-К, “Вильямс”, 2001.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦМНО, 2001.

Мальцев А.И. Алгоритмы и рекурсивные функции. М., “Наука”, 1965.

Колмогоров А.Н. Теория информации и теория алгоритмов. - М.: Наука, 1987.

Успенский В.А. Машина Поста. - М.: Наука, 1988.

Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М., ЛБЗ, 2001.

Новиков Ф.А. Дискретная математика для программистов. Спб, “Питер”, 2001.

2. Тематический план учебной дисциплины

№ п/п

Раздел, тема

Всего часов

В том числе аудиторных

Самостоятельная работа, час

Всего аудиторных

Лекций

Практических



Введение. Интуитивное определение алгоритма. Понятие конструктивного пространства и вычислимой функции.

3

1

1




2



Конечные автоматы и регулярные языки. Понятия языка и алфавита. Определение ДКА.

3

1

1




2



Конечные автоматы и регулярные языки. Понятие НКА.

8

4

2

2

4



Регулярные языки и регулярные выражения.

6

4

2

2

2



Формализация машины Тьюринга (МТ).

6

4

2

2

2



Упорядочение языков и программ. Классификация языков. Рекурсивно-перечислимые и рекурсивные языки. Компьютер фон Неймана и МТ.

6

2

2




4



Многоленточная машина Тьюринга. Эмуляция работы компьютера фон Неймановской архитектуры многоленточной МТ.

4

2

2




2



Синтаксис и семантика языка. Порождающие грамматики Хомского как способ задания языка.

5

3

1

2

2



Примитивно-рекурсивные, частично-рекурсивные и общерекурсивные функции.

3

1

1




2




ИТОГО

44

22

14

8

22


3. СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ
3.1. Содержание учебного материала: ЛЕКЦИИ
^

Лекция № 1


Тема: Введение. Интуитивное определение алгоритма. Понятие конструктивного пространства и вычислимой функции. Конечные автоматы и регулярные языки. Понятия языка и алфавита

Содержание:

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

  2. Алгоритмическая разрешимость проблем.

  3. Понятие конструктивных объектов и конструктивных пространств.

  4. Понятие вычислимой функции.

  5. Цели и задачи курса.
^

Лекция № 2


Тема: Конечные автоматы и регулярные языки. Понятие НКА.

Содержание:

  1. Понятие недетерминированного конечного автомата (НКА).

  2. Особенности НКА. Формы задания НКА.

  3. Сопоставление ДКА и НКА. Построение ДКА по заданному НКА.

  4. НКА как инструмент распознавания языков и поиска образцов.

  5. Понятие -переходов.

  6. Эквивалентность классов языков, распознаваемых ДКА и НКА.

  7. НКА как способ формализации понятия алгоритма.

Лекция № 3

Тема: Регулярные языки и регулярные выражения.

Содержание:

  1. Языки и операции над ними. Замыкание Клини. Понятие регулярного языка.

  2. Регулярные выражения. Замкнутость множества регулярных языков.

  3. Построение регулярного выражения по заданному ДКА.

  4. Построение НКА по заданному регулярному выражению.

  5. Соотношение регулярных языков и языков, распознаваемых КА.

  6. Лемма о накачке регулярных языков.

  7. Примеры нерегулярных языков.
^

Лекция № 4


Тема: Формализация машины Тьюринга (МТ).

Содержание:

  1. Машина Тьюринга - вариант формализации понятия алгоритма.

  2. Структура машины Тьюринга. Алфавит. Внутренние и внешние команды.

  3. Память. Программа. Декларативный характер языка команд машины.

  4. Допускающие входы и допускающие состояния. Слово состояния и код МТ.

  5. Формы записи программ МТ.

  6. МТ как средство решения задач вычислительного характера.

  7. МТ как средство решения задач распознавательного характера.
^

Лекция № 5


Тема: Упорядочение языков и программ. Классификация языков. Рекурсивно-перечислимые и рекурсивные языки. Компьютер фон Неймана и МТ.

Содержание:

  1. Упорядочение входных цепочек над заданным алфавитом.

  2. Упорядочение языков и соответствующих этим языкам МТ.

  3. Классификация языков. Рекурсивно-перечислимые и рекурсивные языки.

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

  5. Универсальный язык как представитель рекурсивно-перечислимых, но не рекурсивных языков. Построение универсального языка.

  6. Определение многоленточной МТ. Эквивалентность многоленточной МТ и одноленточной МТ.

  7. Возможность эмуляции работы компьютера фон Неймановской архитектуры МТ.
^

Лекция № 6


Тема: Понятия вычислимой и частично вычислимой функций. Проблема останова МТ. Примеры алгоритмически неразрешимых проблем.

Содержание:

  1. Понятия вычислимой и частично вычислимой функций.

  2. Вычислимые МТ частичные функции.

  3. Проблема останова МТ на входах цепочек рекурсивно-перечислимых языков.

  4. Проблема распознавания МТ своего кода.

  5. Проблема распознавания МТ заданного кода.

  6. Примеры неразрешимых проблем в математике (проблема континуума и др.).
^

Лекция № 7


Тема: Синтаксис и семантика языка. Порождающие грамматики Хомского как способ задания языка.

Содержание:

  1. Синтаксис и семантика языка. Понятие грамматики.

  2. Порождающие и распознающие грамматики Хомского.

  3. Структура порождающих грамматик Хомского.

  4. Порождающие грамматики Хомского как способ задания языка.

3.3. Содержание учебного материала: ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
^

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 1


Тема: Детерминированные конечные автоматы (ДКА).

Цель: Знакомство с работой ДКА. Построение ДКА. Анализ работы ДКА.

Содержание:

  1. Построение ДКА, распознающих заданные цепочки над заданным алфавитом.

  2. Слово состояния ДКА.

  3. Эффективность ДКА в качестве средства поиска образцов.

  4. Проверка работы программ ДКА над задаваемыми входами.

Рекомендации по организации самостоятельной работы:

    • изучение материалов к контрольной работе №1

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_1.doc);

    • изучение главы #2 "Конечные автоматы и языки" пособия Подзорова С.Ю. "Теория алгоритмов"

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Course.pdf);

    • изучение главы #3 "Конечные автоматы и регулярные грамматики" пособия Мартыненко Б.К. "Языки и трансляции"

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-2.pdf).

Содержание отчёта:

решения заданий, приведённых в разделе "ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ" материалов к контрольной работе №1

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_1.doc);

Форма отчёта: произвольная.
^

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ № 2


Тема: Регулярные выражения и НКА.

Цель: Знакомство с регулярными выражениями. Регулярные выражения как способ явного задания языков.

Содержание:

  1. Регулярные выражения в качестве средства задания языка.

  2. Построение НКА по задаваемым регулярным выражениям.

  3. Проверка работы НКА на регулярных входах.

  4. Построение регулярного выражения по заданному ДКА.

Рекомендации по организации самостоятельной работы:

    • изучение материалов к контрольной работе №1

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_1.doc);

    • изучение главы #2 "Конечные автоматы и языки" пособия Подзорова С.Ю. "Теория алгоритмов"

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Course.pdf);

    • изучение главы #3 "Конечные автоматы и регулярные грамматики" пособия Мартыненко Б.К. "Языки и трансляции"

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-3.pdf).

Содержание отчёта:

решения заданий, приведённых в разделе "ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ" материалов к контрольной работе №1

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_1.doc).

Форма отчёта: произвольная.
^

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 3


Тема: Машина Тьюринга (МТ).

Цель: Знакомство с работой МТ. Построение МТ. Анализ работы МТ.

Содержание:

  1. Программирования алгоритмов уменьшения и наращивания заданных чисел.

  2. Программирования алгоритмов распознавания заданных конфигураций.

  3. Проверка работы программ МТ.

Рекомендации по организации самостоятельной работы:

    • изучение материалов к контрольной работе №2

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_2.doc);

    • изучение главы #6 "Машины Тьюринга" пособия Мартыненко Б.К. "Языки и трансляции"

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-6.pdf);

    • изучение главы "Рекурсивные функции и общее понятие вычислимости" пособия Подзорова С.Ю. "Теория алгоритмов"

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Course.pdf).

Содержание отчёта:

решения заданий, приведённых в разделе "ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ" материалов к контрольной работе №2

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_2.doc);

Форма отчёта: произвольная.
^

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 4


Тема: Порождающие грамматики Хомского.

Цель: Знакомство с приёмами конструирования продукций порождающих грамматик.

Содержание:

  1. Конструирование продукций порождающих грамматик для генерирования задаваемых цепочек.

  2. Проверка однозначности конструирования порождающих грамматик.

Рекомендации по организации самостоятельной работы:

    • изучение материалов к контрольной работе №3

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_3.doc).

    • изучение главы #2 "Грамматики" пособия Мартыненко Б.К. "Языки и трансляции"

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-2.pdf);

Содержание отчёта:

решения заданий, приведённых в разделе "ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ" материалов к контрольной работе №3

(http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_3.doc);

Форма отчёта: произвольная.
^ 3.4. СОДЕРЖАНИЕ И ВИДЫ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ.
1) Работа с материалами лекций.
2) Работа с рекомендованной для самостоятельного изучения литературой:

  1. к лекции № 1: [1], [2], [3], [6], [9], [14];

  2. к лекции № 2: [2], [7];

  3. к лекции № 3: [1], [7], [8];

  4. к лекции № 4: [1], [7];

  5. к лекции № 5: [1];

  6. к лекции № 6: [1], [7];

  7. к лекции № 7: [1], [7];

3) Подготовка к практическим занятиям (теоретическая подготовка):

  1. к практической работе № 1: [1], [7];

  2. к практической работе № 2: [1], [7];

  3. к практической работе № 3: [1], [7];

  4. к практической работе № 4: [1], [4], [5];


^ 4. РЕКОМЕНДАЦИИ ПО ОРГАНИЗАЦИИ

САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ.
Цель самостоятельной работы студентов – формирование представлений относительно процедур построения и последующего анализа алгоритмических конструкций.

Задачи:

1) подготовка к успешному выполнению практических занятий, предусмотренных тематическим планом изучаемой дисциплины;

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

Пути достижения цели:

1) изучение материалов лекций;

2) рассмотрение примеров, разобранных в ходе проведения практических занятий;

3) работа с рекомендованной литературой;

4) работа с рекомендованными для самостоятельного изучения электронными ресурсами:

  1. http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_1.doc

  2. http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_2.doc

  3. http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/contrl_work_3.doc

  4. Пособие Подзорова С.Ю. "Теория алгоритмов"

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Course.pdf

  1. Пособие Мартыненко Б.К. "Языки и трансляции": глава #1 "Языки и их представление"

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-1.pdf

  1. Пособие Мартыненко Б.К. "Языки и трансляции": глава #2 "Грамматики"

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-2.pdf

  1. Пособие Мартыненко Б.К. "Языки и трансляции": глава #3 "Конечные автоматы и регулярные грамматики"

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-3.pdf

  1. Пособие Мартыненко Б.К. "Языки и трансляции": глава #4 "Контекстно-свободные грамматики"

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-4.pdf

  1. Пособие Мартыненко Б.К. "Языки и трансляции": глава #5 "Магазинные автоматы"

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-5.pdf

  1. Пособие Мартыненко Б.К. "Языки и трансляции": глава #6 "Машины Тьюринга"

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-6.pdf

  1. Пособие Мартыненко Б.К. "Языки и трансляции": глава #7 "Машины Тьюринга: проблема остановки, языки типа 0".

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-7.pdf

  1. Пособие Мартыненко Б.К. "Языки и трансляции": глава #8 "Линейно-ограниченные автоматы и контекстно-зависимые языки".

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/Ch-8.pdf
Приобретаемые в ходе самостоятельной работы студентов навыки:

1) умение анализировать предложенную задачу, очерчивать основные этапы ее решения;

2) умение составлять программные модули;

3) умение анализировать результаты трассировки программных модулей и вносить, в случае необходимости, соответствующие изменения;

4) умение оценивать корректность вносимых изменений.

^ 4.1. ТЕСТИРОВАНИЕ УРОВНЯ УСВОЕНИЯ ЛЕКЦИОННОГО МАТЕРИАЛА.

http://www.agpu.net/fakult/ipimif/fpiit/kafinf/umk/el_lib/alg_theor/62_ta_question.doc

^ 4.2. ЗАДАНИЯ К ПРОВЕРОЧНЫМ РАБОТАМ.

Ниже приведены образцы типовых заданий контрольных работ №№ 1, 3:
ПРОВЕРОЧНАЯ РАБОТА №1

Образцы типовых заданий контрольной работы №1:

^ Типовое задание. Пример № 1:

Добавить к имеющейся группе меток 2 группы по 3 метки.

Стартовая позиция: ┕┙▼▼▼▼.

Финальная позиция: ┕┙▼▼▼┕┙▼▼▼┕┙▼▼▼▼

^ Типовое задание. Пример № 2:

Построить машину Тьюринга, допускающую входной язык {(01)n(10)n, n ≥ 1}.

Дополнительное условие:

МТ попеременно обрабатывает цепочки вида (01) и (10), заменяя 0→ А, 1→ В.

Стартовое положение считывающей головки МТ - над крайним левым символом.

ЗАДАНИЕ: Составить и представить код МТ в виде таблицы и графа.

^ Представить код машины Тьюринга в 2-ой системе счисления.

Типовое задание. Пример № 3:

Записать протокол работы МТ (задание №2) для входных цепочек:

010101101010 и 01011001.

^ ПРОВЕРОЧНАЯ РАБОТА №2

Образцы типовых заданий контрольной работы №2:

Типовое задание. Пример № 1:

Построить ДКА (Σ= {0,1}), допускающий следующий входной язык:

множество подцепочек, оканчивающихся комбинацией 01001.

^ Типовое задание. Пример № 2:

Построить регулярное выражение, задаваемое ДКА (Σ= {0,1}) таблицей переходов:




0

1

A

{A}

{B}

*B

{B}

{B}

Типовое задание. Пример № 3:

Построить HКА (Σ= {0,1}), поддерживающий язык, задаваемый регулярным выражением 1*001

Типовое задание. Пример № 4:

Преобразовать НКА в эквивалентный ДКА. Σ= {0,1}. Стартовое состояние обозначается знаком →. Допускающее состояние обозначается знаком *..




0

1

p

{s}

{q}

*q

{r}

{q, r}

r

{s}

{p}

*s

{ }

{p}


^ ПРОВЕРОЧНАЯ РАБОТА №3

Образцы типовых заданий контрольной работы №1:

Типовое задание. Пример № 1:

Построить грамматику G1, порождающую следующий язык:

L1 = {anbn-1│n > 1}

^ Типовое задание. Пример № 2:

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

Типовое задание. Пример № 3:

Построить дерево вывода для цепочки aaabb :языка L1, порожденного грамматикой G1

^ Типовое задание. Пример № 4:

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

{-, /, ^}

Типовое задание. Пример № 5:

Построить дерево вывода для цепочки a/b^c-d языка L1, порожденного грамматикой G1

^
5. ТРЕБОВАНИЯ К ЗАЧЕТУ

Выполнение трех зачетных проверочных работ на положительную оценку.

6. СПИСОК РЕКОМЕНДУЕМОЙ ДЛЯ ИЗУЧЕНИЯ ЛИТЕРАТУРЫ.

6.1. ОСНОВНАЯ ЛИТЕРАТУРА

  1. Хопкрофт Д.Э., Р. Мотвани, Ульман Д. Введение в теорию автоматов, языков и вычислений. М-СПб-К, “Вильямс”, 2002.

  2. Мальцев А.И. Алгоритмы и рекурсивные функции. М., “Наука”, 1965.

  3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦМНО, 2001.

  4. Карпов Ю.Г. Теория и технология программирования. Основы построения трансляторов.- СПб: БХВ-Петербург, 2005.

  5. Мозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход. - СПб.: Наука и Техника, 2006.

^ 6.2. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА:

  1. Колмогоров А.Н. Теория информации и теория алгоритмов. - М.: Наука, 1987.

  2. Эббинхауз Г.-Д., Якобс К., Манн Ф.-К., Хермес Г.. Машины Тьюринга и рекурсивные функции. М.: Мир, 1972.

  3. Успенский В.А. Машина Поста. - М.: Наука, 1988.

  4. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М-СПб-К, “Вильямс”, 2001.

  5. Горбатов В.А. Фундаментальные основы дискретной математики. М., “Наука. Физматлит”, 2000.

  6. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М., ЛБЗ, 2001.

  7. Новиков Ф.А. Дискретная математика для программистов. Спб, “Питер”, 2001.

  8. Романовский И.В. Дискретный анализ. СПб-М., “ФИЗМАТЛИТ. Невский диалект”, 2000.

  9. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989.

  10. Буч Г. Объектно-ориентированное проектирование с примерами применения. – И.: Конкорд, 1992.

  11. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков. М.: Наука, 1988.




Добавить документ в свой блог или на сайт

Похожие:

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине теория алгоритмов
Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине Б2 «Теория алгоритмов»
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального...

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине «Теория вероятностей и...
Учебно-методический комплекс предназначен для преподавателей, студентов, обучающихся по направлению «Педагогическое образование»,...

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс курс по выбору по дисциплине « дв4»
Учебно-методический комплекс по дисциплине " Технические и аудиовизуальные средства обучения"

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине « Б2»
Учебно-методический комплекс (далее умк) по дисциплине «Информатика» разработан в соответствии с требованиями фгос впо к обязательному...

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине Инженерная графика
...

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине Инженерная графика
Данный учебно-методический комплекс рассмотрен и утвержден на заседании Учебно-методической комиссии роат. Протокол №4 от 01. 07....

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине «Информатика»
Учебно-методический комплекс по дисциплине «Использование современных информационных и коммуникационных технологий» разработан в...

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине «Информатика»
Учебно-методический комплекс по дисциплине «Использование современных информационных и коммуникационных технологий» разработан в...

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине « дв32»
Учебно-методический комплекс по дисциплине " Технические и аудиовизуальные средства обучения"



Школьные материалы


При копировании материала укажите ссылку © 2018
контакты
top-bal.ru

Поиск