Пояснительная записка Курс разработан для студентов 1 курса фртк мфти, обучающихся в лаборатории Intel




страница3/4
Дата28.08.2016
Размер0.52 Mb.
1   2   3   4

Годовой образовательный курс лаборатории Intel
«Введение в промышленное программирование на языках С, С++
и структуры данных»
для студентов 1 курса ФРТК, 2 ч. лекций + 2 ч. семинаров в неделю
(сокращенный вариант)


И. Р. Дединский, ст. преп. каф. информатики МФТИ

Пояснительная записка


Курс разработан для студентов 1 курса ФРТК МФТИ, обучающихся в лаборатории Intel.

Цель курса – научить студентов современным методам программирования и разработки программных систем на языках С и С++, привить навыки надежного, промышленного программирования, работы в команде, подготовить их для участия в тематических проектах второго курса ILab.

Преподавание курса ведется в предположении, что студенты уже знают язык Паскаль или аналогичный процедурный язык. Курс разбит на 2 части:

Первая (5-6 занятий) – быстрое практическое введение в С через разбор и решение большого количества небольших задач, заканчивающееся потоковой контрольной работой с автоматической проверкой.

Вторая (11-12 занятий) – введение в структуры данных и алгоритмы, практическая часть которой содержит меньшее число задач, но большего объема.

Задачи второй части подобраны по большей части таким образом, что в конце курса каждый студент самостоятельно реализует примитивную модель вычислительной системы (стековой виртуальной машины), инструментальные средства низкоуровневой разработки для него (ассемблер и дизассемблер), а также примитивный высокоуровневый транслятор (проект «нано-GCC»).

Третья часть курса (6-10 занятий) представляет собой введение в язык С++ в терминах различий С и С++, методом рефакторинга ряда решений на языке С, рассматривавшихся в осеннем семестре.

Четвертая часть (6-10 занятий) посвящена технологии применения С++ (ООД, ООП, компонентное программирование) в многомодульном проекте, использующем программный код группы разработчиков в виде динамически подключаемых библиотек.

Сложность задач курса легко регулируется их функциональным наполнением (простейший вариант – транслятор формул, используемый для построения графиков элементарных функций).

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

Сдача работ студентами осуществляется через помещение его на серверный репозиторий курса. Основная форма проверки кода менторами – детальный code review с разбором типичных случаев на групповых занятиях. Со второй части курса вводится peer review.

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


Содержание курса (по семестрам)

I семестр




Содержание темы

К-во часов

Лек.

Сем.



Введение в язык С. Краткая история и особенности возникновения языка. Ключевая роль Си в обучении программированию. Высокоуровневые и низкоуровневые языки. Высокоуровневые языки. Переносимость высокоуровневых программ. Проблемы с производительностью и доступом к вычислительным средствам из языков высокого уровня.. Си как язык промежуточного уровня, задуманный и построенный как компромисс между низким и высоким уровнем. Командная разработка проектов. Системы контроля версий, репозитории и работа с ними. Системы контроля версий SVN Code review в системе контроля версий. Типичный рабочий процесс при работе с системой контроля версий SVN и репозиторием Google Code в Linux и Windows. Рабочий процесс для code review в ILab.

Тестирование программ. Тестирование с помощью специальных программ (серверов).



2

2



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

Введение в язык Си. Структура и синтаксис простейшей программы на языке Си. Раздел включаемых заголовочных файлов, главная программа. Объявление переменных, типы данных (на примере int и double). Ввод и вывод информации, функции printf и scanf. Арифметические выражения, операторы сложения, вычитания, умножения и деления, оператор присваивания. Функция вычисления квадратного корня. Условный оператор.



2

2



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

Понятие определения функции, ее заголовка и тела. Формальные параметры функции квадратного уравнения (коэффициенты), синтаксис их объявления. Понятие и синтаксис вызова функции. Понятие прототипа функции, синтаксис. Модульный принцип построения программ. Передача данных через оператор return. Анализ возвращаемого значения в main, оператор switch, его синтаксис. Проблема передачи информации о бесконечном количестве корней. Использование «магических чисел» и именованных констант для обозначения бесконечного количества корней. Синтаксис определения именованной константы. Указатели, передача данных через параметр-указатель. Макрос assert, его применение для проверки указательных параметров, информативность для программиста при отладке.



2

2



Комментирование кода. Блочные комментарии файла и функции. Препроцессор языка C. Директивы препроцессора. Директива include для стандартных заголовочных файлов. Директива define. Использование директивы для задания констант, ее отличия от конструкции с const. Директива define с параметрами. Особенности и побочные эффекты в случае макроопределения с параметрами, ее отличие от функций. Классические примеры построения макроопределения с параметрами с демонстрацией побочных эффектов и защитой параметров скобками. Продолжение макроопределения на следующие строки с помощью символа обратной косой черты. Ошибки применения define: использование аргументов с побочным эффектом (инкремент/декремент переменных, вызовы функций, работающих с потоками и т.п.)Стандартные макроопределения __FILE__, __LINE__, __DATE__, __TIME__. Разбор механизма влияния NDEBUG на assert, условная компиляция. Директивы #ifdef, #ifndef, #if (и синтаксис допустимых в нем конструкций), #else, #elif, #endif.

2

2



Массивы в языке Си. Использование массивов для хранения серий данных. Объявление и инициализация массива. Ограничения массивов в Си (нумерация, единство типа данных, ограниченный размер). Хранение массивов в оперативной памяти. Адресация к массиву. Имя массива как адрес (указатель) его начального элемента. Типичные ошибки при работе с массивами (выход за границы массива).Проверка допустимости индексации с помощью assert. Решение проблемы волатильности с помощью модификатора const.

2

2



Динамическая память в языке Си. Понятие «свободной памяти». Функции работы с динамической памятью. Время жизни блока динамической памяти. Динамическая память как ресурс, работа с исчерпанием памяти, реализация стратегий гарантированного освобождения. Пример структуры блока динамической памяти. Последствия выхода за границы блока, двойного освобождения блока, переполнения буфера, находящегося в динамической памяти. Реаллокация блоков динамической памяти, проблема пересчета указателей в случае изменения адреса блока. Указательная арифметика. Операции с указателями в языке См. Формула вычисления адреса для доступа к элементу массива. Использование указательной арифметики для потоковых вычислений на массивах, понятие «текущего элемента».

2

2



Многомерные массивы, их объявление, инициализация, адресация в них. Проблема передачи многомерного массива в функцию. Вычисление адреса элемента в многомерном массиве. Необходимость передавать размеры многомерного массива в функцию. Самостоятельное вычисление смещения относительно начала массива и адреса нужного элемента массива, преимущества и недостатки такого подхода. Реализация многомерных массивов в динамической памяти, доступ к таким массивам.

Массивы указателей. Синтаксис объявления и использования массивов указателей. Трактовка операции индексации в случае массивов указателей. Реализация многомерных массивов через массивы указателей, Решение вопроса о хранении массива с «рваным правым краем» (неодинаковым размером строк). Использование разных блоков для хранения разных строк массива, возможность реаллокации для изменения длин строк.



2

2



Строки. Реализация строк в языке Си, «смысловая» и «свободная» зоны строки, Нулевой символ. Понятие пустой строки. Задачи о копировании и сравнении строк, задача о сжатии пробелов в строке «на месте». Концепция «текущего символа». Проблемы «маляра Шлемиля (Шлемиэля)», их характерные проявления и устранение. Возможности строковой библиотеки языка Си. Массивы строк. Задача о сортировке строк, обобщение алгоритмов сравнения строк. Указатели на функции. Использование указателей на функции для построения универсальной функции сортировки строк. Библиотечная функция qsort и работа с ней.

Работа с файлами. Функции открытия и закрытия файла. Текстовые файлы, посимвольное и построчное считывание. Состояние «конец файла», константа EOF. Опасность переполнения буфера при чтении. Форматированный текстовый ввод и вывод, опасности, с ним связанные. Символы преобразования данных и форматирования. Бинарные файлы. Перемещение по файлу.



2

2



Структуры. Операции доступа к структурам. Построение структур, размер структуры. Передача структур в функцию, способы ее ускорения (через указатель) и защиты доступа (через указатель на константные данные). Реализация «методов класса» средствами языка Си.

2

2



Понятие абстрактных структур данных.Структура данных «стек».Функции для работы со стеком. Функции конструирования, уничтожения, верификации и технической распечатки (дампа). Пример реализации функции дампа. Использование стека. Задача о вычислении выражений. Вычисление выражений, заданных обратной польской записью. Понятие стекового вычислителя (процессора). Реализация структуры стекового вычислителя и связанных с ней функций. Реализация арифметических команд для стекового вычислителя. Примеры работы стекового вычислителя. Интерактивный режим работы программы вычисления выражений. Задача о построении таблицы значений функции или ее графика. Понятие регистра вычислителя (процессора), введение регистра абсциссы (АХ) в стековый вычислитель. Функция на языке Си для загрузки значения абсциссы в вычислитель (mov_ax).

2

2



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

2

2



Расширение круга задач для стекового вычислителя. Обобщение постановки задачи для построения таблиц значений (графиков) функций с необходимостью единственного исполнения программы и организации перебора значений аргумента в Р-программе. Пример возможной Р-программы для построения таблиц значений (графика) функции. Необходимость команд текстового или графического вывода данных (out), команд условного и безусловного переходов (j*, jmp) для организации цикла в Р-программе. Проблема аргумента в командах переходов. Реализация команд переходов с помощью вручную рассчитанных адресов переходов, недостатки такого подхода. Задача автоматического расчета адресов переходов. Понятие меток как синонимов адресов. Реализация вызова функций в стековом вычислителе. Сравнение работы команд вызова функции и безусловного перехода. Понятие возврата из функции. Реализация команд вызова функции с аргументом в виде метки и возврата из функции с помощью отдельного стека для хранения адресов возврата.

Выполнение задач на стековом вычислителе в виде написания самостоятельно разработанных Р-программ (решение квадратных уравнений с разбором всех частных случаев, выдачей количества и величин их корней, вычисления факториала чисел и чисел Фибоначчи итеративным и рекурсивным способами). Расширение количества регистров (добавление регистров bx, cx, dx), системы команд (добавления команды ввода с клавиатуры in).



2

2



Структура данных «список». Использование списков. Односвязные и двусвязные списки. Неэффективность операции индексации для списков (еще один пример «алгоритма маляра Шлемиля»).Проверка валидности списка,

Структура данных «хеш-таблица». Задачи, приводящие к хеш-таблицам. Хеш-функции, их примеры (от простейших и бесполезных к реальным) и свойства, качество хеширования. Характерные размеры хеш-таблиц. Использование хеш-таблиц. Качественное сравнение качества хеширования с помощью гистограммы заполнения хеш-таблицы.



2

2



Структура данных «дерево». Примеры различного использование деревьев. Деревья поиска. Перечисление узлов дерева, виды обходов дерева. Верификация деревьев. Дамп деревьев. Задачи, использующие деревья.

Структура арифметических выражений. Инфиксная форма записи выражений, ее соответствие порядку действий и дереву вычислений. Задача о грамматическом разборе выражений. Необходимость задания структуры выражений. Понятие языка и грамматики. Способы построения дерева разбора. Алгоритм распознавания языка методом рекурсивного спуска. Различные обходы деревьев выражений, восстановление линейной инфиксной записи и генерация различных видов польских записей (префиксной, постфиксной). Транслятор инфиксных выражений в ассемблер стекового процессора.



Лексический анализ как предварительная фаза перед синтаксическим, его роль в повышении эффективности трансляции и ее упрощении. Понятие лексемы, ее реализация. Рефакторинг транслятора с применением лексического анализа.

2

2



Архитектура nGCC. Front-end, middle-end и back-end. Достоинства модульного принципа и общего внутреннего формата. Разработка общего внутригруппового стандарта промежуточного файла с AST, поддерживающего дополнительные данные (имена переменных и т.п.). Рефакторинг транслятора инфиксных выражений с использованием архитектуры nGCC. Реализация программы для запуска частей транслятора (драйвера). Реализация обратного преобразования (из AST в код модельного высокоуровневого языка).

2

2




Всего за 1 семестр

30

30
1   2   3   4


База данных защищена авторским правом ©infoeto.ru 2016
обратиться к администрации
Как написать курсовую работу | Как написать хороший реферат
    Главная страница