Программа дисциплины «Теоретическая информатика» - gozda.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Программа дисциплины «Теоретическая информатика» - страница №1/1

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

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

Факультет бизнес-информатики и прикладной математики

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

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

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

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

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

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


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

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


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

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

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

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


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

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

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

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

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

Правительство Российской Федерации >>
Государственный университет – Высшая школа экономики Программа дисциплины Информационные системы в организациях для направления 080700.68 Бизнес-информатика подготовки магистра Правительство Российской Федерации Государственное образовательное бюджетное учреждение высшего профессионального образования «Государственный университет - Высшая школа экономики» Нижегородский филиал Факультет Бизнес-информатики и прикладной математики Программа дисциплины Информационные системы в организациях  для направления 080700.68 «Бизнес-информатика» подготовки магистра Автор программы: Шутов А.А., ст. преподаватель, ashutov@hse.ru Одобрена на заседании кафедры Информационных систем и технологий «___»____________ 2010 г Зав. кафедрой Э.А. Бабкин Рекомендована секцией УМС «Математика и информатика» «___»____________ 2010 г Председатель В.М. Демкин Утверждена УМС НФ ГУ-ВШЭ «___»_____________2010 г. Председатель Л.Г. Макарова ____________________ Нижний Новгород, 2010 Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы. 1Область применения и нормативные ссылки Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 080700.68 «Бизнес-информатика», обучающихся по магистерской программе «Бизнес-информатика». Программа разработана в соответствии с: ФГОС направления 080700 Бизнес-информатика, степень (квалификация) — магистр бизнес-информатики. Образовательной программой 080700.68 Бизнес-информатика. Рабочим учебным планом университета по направлению подготовки 080700.68 Бизнес-информатика, утвержденным в 2010г. 2Цели освоения дисциплины Целями освоения дисциплины «Информационные системы в организациях» является освещение ключевых вопросов, связанных с информатизацией современного общества и использованием автоматизированных информационных технологий и систем для повышения эффективности экономической и управленческой деятельности. 3Компетенции обучающегося, формируемые в результате освоения дисциплины В результате освоения дисциплины студент должен:

Правительство Российской Федерации >>
Национальный исследовательский университет «Высшая школа экономики» Программа дисциплины «Архитектура предприятия» для направления 38.04.05 «Бизнес-информатика» подготовки магистра Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики" Факультет бизнес - информатики Программа дисциплины Совершенствование архитектуры предприятия по направлению подготовки 38.04.05 БИЗНЕС-ИНФОРМАТИКА Уровень подготовки: Магистр Автор программы: Понфиленок М.В., преподаватель, E-mail: ponfilenok@hse.ru Казанцев Н.С., преподаватель, E-mail: nkazantsev@hse.ru Горчаков Я.В., доцент, E-mail: jagorchakov@hse.ru Худобин Е.И. преподаватель Одобрена на заседании кафедры Моделирования и оптимизации бизнес-процессов «___» ____________ 20 г Зав. кафедрой А.И. Громов Рекомендована секцией УМС факультета бизнес-информатики «___»____________ 20 г Председатель Утверждена УС факультета факультета бизнес-информатики «___»_____________20 г. Ученый секретарь ________________________ [подпись] Москва, 2014 Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы Область применения и нормативные ссылки Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 38.04.05 «Бизнес-информатика» подготовки магистра. Программа разработана в соответствии с: Образовательным стандартом Федерального государственного автономного образовательного учреждения высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики», уровень подготовки: магистр, утвержденным Ученым советом НИУ ВШЭ, Протокол от 24.06.2011 г. № 26; Рабочим учебным планом НИУ ВШЭ по направлению 38.04.05 бизнес-информатика подготовки магистра 1 курса, утвержденным в 2014 г. Цели освоения дисциплины

Аннотация к ПРОГРАММе УЧЕБНОЙ ДИСЦИПЛИНЫ РУССКИЙ ЯЗЫК И КУЛЬТУРА РЕЧИ >>
к ПРОГРАММе УЧЕБНОЙ ДИСЦИПЛИНЫ РУССКИЙ ЯЗЫК И КУЛЬТУРА РЕЧИ Область применения программы Программа учебной дисциплины является частью основной профессиональной образовательной программы в соответствии с ФГОС, по специальности СПО 230701 «Прикладная информатика (по отраслям)» 1.2. Место учебной дисциплины в структуре основной профессиональной образовательной программы: общепрофессиональные дисциплины. 1.3. Цели и задачи учебной дисциплины – требования к результатам освоения учебной дисциплины: В результате освоения учебной дисциплины обучающийся должен уметь: - строить и анализировать свою речь в соответствии с языковыми и коммуникативными нормами; - устранять ошибки в устной и письменной речи в соответствии с нормами русского литературного языка; пользоваться словарями и справочниками. - использовать средства художественной выразительности; - продуцировать тексты деловых и учебно-научных жанров В результате освоения учебной дисциплины обучающийся должен знать: - различия между языком и речью, их коммуникативные функции; - языковые нормы, их разновидности; - нарушение норм современного русского литературного языка и способы их устранения; - признаки текста и его стилистическую принадлежность; 1.4. Количество часов на освоение программы учебной дисциплины: максимальной учебной нагрузки обучающегося 83 часа обязательной аудиторной учебной нагрузки обучающегося 55 часов; самостоятельной работы обучающегося 28 часов. 2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ 2.1. Объем учебной дисциплины и виды учебной работы Вид учебной работы Количество часов Максимальная учебная нагрузка (всего) 83 Обязательная аудиторная учебная нагрузка (всего) 55 в том числе: практические занятия 16 контрольные работы 2 Самостоятельная работа обучающегося (всего) 28

Правительство Российской Федерации >>
Национальный исследовательский университет «Высшая школа экономики» Программа дисциплины «Проектирование информационных систем» для направления 38.04.05 «Бизнес-информатика» подготовки магистра Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики" Факультет бизнес-информатики Программа дисциплины Проектирование информационных систем (адаптационный курс) по направлению подготовки 38.04.05 БИЗНЕС-ИНФОРМАТИКА Уровень подготовки:Магистр Автор программы: Грекул В.И., к.т.н., профессор, grekoul@hse.ru Коровкина Н.Л., доцент, nkorovkina@hse.ru Одобрена на заседании кафедры корпоративных информационных систем « » сентября 2014 г Зав. кафедрой. Грекул В.И. ________________________ Рекомендована секцией УМС «Бизнес-информатика» «___»____________ 2014 г Председатель Таратухина Ю.В. ________________________ Утверждена УС факультета бизнес-информатики «___»_____________2014 г. Ученый секретарь Фомичев В.А. ________________________ Москва, 2014 Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы. 1Область применения и нормативные ссылки Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 38.04.05 «Бизнес-информатика» подготовки магистра. Программа разработана в соответствии: с образовательным стандартом Федерального государственного автономного образовательного учреждения высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики», уровень подготовки: магистр, утвержденным 26.06.2011; рабочим учебным планом университета по направлению 38.04.05 бизнес-информатика подготовки магистра для магистерской программы «Бизнес-информатика», специализация «Управление жизненным циклом информационных систем», специализация «Бизнес-аналитика», «Моделирование и оптимизация бизнес-процессов», утвержденными в 2012 г. 2Цели освоения дисциплины

Правительство Российской Федерации >>
НИУ ВШЭ – Нижний Новгород Программа дисциплины «Телекоммуникационные технологии» для направления 010400.62 – Прикладная математика и информатика подготовки бакалавра Правительство Российской Федерации Нижегородский филиал Федерального государственного автономного образовательного учреждения высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики" Факультет бизнес-информатики и прикладной математики Программа дисциплины «Телекоммуникационные технологии» для направления 010400.62 – Прикладная математика и информатика подготовки бакалавра Автор программы: старший преподаватель И.В.Стеклов e-mail: i.steklov@font.nnov.ru Одобрена на заседании кафедры «Базовая кафедра МЕРА» «___»____________ 2012г. Зав. кафедрой Н.И.Кащеев Рекомендована секцией УМС «Прикладная математика» «___»____________ 2012г. Председатель В.А. Калягин Утверждена УМС НИУ ВШЭ – Нижний Новгород «___»_____________2012 г. Председатель Н.С. Петрухин Нижний Новгород, 2012 г. Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы. Область применения и нормативные ссылки Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений 010400.62 – Прикладная математика и информатика подготовки бакалавра, изучающих дисциплину «Телекоммуникационные технологии». Программа разработана в соответствии с образовательным стандартом федерального государственного образовательного автономного учреждения высшего профессионального образования Высшая школа экономики, учебным планом университета по направлению 010400.62 – Прикладная математика и информатика, утвержденным в 2012г. Цели освоения дисциплины Целью освоения данной дисциплины является познакомить слушателей с основными тенденциями развития сетевых технологий, в частности , с концепцией Глобальной информационной инфраструктуры и принципами построения её сетевой инфраструктуры, включая методы интеграции глобальных компьютерных сетей с телекоммуникационными технологиями , принципы построения и функционирования систем цифровой электросвязи интегрального обслуживания , систем мобильной связи , а также интеллектуальной сети . Компетенции обучающегося, формируемые в результате освоения дисциплины

Правительство Российской Федерации >>
Национальный исследовательский университет «Высшая школа экономики» Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики" Факультет Информационных технологий и вычислительной техники Программа дисциплины Математическая логика и теория алгоритмов  для направления 230100 “Информатика и вычислительная техника” подготовки бакалавра Автор программы: Афонина Л.М. E-mail: lafonina@hse.ru Одобрена на заседании кафедры Вычислительные системы и сети «___»____________ 20 г Зав. кафедрой А.В. Вишнеков Рекомендована секцией УМС [Введите название секции УМС] «___»____________ 20 г Председатель [Введите И.О. Фамилия] Утверждена УС факультета Информационных технологий и вычислительной техники «___»_____________20 г. Ученый секретарь [Введите И.О. Фамилия] ________________________ [подпись] Москва, 2012 1Область применения и нормативные ссылки Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 230100 “Информатика и вычислительная техника”, изучающих дисциплину “Математическая логика и теория алгоритмов”. Программа разработана в соответствии с: Федеральным государственным образовательным стандартом высшего профессионального образования по направлению 230100 "Информатика и вычислительная техника" (квалификация "бакалавр"); Образовательной программой по направлению 230100.62 "Информатика и вычислительная техника" подготовки бакалавра по специализации "Вычислительные машины, комплексы, системы и сети"; Рабочим учебным планом университета по направлению 230100.62 "Информатика и вычислительная техника" подготовки бакалавра по специализации "Вычислительные машины, комплексы, системы и сети". 2Цели освоения дисциплины Целью освоения дисциплины “Математическая логика и теория алгоритмов” является изучение понятий и практическое освоение методов математической логики и теории алгоритмов с ориентацией на их использование в задачах практической информатики. 3Компетенции обучающегося, формируемые в результате освоения дисциплины

Национальный исследовательский университет >>
Программа дисциплины «Выпуклый анализ» >>
Национальный исследовательский университет «Высшая школа экономики» Программа дисциплины «Выпуклый анализ» для направления 010400.68 «Прикладная математика и информатика» подготовки магистра Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования Национальный исследовательский университет "Высшая школа экономики" Факультет Бизнес-информатики отд. Прикладной математики и информатики Программа дисциплины Выпуклый анализ для направления 010400.68 «Прикладная математика и информатика» подготовки магистра специализация «Анализ и принятие решение» Автор программы: Беленький Александр Соломонович Одобрена на заседании кафедры высшей математики на факультете экономики 25.02.2013 г. Зав. кафедрой Алескеров Ф.Т. Рекомендована секцией УМС [Введите название секции УМС] «___»____________ 20 г Председатель Утверждена Ученым Советом факультета экономики «___»_____________20 г. Ученый секретарь Москва, 2012 Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы. 1Область применения и нормативные ссылки Настоящая программа учебной дисциплины устанавливает требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 010400.68 «Прикладная математика и информатика», обучающихся по магистерской программе «Математическое моделирование» по специализации «Анализ и принятие решений», изучающих дисциплину «Выпуклый анализ». Программа разработана в соответствии с: Образовательным стандартом государственного образовательного бюджетного учреждения высшего профессионального образования «Государственный университет – Высшая школа экономики», в отношении которого установлена категория «Национальный исследовательский университет»; Рабочим учебным планом университета подготовки магистра по направлению 010400.68 «Прикладная математика и информатика» подготовки магистра, утвержденным в 2011 г. 2Цели освоения дисциплины Целями освоения дисциплины «Выпуклый анализ» являются

Национальный исследовательский университет Высшая школа экономики Факультет бизнес - информатики Программа дисциплины «Теоретические основы информатики» для направления 080700.62 – « Бизнес – информатика» подготовки бакалавров 1 курса Автор д.т.н., с.н.с. А.П.Кирсанов Рекомендовано секцией УМС Одобрено на заседании Секция «Бизнес-информатика» кафедры бизнес-аналитики Председатель Зав. кафедрой ______________ Ю.В.Таратухина ______________ Т.К.Кравченко «____» ________________ 2011 г. «____» _______________ 2011 г. Утверждено Ученым советом факультета бизнес-информатики Ученый секретарь _________________ В.А.Фомичев «____» _________________2011 г. Москва – 2011 1. Цели и задачи дисциплины: Освоение теоретических основ информатики, необходимых для изучения, понимания и разработки прикладных информационных технологий и систем. 2. Место дисциплины в структуре ООП: дисциплина относится к математическому и естественнонаучному циклу; приступая к изучению дисциплины, студенты должны знать основы линейной алгебры (матрицы и матричные операции, векторные пространства, системы линейных уравнений и методы их решения, пространство решений) дискретной математики (множества, отношения, операции над отношениями, графы, деревья), комбинаторики (основные комбинаторные объекты и комбинаторные тождества), теории вероятности (понятие вероятности, дискретные случайные величины и их вероятностные распределения, математическое ожидание случайной величины); дисциплина является предшествующей для дисциплин: Основы формальной лингвистики, Базы, данных, Информационная безопасность, Распределенные системы, Архитектура корпоративных информационных систем. 3. Требования к результатам освоения дисциплины: Процесс изучения дисциплины направлен на формирование следующих компетенций: готовность использовать основные информационные технологии в профессиональной деятельности, применять методы теоретического и экспериментального исследования; владение культурой мышления, способность к обобщению, анализу, восприятию информации, постановке цели и выбору путей еѐ достижения; способность анализировать и моделировать социально-значимые процессы, происходящие в обществе, и прогнозировать возможное их развитие в будущем В результате изучения дисциплины студент должен: Знать: – теоретические основы информатики и тенденции её развития, принципы реализации процессов передачи, хранения, поиска и обработки информации, основные области применения информационных технологий;

Рабочим учебным планом университета для направления подготовки бакалавра 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

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