Программа курса ПРОГРАММИРОВАНИЕ

(Пятый и шестой семестры)
Лектор: Соловьев Сергей Юрьевич

Преподаватель практических занятий: Соловьев Сергей Юрьевич
Описание курса:
«Программирование» – годовой курс для студентов 3-го года обучения факультета математики ГУ-ВШЭ. Это – базовый курс программирования на языках высокого уровня для студентов, специализирующихся в области математики. Его пререквизиты – курсы дискретной математики, линейной алгебры и математического анализа. Курс преподается на русском языке.

Акцент в курсе делается на практическом освоении программирования на языке С++. Основные конструкции языка иллюстрируются на примерах классических вычислительных задач. Кроме того, значительное внимание в курсе уделяется технологиям программирования, вообще, и объектно-ориентированному программированию в частности.

Цели курса:

Студенты должны получить знания и навыки в области практического программирования на языке C++. Они должны уметь применять полученные знания в индивидуальном и коллективном программировании, а также должны понимать методы, идеи, результаты и выводы, встречаемые в большинстве вычислительных задач экономического содержания. В данном курсе студенты должны освоить традиционные методы программирования, предназначенные в основном для решения отдельны вычислительных задач. Студенты должны знать и уметь практически применять основные технологии программирования и отладки программ. Рассматриваемые методы и технологии должны быть освоены на практике с использованием реальных массивов данных.

Методы:

В курсе используются следующие методы и формы работы:

• 
  лекции (2 часа в неделю)
  
• 
  практические занятия в компьютерном классе (2 часа в неделю, выполняются задания на компьютерах и обсуждаются основные вопросы домашних заданий);
  
• 
  контрольные работы (4 шт.);
  
• 
  домашние задания (2 шт.);
  
• 
  консультации преподавателя;
  
• 
  самостоятельная работа в компьютерном классе, в том числе в Интернет;
  
• 
  самостоятельная работа с литературой;
  
• 
  сдача зачетов (2 шт.) и экзаменов (2 шт.).
  

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

Основная литература:

1. 
   Страуструп Б. Язык программирования С++. Специальное издание. – СПб.: Бином, Невский диалект, 2008.
   
2. 
   Фридман А.Л. Основы объектно-ориентированного программирования на языке Си++. – М.: Горячая линия – Телеком, Радио и связь, 1999.
   
3. 
   Форд А.Р., Теори Т.Дж. Практическая отладка в С++. – М.: КУДИЦ-ОБРАЗ, 2002.
   

Дополнительная литература:

1. 
   Страуструп Б. Дизайн и эволюция С++. – СПб.: ДМК-Пресс, 2006.
   
2. 
   Тан К.Ш., Стиб В.-Х., Харди Й. Символьный С++: Введение в компьютерную алгебру с использованием объектно-ориентированного программирования. – М.: Мир, 2001.
   
3. 
   Топп У., Форд У. Структуры данных в С++. – М.: ЗАО “Издательство БИНОМ”, 2000.
   
4. 
   Давыдов В.Г. Технологии программирования. С++. – СПб.: БХВ-Петербург, 2005.
   
5. 
   Березин И.С., Житков Н.П. Методы вычислений. т.1,2 - М.: Гос. изд-во физ-мат литературы, 1962.
   
6. 
   Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.
   

Принципы оценки работы студентов:
В рамках данного курса предусмотрено проведение 4 контрольных работ и сдача 2 домашних заданий. Основная форма контроля – два зачета и два экзамена. Необходимым условием отличной оценки на экзаменах является отлично выполненные контрольные работы (25% итоговой оценки), сдача всех домашних заданий, а также заданий практикума в течение семестра (20% итоговой оценки), полное владение теоретическим материалом, продемонстрированное на экзамене (55% итоговой оценки). Необходимым условием хорошей оценки на экзамене является уверенное знание основ курса, сдача всех заданий, хорошо выполненные контрольные работы.
Содержание курса:

1. Введение в программирование

1. 
   Устройство компьютера: схема, устройства ввода и вывода, внутренняя и внешняя память, центральный процессор.
   
2. 
   Оперативная память: ячейки, адреса ячеек, размер ячеек.
   
3. 
   Машинное представление данных: представление целых и вещественных чисел, точность представления целых и вещественных чисел, представление символьной информации.
   
4. 
   Машинная программа: смысл и формат команд, система команд.
   

2. Введение в язык программирования C++

1. 
   Язык C++: история, назначение, области применения, стандарт языка.
   
2. 
   Программы на языке С++: запись программ, имена, переменные и константы, стиль записи программ.
   
3. 
   Вывод на экран, ввод с клавиатуры.
   
4. 
   Практикум:
   
   1. 
      Среда программирования.
      
   2. 
      Компилирование и выполнение программ.
      
   3. 
      Программа «Hello World».
      

3. Вычисления на языке C++

1. 
   Арифметические и логические операции.
   
2. 
   Операция присваивания.
   
3. 
   Отношения.
   
4. 
   Условный оператор if-else.
   
5. 
   Битовые и адресные операции.
   
6. 
   Приоритеты и ассоциативность операций.
   
7. 
   Практикум:
   
   1. 
      Вычисления по формулам.
      
   2. 
      Программа вычисления корней квадратного уравнения.
      
   3. 
      Тестирование программ.
      

4. Итерационные вычисления на языке C++

1. 
   Операторы цикла: while и do-while.
   
2. 
   Составной оператор
   
3. 
   Операторы break, continue и return.
   
4. 
   Практикум:
   
   1. 
      Программа решения уравнений методом касательных.
      
   2. 
      Программа решения уравнений методом хорд.
      

5. Матричные и векторные вычисления на языке C++

1. 
   Массивы: определение и размещение в памяти, индексация элементов массива.
   
2. 
   Оператор цикла for
   
3. 
   Практикум:
   
   1. 
      Алгоритмы суммирования, поиска и сортировки.
      
   2. 
      Алгоритмы решения систем линейных уравнений.
      
   3. 
      Алгоритмы вычисления собственных значений.
      
   4. 
      Алгоритмы вычисления обратной матрицы.
      

6. Обзор операторов языка С++

1. 
   Оператор/операция присваивания: ++, += и т.д.
   
2. 
   Оператор-выражение vs. Cоставной оператор.
   
3. 
   Метки.
   
4. 
   Управляющие операторы goto и switch.
   
5. 
   [повт] Условный оператор if-else.
   
6. 
   [повт] Операторы цикла while, do-while и for.
   
7. 
   [повт] Операторы break, continue и return.
   
8. 
   Структурное программирование.
   

7. Функции в языке С++

1. 
   Объявление функции: имя функции, аргументы функции, тип результата.
   
2. 
   Вызов функции.
   
3. 
   Необязательные аргументы функции, значения по умолчанию.
   
4. 
   Определение функции: заголовок функции, тело функции, оператор return.
   
5. 
   Стандартные функции языка С++.
   
6. 
   Рекурсивные функции.
   
7. 
   Практикум:
   
   1. 
      Схема Горнера для вычисления значения полинома.
      
   2. 
      Алгоритм численного интегрирования методом прямоугольников.
      
   3. 
      Алгоритм численного интегрирования методом трапеций.
      
   4. 
      Рекурсивная функция sin(x).
      

8. Производные типы данных

1. 
   [повт] Массивы.
   
2. 
   Структуры; битовые поля.
   
3. 
   Объединения.
   
4. 
   Указатели: массивы и указатели, адресная арифметика, бестиповый указатель, нулевой указатель.
   
5. 
   Строки и литералы.
   
6. 
   Распределение памяти: автоматическое, статическое, динамическое.
   
7. 
   Ссылки: распределение памяти при передаче аргументов функции, правила передачи аргументов.
   
8. 
   Практикум:
   
   1. 
      Структуры данных для представления бинарных деревьев поиска.
      

9. Сложность алгоритмов.

1. 
   Оценка сложности алгоритмов в худшем случае и в среднем.
   
2. 
   Операции поиска, вставки и удаления в деревьях поиска.
   
3. 
   Сложность операции поиска в деревьях поиска.
   
4. 
   Построение дерева поиска.
   
5. 
   Сбалансированные деревья поиска; сложность операций вставки и удаления.
   
6. 
   AVL-деревья; сложность операций вставки и удаления.
   
7. 
   Практикум:
   
   1. 
      Алгоритм построения дерева поиска.
      
   2. 
      Алгоритм поиска в дереве поиска.
      
   3. 
      Алгоритм построения AVL-дерева.
      

10. Принципы объектно-ориентированного программирования

1. 
   Понятие объекта: имя объекта, данные и методы.
   
2. 
   Конструкторы и деструкторы.
   
3. 
   Принципы объектно-ориентированного программирования:
   
   1. 
      Инкапсуляция - совмещение / сокрытие в одном объекте данных и методов их обработки.
      
   2. 
      Наследование – создание новых объектов, автоматически приобретающих данные и методы определённых ранее объектов.
      
   3. 
      Полиморфизм – переопределение семантики операций в иерархии объектов.
      
4. 
   Средства поддержки инкапсуляции.
   
5. 
   Средства поддержки наследования.
   
6. 
   Средства поддержки полиморфизма.
   
7. 
   Практикум:
   
   1. 
      Объект для представления комплексных чисел.
      

11. Объектно-ориентированное программирование в языке C++

1. 
   Класс, тип и объект в языке C++.
   
2. 
   Контроль доступа к объекту; доступ по чтению и по записи.
   
3. 
   Оптимизация записи простых методов.
   
4. 
   Переопределение операций.
   
5. 
   Производные классы, наследование: виртуальные методы, преобразование базового и производного классов, внутреннее и защищенное наследование.
   
6. 
   Абстрактные классы.
   
7. 
   Инициализация объектов.
   
8. 
   Множественное наследование; виртуальное наследование.
   
9. 
   Практикум:
   
   1. 
      Система объектов для геометрических фигур.
      

12. Управление объектами в языке С++

1. 
   Операции new и delete.
   
2. 
   Преобразования типов: явные преобразования типов, стандартные преобразования типов, преобразования указателей и ссылок, преобразования типов, определенных в программе.
   
3. 
   Динамическое определение типов.
   
4. 
   Указатели на элементы класса.
   
5. 
   Практикум:
   
   1. 
      Вычисления на графах.
      

13. Ввод-вывод в языке С++

1. 
   Потоки; манипуляторы и форматирование ввода-вывода.
   
2. 
   Строковые потоки.
   
3. 
   Ввод-вывод файлов.
   
4. 
   Практикум:
   
   1. 
      Алгоритмы обработки текстовых файлов.
      

14. Шаблоны в языке С++

1. 
   Функции-шаблоны.
   
2. 
   Шаблоны классов; задание свойств класса.
   
3. 
   Практикум:
   
   1. 
      Программирование для баз данных.
      

15. Библиотеки классов в языке С++

1. 
   Многократное использование функций и классов.
   
2. 
   Принципы построения библиотеки классов.
   
3. 
   Библиотека классов Tools.h++
   
4. 
   Стандартная библиотека шаблонов STL: коллекции и алгоритмы, итераторы, моделирование концепций.
   
5. 
   Стандартная библиотека языка Си++.
   
6. 
   Классы исключительных ситуаций.
   
7. 
   Стандартная библиотека ввода-вывода потоков.
   
8. 
   Практикум:
   
   1. 
      Программирование веб-приложений.
      

Распределение часов курса по темам и видам работ:

№ п/п	Наименование тем и разделов	ВСЕГО (часов)	Аудиторные занятия
			в том числе
			Лекции	Практические занятия
1.	Введение в программирование	4	4
2.	Введение в язык программирования C++	6	2	4
Контрольная работа		2		2
3.	Вычисления на языке C++	12	6	6
4.	Итерационные вычисления на языке C++	12	6	6
Зачет
5.	Матричные и векторные вычисления на языке C++	6	2	4
6.	Обзор операторов языка С++	8	4	4
Контрольная работа		2		2
7.	Функции в языке С++	10	6	4
8.	Производные типы данных	10	6	4
Экзамен
9.	Сложность алгоритмов	6	2	4
10.	Принципы объектно-ориентированного программирования	8	4	4
Контрольная работа		2		2
11.	Объектно-ориентированное программирование в языке C++	10	6	4
12.	Управление объектами в языке С++	10	6	4
Зачет
13.	Ввод-вывод в языке С++	6	2	4
14.	Шаблоны в языке С++	10	6	4
Контрольная работа		2		2
15.	Библиотеки классов в языке С++	18	10	8
Экзамен
	ИТОГО:	144	72	72