страница 1
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Похожие работы
|
Программа дисциплины «Теоретическая информатика» - страница №1/1
Правительство Российской Федерации Нижегородский филиал Федерального государственного автономного образовательного учреждения высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики" Факультет бизнес-информатики и прикладной математики Программа дисциплины «Теоретическая информатика» для направления 080500.62 «Бизнес-информатика» подготовки бакалавра Автор программы: Логвинова К.В., к.ф.-м.н., профессор, klogvinova@hse.ru Одобрена на заседании кафедры «___»____________ 2013 г Зав. кафедрой _______________________ Рекомендована секцией УМС «Информатика» «___»____________ 2013 г Председатель Визгунов А.Н. _______________________ Утверждена УМС НИУ ВШЭ – Нижний Новгород «___»_____________2013 г. Председатель Петрухин Н.С. _______________________ Нижний Новгород, 2013 1Область применения и нормативные ссылкиНастоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 080500.62 «Бизнес-информатика» подготовки бакалавра. Программа разработана в соответствии с: ОС ГОБУ ВПО ГУ-ВШЭ для направления подготовки бакалавра 080500.62 «Бизнес-информатика»; ООП для направления подготовки бакалавра 080500.62 «Бизнес-информатика»; Рабочим учебным планом университета для направления подготовки бакалавра 080500.62 «Бизнес-информатика», утверждённым в 2010 г. 2Цели освоения дисциплиныЦелями освоения дисциплины «Теоретическаяинформатика» являются изучение понятийного аппарата и применение полученных знаний к анализу математических моделей в различных предметных областях. 3Компетенции обучающегося, формируемые в результате освоения дисциплиныВ результате освоения дисциплины студент должен: Знать основные методы, применяющиеся в дискретной математике Уметь применять эти методы на практике Иметь навыки (приобрести опыт) решения задач, возникающих в различных прикладных областях В результате освоения дисциплины студент осваивает следующие компетенции:
4Место дисциплины в структуре образовательной программыНастоящая дисциплина относится к циклу математических и естественнонаучных дисциплин и блоку дисциплин, обеспечивающих подготовку бакалавра по направлению 080500.62 «Бизнес-информатика». Для направления «Бизнес-информатика» настоящая дисциплина является базовой. Изучение данной дисциплины базируется на знании материала курса «Дискретная математика» и основ программирования, а также навыках логического мышления. Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин: «Дискретные модели и сложность алгоритмов», «Методы трансляции и компиляции». 5Тематический план учебной дисциплины
6Формы контроля знаний студентов
6.1Критерии оценки знаний, навыковПри выполнении письменных контрольных работ, а также зачетной и экзаменационной работ, студент должен продемонстрировать умение решать конкретные задачи, знание теоретического материала и умение правильно применять его к решению задач, соблюдать логику решения. Оценки по всем формам контроля выставляются по 10-ти балльной шкале. 7Содержание дисциплины
Алфавит, цепочки в алфавите, язык как множество цепочек. Проблема определения бесконечного языка конечными средствами. Способы определения языка: механизм генерации и распознавания. Иерархия Хомского. Автоматы как способ распознавания языка. Формальные грамматики как способ генерации цепочек языка. Литература по разделу: [1] , [2,4].
Такт и конфигурация конечного автомата. Детерминированные и недетерминированные КА. Язык, допускаемый КА. Алгоритм построения детерминированного автомата по заданному недетерминированному. Автоматы с ԑ-тактами. Алгоритм построения ԑ-свободного автомата. Регулярные выражения. Теорема Клини об эквивалентности класса регулярных языков и конечно-автоматных языков. Анализ и синтез КА. Лемма о расширении регулярных множеств. Свойства замкнутости класса регулярных языков. Конечные преобразователи. Праволинейные грамматики. Эквивалентность праволинейных и регулярных языков. Литература по разделу: [1] , [2,3,5]
Формальное определение и схематическое представление МП-автомата. Операции с магазином. Эквивалентность МП-автоматов и КС-грамматик. Деревья выводов в КС-грамматиках. Неоднозначность КС-грамматик. Алгоритм удаления бесполезных символов. Нормальные формы КС-грамматик. Удаление левой (правой) рекурсии. Преобразователи с магазинной памятью. Литература по разделу: [1] , [2,3].
Нисходящий синтаксический анализ. Проблема построения дерминированного нисходящего анализатора. LL(k)- грамматики. Простая (разделенная) LL(1) – грамматика. Функции FIRST и FOLLOW.. Предсказывающий алгоритм разбора для LL(1) – грамматик. Литература по разделу: [1], [2,3,6].
Восходящий синтаксический анализ. Алгоритм перенос-свертка. LR(k)-грамматики. Детерминированный восходящий синтаксический анализ. Построение правых анализаторов для LR(k)-грамматик. Литература по разделу: [1], [2,3,4]. 8Образовательные технологииПри реализации учебной работы используется повторение основных теоретических положений лекционного материала и их применение при разборе практических задач. 9Оценочные средства для текущего контроля и аттестации студента9.1Тематика заданий текущего контроля
9.2Вопросы для оценки качества освоения дисциплины
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 Автор программы К.В.Логвинова |
|