C.Ю.Соловьев

Программирование

для студентов третьего курса факультета математики ГУ-ВШЭ


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

Содержание курса

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

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

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

    9.  
    Вопросы?