Вступ

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

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

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

" Основы теории отношений, частичный порядок, алгебраические структуры, универсальные алгебры..

" Языки и грамматики. Алфавит, строки и подстроки. Операции над языками. Продукции, грамматики. Иерархия Хомского.

" Регулярные выражения. Детерминированные конечные автоматы (ДКА), язык ДКА. Диаграммы и таблицы переходов. Недетерминированные конечные автоматы (НКА). Эквивалентность ДКА и НКА. Конечные автоматы с ε-переходом. Связь автоматов с регулярными выражениями. Построение регулярного выражения по ДКА. ых выражений. Построение НКА по регулярному выражению. Свойства регулярных языков.

" Контекстно-свободные языки. Левые и правые порождения. Деревья разбора. Неоднозначность в грамматиках. Автоматы с магазинной памятью. Детерминированные МП-автоматы. Свойства контекстных языков. Нормальная форма Хомского. Лемма о расширении для контекстно-свободных языков.

" Методологии программирования. Императивное программирование, объектно-ориентированное программирование. Лямбда-исчисление, функциональное программирование, язык Лисп, операторы языка. Логическое программирование, хорновские выражения, язык логического программирования Пролог.

" Верификация программ. Постусловия, предусловия и слабейшие предусловия. Правила верификации Хоара. Аксиомы, правила логического вывода и правила логического следствия. Правила для последовательности операторов, условного оператора, цикла с предусловием.

" Неразрешимые проблемы. Абстрактные машины их использование в информатике. Неперечислимый язык, язык диагонализации. Рекурсивный и рекурсивно-перечислимый язык. Сведение одной проблемы к другой.

Мета та завдання

Задачи изучения дисциплины

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

ЗНАНИЯ:

- теоретических основ программирования;

- основ построения формальных языков и грамматик;

- систем программирования;

- семантики программ;

- основных методологий программирования;

- основ теории компиляции и вычислений.

УМЕНИЯ:

- строить формальные модели языков программирования и программ;

- планировать и строить компиляторы;

- выполнять доказательства правильности программ;

- строить грамматики простых языков программирования;

- работать с разными типами программного обеспечения.

Автори

кафедра компьютерных наук, секция "Информатика"

Бабий Михаил Семёнович
кандидат технических наук, доцент