Современные методы и понятия программирования

Программа курса «Современные методы и понятия программирования» на 2012-1013 гг
составил доцент, к.ф.-м.н. Бульонков М.А.

software-development
ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Целью курса является освоение студентами базовых понятий базовых понятий и методов
программирования. Вводная часть курса даѐт представление о различных сторонах
программировании — как инженерной деятельности, как методологии и как научной дисциплины –
и их взаимосвязи. Основная часть курса построена вокруг рассмотрения языков
программирования, того, как используются и реализуются различные языковые конструкции.
Несмотря на то, что основным языком, рассматривым в курсе, является язык С, детальное освоение этого языка не ключевой целью. Практика современного программирования такова, что даже в рамках одной системы разработчик использует несколько языков, и способность осознанного выбора подходящего языка и инструментария является одним из основных профессиональных качеств. Достаточно низкий уровень большинства рассматриваемых языков также не случаен: он позволяет проследить не только назначение языковых конструкций, но и насколько эффективную реализацию они допускают. Предполагается, что на основе такого знания студент сможет более осознанно изучать и использовать на практике современные языки более высокого уровня рассматриваемые в последующих курсах.

Таким образом, у студента должен быть сформирован кругозор и понимание того, что и сами
языки программирования являются «живыми» объектами со своей логикой развития. Курс
представляет базовые средства – БНФ грамматики и синтаксические диаграммы — для описания
языков программирования. Большая часть курса посвящена рассмотрению наиболее
распространѐнных концепций, таких как типы данных, вычисления, управление на уровне
выражений и операторов, модульная структура программы и т.п. При этом стимулируется
альтернативное рассмотрение различных конструкций, позволяющих реализовать одну и ту же
задачу.

Заканчивается курс краткое рассмотрение вопросов анализа сложности программ, некоторых
методов преобразование и оптимизации программ. Студенты, слушающие курс, должны усвоить,
что собственно кодирование составляет весьма незначительную часть деятельности программиста, а существенно более важные вопросы: понимаемость, сопровождаемость и эффективность программного обеспечения.
СОДЕРЖАНИЕ ЛЕКЦИЙ
Лекция 1. Области программирования как научно-технической дисциплины: пользовательское
программирование, системное программирование, технология программирования, теоретическое
программирование. Логическая модель ЭВМ. Дискретная память: байты, биты, слова, адресация.
Вычислитель: виды команд управление и вычисление. Внешние и внутренние функции операционной системы: управление устройствами и ресурсами, запуск процессов, файловая
система, пользовательский интерфейс. Классификация языков программирования: машинный
язык, языки макроассемблера, языки высокого и сверхвысокого уровня. Императивные,
логические, фукциональные языки программирования.

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

Лекция 3. Понятие языка программирования как знаковой системы. Понятие лексики, синтаксиса
и семантики. Формальное описание лексики и синтаксиса. Форма Бэкуса-Наура, регуляризованная БНФ. Проблема национальных версий языков программирования. Контекстно-свободный и
контекстно-зависимый синтаксис. Понятие синтаксического вывода и дерева разбора. Проблема
неоднозначности. Синтаксические диаграммы. Устойчивость синтаксиса к ошибкам.

Лекция 4. Контекстно-зависимый анализ, анализ типов. Общее понятие об операционной,
функциональной и аксиоматической семантиках. Понятие стиля в программировании:
структурирование текста, мнемоничность имѐн, комментирование исходного текста. Понятие
прагматики языковых конструкций. Преемственность языков программирования, обратная
совместимость.

Лекция 5. Препроцессор: назначение, язык препроцессора. Директивы препроцессора на примере
языка С: включение файлов, определение и использование макропеременных, предопределѐнные
макропеременные, условная трансляция, конструирование лексем. Проблемы использования
препроцессоров: дублирование кода, невозможность рекурсии, несоответствие директив структуре
программы,

Лекции 6. Объекты и типы данных. Области видимости, блочная структура, правила поиска.
Присоединяющие операторы и квалификация имѐн. Способы импорта библиотечных имѐн.
Анонимные объекты. Понятие типа данных: моделируемая категория, синтаксис, множество
литеральных значений, набор операций, реализация доступа к памяти. Статический и
динамический анализ типов, их достоинства и недостатки. Строгая типизация. Полиморфизм.
Классификация типов данных: предопределѐнные и определяемые, простые и структурированные,
неупорядоченные, упорядоченные и перечислимые, арифметические.

Лекция 7. Описание базовых типов на примере языков С и Pascal. Символы как целочисленные
коды, необходимость многобайтных кодировок. Различные представления целых и вещественных
чисел. Числа с фиксированной и плавающей точкой, проблема потери точности. Множества и
битовые шкалы, битовая арифметика. Логические значения и логические связки. Понятие
приведения типов.Лекция 8. Указатели на примере языка С. Адресная арифметика, тип void*. Реализация массивов как указателей. Виды массивы в других языках программирования: многомерные, динамические, подвижные, непрямоугольные, массивы-дескриторы. Массовые операции над массивами на примере языков Альфа и APL. Строки на примере языков С и Pascal.

Лекция 9. Структуры и объединения, понятие выравнивания, псевдооперация sizeof. Проблема
«дыр» в контроле типов, связанных с типом объединения и пример еѐ решения в Algol-68.
Присваивание,как элементарное действия изменения состояния памяти. Побочные эффекты.
Операции, совмещѐнные с присваиванием, инкремент и декремент.

Лекция 10. Управление в программе. Управление на уровне выражений, приоритет операций,
последовательные и условные выражения, связки Маккарти. Управление на уровне операторов:
оператор goto и его недостатки. Условные операторы: логические, арифметические,
переключатели, переходы по вычисляемой метке, на примере Pascal, C, Fortran. Оператора цикла:
for, while, repeat, циклы по множеству, переменные и границы цикла. Операторы выхода и
продолжения цикла на примерах языков C, Pascal, Альфа, SETL, Java.

Лекция 11. Распределение памяти: глобальная, автоматическая, динамическая. Динамическое
создание и удаление объектов и массивов. Накладные расходы и типчные ошибки. Автоматическая сборка мусора. Примеры представления динамических структур данных: деревья, односвязные и двусвязные списки, стеки, очереди, упорядоченные списки, вагонная память.

Лекция 12. Процедуры и функции: описание и вызов на примере С, формальные и фактические
параметры. Выполнение функции: автоматическая память, связывание параметров, выполнение
тела. Оператор возврата. Граф вызовов и дерево вызовов, поколения переменных. Рекурсия:
достоинства и недостатки. Вложенные процедуры на примере Pascal, динамический контекст.
Переменное число параметров, необязательные параметры, позиционные и именованные
параметры.

Лекция 13. Виды подстановки параметров. Подстановка параметров по ссылке, процедуры с
несколькими результатами. Проблема синонимов. Подстановка параметров по значению-результату.
Строгое и нестрогое вычисление параметров. Подстановка параметров по имени. Подстановка
параметров по необходимости. Процедурные параметры: функции обратного вызова (callback).

Лекция 14. Реализация функций. Преобразование функций в процедуры. Преобразование в
функции с одним параметром. Использование стека фреймов. Реализация возврата из процедуры,
вычисляемые метки, устранение процедур. Перемещение кода. Обработка исключительных
ситуаций: коды ошибок, выход из глубокой рекурсии, нелокальные переходы setjmp/longjmp.
Модульная структура программы, классы памяти.

Лекция 15. Ввод-вывод: логические и физические файлы, связь с объектами операционной
системы. Виды языковых конструкций ввода-вывода: специальные конструкции,
псевдопроцедуры, типизированные процедуры, форматный вывод (на пример C, Fortran, Modula-
2). Низкоуровневый ввод-вывод: достоинства и недостатки. Буферизованный ввод-вывод: типичные ошибки использования файлов. Стандартные файлы ввода-вывода. Форматный вывод:
язык форматирования данных. Ввод-вывод указательных структур данных.

Лекция 16. Оценка сложности программ: временная и ѐмкостная сложность, асимптотическое
поведение. Сравнительный анализ алгоритмов. Примеры оптимизации и пессимизации программ

http://mmf.nsu.ru/sites/default/files/Program1-Bulyonkov-2012.pdf

Добавить комментарий