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






Скачать 410.53 Kb.
НазваниеУчебно-методический комплекс по дисциплине теория алгоритмов
страница2/7
Дата публикации01.02.2015
Размер410.53 Kb.
ТипУчебно-методический комплекс
top-bal.ru > Информатика > Учебно-методический комплекс
1   2   3   4   5   6   7

Лекция № 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. Возможность эмуляции работы компьютера фон Неймановской архитектуры МТ.

Лекция № 7


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

Содержание:

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

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

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

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

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

  6. Примеры неразрешимых проблем в математике (проблема континуума и др.).
1   2   3   4   5   6   7

Похожие:

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

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

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

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

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

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

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

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

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

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



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


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

Поиск