Программа дисциплины «Теоретическая информатика» - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины Управление качеством программного обеспечения... 1 132.89kb.
Программа дисциплины для студентов специальности 080801. 65 «Прикладная... 3 491.45kb.
Программа дисциплины Информационные технологии управления знаниями... 1 212.85kb.
Примерная программа дисциплины теоретическая механика 1 182.78kb.
Программа дисциплины «Управление данными» 1 328.64kb.
Программа дисциплины Современная прикладная алгебра для направления... 1 189.55kb.
Программа дисциплины Распределенные информационные системы для направления... 1 219.99kb.
Рабочая программа дисциплины Социология управления Направление подготовки... 1 140.1kb.
Рабочая программа по дисциплине «Исследование операций и методы оптимизации»... 1 140.33kb.
Программа дисциплины "Базы данных" для направления 230100. 01 "Информатика... 1 160.69kb.
Программа дисциплины Дискретная математика для направления 080500. 1 323.06kb.
Закономерности систем. Закономерности целеобразования. Метод принятия... 1 22.9kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Программа дисциплины «Теоретическая информатика» - страница №1/1

Правительство Российской Федерации
Нижегородский филиал

Федерального государственного автономного образовательного учреждения высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"
Факультет бизнес-информатики и прикладной математики

Программа дисциплины «Теоретическая информатика»

для направления 080500.62 «Бизнес-информатика» подготовки бакалавра

Автор программы:

Логвинова К.В., к.ф.-м.н., профессор, klogvinova@hse.ru

Одобрена на заседании кафедры «___»____________ 2013 г

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


Рекомендована секцией УМС «Информатика» «___»____________ 2013 г

Председатель Визгунов А.Н. _______________________


Утверждена УМС НИУ ВШЭ – Нижний Новгород «___»_____________2013 г.

Председатель Петрухин Н.С. _______________________

Нижний Новгород, 2013

1Область применения и нормативные ссылки


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

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

Программа разработана в соответствии с:

ОС ГОБУ ВПО ГУ-ВШЭ для направления подготовки бакалавра 080500.62 «Бизнес-информатика»;

ООП для направления подготовки бакалавра 080500.62 «Бизнес-информатика»;

Рабочим учебным планом университета для направления подготовки бакалавра 080500.62 «Бизнес-информатика», утверждённым в 2010 г.


2Цели освоения дисциплины


Целями освоения дисциплины «Теоретическаяинформатика» являются изучение понятийного аппарата и применение полученных знаний к анализу математических моделей в различных предметных областях.

3Компетенции обучающегося, формируемые в результате освоения дисциплины


В результате освоения дисциплины студент должен:

Знать основные методы, применяющиеся в дискретной математике

Уметь применять эти методы на практике

Иметь навыки (приобрести опыт) решения задач, возникающих в различных прикладных областях


В результате освоения дисциплины студент осваивает следующие компетенции:

Компетенция
Код по ФГОС/ НИУ
Дескрипторы – основные признаки освоения (показатели достижения результата)
Формы и методы обучения, способствующие формированию и развитию компетенции

Готовность выявить естественнонаучную сущность проблем, возникающих в ходе профессиональной деятельности, привлечь для их решения соответствующий математический аппарат
ОНК-3
Студент способен к распознаванию естественнонаучных аспектов широкого круга проблем профессиональной деятельности, обладает необходимыми навыками применения понятийного аппарата
Чтение лекций, проведение практических занятий, самостоятельная работа

Готовность работать с ин-формацией из различных источников
ИК-4
В ходе подготовки к занятиям студент получает и совершенствует навыки работы с информационными источниками различного типа
Самостоятельная работа

Способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат
ПК-2
Студент способен применять современный математический аппарат в прикладной и исследовательской деятельности
Чтение лекций, проведение практических занятий, самостоятельная работа

Способность решать задачи производственной и технологической деятельности на профессиональном уровне, включая разработку математических моделей, алгоритмических и программных решений
ПК-8
Студент способен применять методы дискретной математики для разработки математических моделей, алгоритмических и программных решений
Чтение лекций, проведение практических занятий, самостоятельная работа



4Место дисциплины в структуре образовательной программы


Настоящая дисциплина относится к циклу математических и естественнонаучных дисциплин и блоку дисциплин, обеспечивающих подготовку бакалавра по направлению 080500.62 «Бизнес-информатика».

Для направления «Бизнес-информатика» настоящая дисциплина является базовой.

Изучение данной дисциплины базируется на знании материала курса «Дискретная математика» и основ программирования, а также навыках логического мышления.

Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин: «Дискретные модели и сложность алгоритмов», «Методы трансляции и компиляции».


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




№
Название раздела
Всего часов
Аудиторные часы
Самостоятельная работа










Лекции
Семинары
Практические занятия



1
Формальные языки
12
4



2
6

2
Конечные автоматы
52
10



12
30

3
Автоматы с магазинной памятью
48
8



10
30

4
LL-грамматики
50
10



10
30

5
LR-грамматики
54
10



8
36




Итого
216
42



42
132


6Формы контроля знаний студентов


Тип контроля
Форма контроля
1 год
Параметры







1
2
3
4



Текущий

(неделя)


Контрольная работа









7
Письменная работа 60 минут




Домашнее задание






4
3
Письменная (5-6 задач)

Промежуточный
Зачет






*



Письменная работа 80 минут

Итоговый
Экзамен









*
Письменная работа 80 минут



6.1Критерии оценки знаний, навыков


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


7Содержание дисциплины


  1. Формальные языки.

Алфавит, цепочки в алфавите, язык как множество цепочек. Проблема определения бесконечного языка конечными средствами. Способы определения языка: механизм генерации и распознавания. Иерархия Хомского. Автоматы как способ распознавания языка. Формальные грамматики как способ генерации цепочек языка.
Литература по разделу: [1] , [2,4].


  1. Конечные автоматы.

Такт и конфигурация конечного автомата. Детерминированные и недетерминированные КА. Язык, допускаемый КА. Алгоритм построения детерминированного автомата по заданному недетерминированному. Автоматы с ԑ-тактами. Алгоритм построения ԑ-свободного автомата. Регулярные выражения. Теорема Клини об эквивалентности класса регулярных языков и конечно-автоматных языков. Анализ и синтез КА. Лемма о расширении регулярных множеств. Свойства замкнутости класса регулярных языков. Конечные преобразователи. Праволинейные грамматики. Эквивалентность праволинейных и регулярных языков.
Литература по разделу: [1] , [2,3,5]


  1. Автоматы с магазинной памятью и контекстно-свободные грамматики

Формальное определение и схематическое представление МП-автомата. Операции с магазином. Эквивалентность МП-автоматов и КС-грамматик. Деревья выводов в КС-грамматиках. Неоднозначность КС-грамматик. Алгоритм удаления бесполезных символов. Нормальные формы КС-грамматик. Удаление левой (правой) рекурсии. Преобразователи с магазинной памятью.
Литература по разделу: [1] , [2,3].


  1. LL-грамматики

Нисходящий синтаксический анализ. Проблема построения дерминированного нисходящего анализатора. LL(k)- грамматики. Простая (разделенная) LL(1) – грамматика. Функции FIRST и FOLLOW.. Предсказывающий алгоритм разбора для LL(1) – грамматик.
Литература по разделу: [1], [2,3,6].

  1. LR-грамматики

Восходящий синтаксический анализ. Алгоритм перенос-свертка. LR(k)-грамматики. Детерминированный восходящий синтаксический анализ. Построение правых анализаторов для LR(k)-грамматик.

Литература по разделу: [1], [2,3,4].



8Образовательные технологии


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

9Оценочные средства для текущего контроля и аттестации студента

9.1Тематика заданий текущего контроля

  1. Построение КА по заданному языку.


  2. Построение детерминированного автомата по заданному недетерминированному автомату.

  3. Построение ԑ-свободного КА

  4. Синтез автомата по регулярному выражению

  5. Анализ КА

  6. Минимизация КА

  7. Нахождение грамматики (регулярной или КС-свободной) по заданному языку

  8. Построение МП-автомата по заданному языку

  9. Построение нисходящего (восходящего) анализатора по заданной грамматике.

  10. Удаление бесполезных символов из КС-грамматики

  11. Удаление леворекурсивных правил.

  12. Устранение неоднозначности

  13. Приведение грамматики к нормальной форме Хомского

  14. Вычисление функций FIRST и FOLLOW для заданной LL грамматики

  15. Построение левого анализатора для заданной LL(1) грамматики.

  16. Построение правого анализатора для заданной LR(1) грамматики

9.2Вопросы для оценки качества освоения дисциплины


  1. Понятие формального языка. Способы определения языка. Иерархия Хомского.

  2. Операции над языками.

  3. Концепция КА-распознавателя: формальное определение, схематическое представление, такт и конфигурация.

  4. Детерминированный КА.

  5. Недетерминированный КА, язык допускаемый недетерминированным КА

  6. Эквивалентные состояния, недостижимые символы, построение минимального автомата для заданного языка.

  7. Регулярные множества и регулярные выражения.

  8. Теорема Клини.

  9. Свойства замкнутости регулярных языков.

  10. Праволинейные грамматики. Эквивалентность праволинейных и регулярных языков.

  11. Лемма о разрастании регулярных множеств.

  12. Понятие перевода (трансляции)

  13. Конечные преобразователи.

  14. Автоматы с магазинной памятью. Операции с магазином.

  15. КС-грамматики. Деревья вывода. Неоднозначность КС-грамматик.

  16. Бесполезные символы в грамматике. Рекурсивные правила.

  17. Нормальные формы КС-грамматик.

  18. Свойства замкнутости КС-языков.

  19. Преобразователи с магазинной памятью.

  20. Синтаксический анализ (разбор). Построение нисходящего (восходящего) анализаторов по заданной грамматике.

  21. Проблема построения детерминированных анализаторов. Классы LL и LR грамматик.

  22. Определение LL(k)-грамматики.

  23. Функции FIRST и FOLLOW

  24. Предсказывающий алгоритм разбора для LL(1) – грамматик

  25. Разбор для LL(k) – грамматик

  26. Проверка LL(k) - условия

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

  28. Определение LR(k)-грамматики.

  29. Алгоритм LR(k) – разбора.

  30. Проверка LR(k) – условия.

9.3Примеры заданий промежуточного /итогового контроля

10Порядок формирования оценок по дисциплине


По дисциплине предусмотрены: 1 контрольная работы (Ок/р1), 2 домашних задания (Од/з1, Од/з2 ), 1 промежуточный контроль в форме зачета (Озачет) и итоговый экзамен (Оэкзамен).

В диплом идет результирующая оценка по дисциплине (Орезульт ), которая рассчитывается по формуле:



Орезульт = 0.5 Онакопленная Итоговая + 0.5 ·Оэкзамен

Онакопленная Итоговая = 0.5 Опромежуточная + 0.5 Отекущая

Опромежуточная = 0.3 Од/з1 + 0.7 Озачет - промежуточная оценка после 3-го модуля

Отекущая = 0.7 Ок/р1 + 0.3 Од/з2 – оценка, накопленная четвертом модуле.

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

На пересдаче студенту не предоставляется возможность получить дополнительный балл для компенсации оценки за текущий контроль.

На зачете студент может получить дополнительный вопрос (дополнительную практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается в 1 балл.

На экзамене студент может получить дополнительный вопрос (дополнительную практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается в 1 балл.

11Учебно-методическое и информационное обеспечение дисциплины

11.1Базовый учебник


[1]. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков.М: БИНОМ, 2006.

11.2Основная литература

[2]. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1:Синтаксический анализ. – М.:Мир, 1978


[3]. Мартыненко Б.К. Языки и трансляция. – СПб: Издательство С.-Петербургского университета, 2004

11.3 Дополнительная литература
[4]. Манфред Брой. Информатика. М.:Наука, 1996

[5]. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.:Мир, 1979



[6]. Ахо А., Сети Р, Ульман Дж. Компиляторы: принципы, технологии, инструменты. М.:Вильямс, 2001

Автор программы К.В.Логвинова