С++, 322 гр., спец. САПР/MM

Место и время проведения: вторник, вторая и третья пары, аудитория 2414.
Преподаватель: Шлемов Александр Юрьевич shlemovalex@gmail.com

• Что? — Курс по программированию на С/C++.
• А конкретнее? — в этом семестре: начнем с основ, буквально с синтаксиса, затем изучим программирование «до объектов», т.е. практически, «чистый C»; в следующем семестре: ООП, шаблоны, библиотеки (STL и, возможно, boost), элементы нового стандарта (умные указатели, замыкания, etc).
• А на чем писать будем? — Мы не будем касаться каких-то платформоспецифичных вопросов (типа WinAPI), поэтому можно использовать любой современный компилятор и любую современную среду. Я предполагаю использование MS Visual Studio под Windows и GCC под Unix.
• А еще что-нибудь будет? — Курс будет обогащен всевозможными смежными темами, относящимися к программированию вообще: базовые алгоритмы и структуры данных, сведения о компиляторах, операционной системе, etc.
• А продвинутые алгоритмы будут? А системное программирование? А многопоточность? А… — Очень жаль, но ничего этого включить не удастся. Впрочем, возможно организовать дополнительные пары, целиком посвященные интересующим вопросам.
• Я все это знаю, что мне делать? — приходите на пару. Потом подойдите ко мне. Возможно, придумаем интересное индивидуальное задание.
• Я вообще не знаю C++, знаю только PASCAL (BASIC, PHP, ничего не знаю) — Приходите, всему научим
• А зачем мне C++? Все давно пишут на C#, Java, R, MATLAB, etc — Во-первых, на C++ пишут до сих пор довольно много. А во-вторых, разобравшись с C++ намного легче работать с языками более высокого уровня, потому что начинаешь понимать, как все устроено. Кроме того, за последние несколько лет C++ обогатился новыми возможностями, что существенно расширило границы его применения.
• Кто читает? — Читаю я, Александр Шлемов, аспирант Статмода.
• Сколько пар? — Две пары в неделю (вторая и третья во вторник).
• За что ставится зачет? — В осеннем семестре формальных зачета два, по вычпрактикуму (практика, проверяется умение писать законченные программы) и по семинару (теория, проверяется знание языка, методов программирования и умение быстро разбираться в коде и алгоритмах). Для первого нужно будет написать (во время семестра, в комфортном режиме) и сдать (по почте или на занятии) несколько (порядка 6) программ, а для второго — успешно написать две контрольных работы. Также будет учитываться активность на занятиях (ответы, решенные задачи, etc)
• Что за программы? — Небольшие программы по темам курса. Можете посмотреть в вики условия прошлого года. Но в прошлом году курс был полугодовой (включал и C и основы C++), в этом году задачи могут быть немного другими.
• Что за контрольные работы? — Первая контрольная работа — на бумаге, в виде теста, вторая — решение практических задач в классе с ограниченным временем.
• Какой формат теста? — Тест состоит из нескольких примеров реального (или почти реального) кода; необходимо разобраться, что этот код делает (или должен был делать) и найти в нем ошибки. Рабочее название этого типа заданий «антипримеры». Задания иллюстрируют типичные ошибки и учат их избегать.
• Какой формат «задач с ограниченным временем» — Нужно будет за время занятия разобраться в выданной программе и исправить ошибки и/или реализовать алгоритм по выданному описанию.
• У меня еще остались вопросы — Приходите на пары, задавайте. Можете написать мне на почту.

• Руководство по созданию и отладке консольных приложений в MS Visual Studio 2010
• Пример использования стандартного случайного генератора. Пример проекта с несколькими файлами. Больше примеров, подробное описание модуля std::random. Еще неплохое описание.Нам нужен только пример, читать остальные ссылки имеет смысл только интересующимся.
• Проект с примером использования фреймворка googletest и Руководство по добавлению фреймворка в проект + сами файлы фреймворка + вводная статья из официальной документации. Для корректной работы фреймворка в MS Visual Studio 2012, добавьте первой строчкой в gtest.h следующее: '#define _VARIADIC_MAX 10'

9 сентября

1. Приветствие. Знакомство. Система приема задач, план семестра. Проверка знаний слушателей. Возникновение С/С++, эволюция, статус на данный момент. Где и как используется, положение относительно других языков.
2. Компилятор. Оптимизатор. Debug/Release сборка.
3. Немного о стандартах. Стандарт/Платформа+Компилятор/Undefined Behavour.
4. Структура программы, объявления, заголовочные файлы. Hello, world. Элементарный вывод. Комментарии, отступы, оформление кода.
5. Переменные (начало).

16 сентября

1. Переменные. Понятие о строгой типизации. Основные целочисленные типы, unsigned, производные типы; size_t. Вещественные типы. Символ как целочисленный тип. Арифметика, приоритеты операций. Побитовые операции. Переполнение. Приведение типа. NaN, INFINITY. Примеры переполнений. Sizeof. cfloat, climits, limits.
2. <cmath>
3. const и #define. Препроцессор.
4. Управляющие конструкции языка.
5. Логические выражения.
6. Блоки, область видимости.

Примеры
Пример с различными арифметическими действиями
Пример с limits, NaN и переполнениями
Пример с вычислением экспоненты
Возведение в степень
auto, decltype() and initializer_lists

23 сентября

1. Статические массивы, инициализация, многомерные массивы.
2. Указатели, типы указателей, арифметика с указателями.
3. Связь указателей и массивов.
4. Нулевой указатель (nullptr).
5. Динамическое выделение памяти, new, delete.
6. Выделение памяти для массивов.
7. typedef, динамические многомерные массивы.
8. const *, void *, приведение типов для указателей.
9. Ссылочный тип и создание псевдонимов.

Примеры
auto, decltype() and initializer_lists
Тернарный оператор и вычисления по короткой схеме
Приоритеты операций
Массивы и указатели
Указатели и ссылки
Что напечатает программа?

30 сентября

1. Функции, вызов, передача параметров и возврат.
2. Передача параметров по значению, по ссылке, по указателю.
3. Const& Const* в параметрах.
4. Статическая перегрузка функций.
5. Понятие о куче и стеке, почему нельзя возвращать ссылку на локальный объект.
6. Понятие о рекурсии.
7. Моделирование случайных величин. Метод Монте-Карло для нахождения площадей фигур.
8. Самостоятельная работа в компьютерных классах. Темы: массивы, выделение памяти, динамический массив с поблоковым отведением памяти.

7 октября

1. Значения по умолчанию.
2. Указатель на функцию.
3. Unit-tests (модульное тестирование). gtest.
4. Понятие о компиляции (compilation) и компоновке (linking).
5. Заголовочные файлы (headers).
6. Самостоятельная работа в компьютерных классах Темы: сортировка, юнит-тесты, заголовочные файлы

Примеры
Использование указателя на функцию. Пример показывает разные способы определения и использования указателя на функцию. Все они эквивалентны. Функция === указатель на функцию.
Еще пример (с использованием auto и разрешением конфликта имен)

14 октября

1. Символы и строки. Различные представления символов, кодировки.
2. C-строки, функции для работы с ними.
3. Определения класса символа (<cctype>).
4. Массивы строк.

21 октября

1. Перевод чисел в строки и наоборот.
2. Структуры.
3. Вложенные структуры, инициализация структур.
4. Передача структур по ссылке/указателю, динамическое создание структур.
5. Динамические структуры данных (списки и так далее).

Далее идут минорные темы, «для общего развития»

28 октября

1. Массивы структур.
2. Битовые поля.
3. Объединения (union).
4. Перечисления (enum, enum class).
5. Самостоятельная работа

11 ноября

1. const/constexpr
2. inline
3. register
4. Самостоятельная работа

18 ноября

1. Абстрактные словари (Map/Set/MultiMap)
2. Словарь на массиве, бинарный поиск
3. Бинарное дерево поиска
4. Префиксное дерево (Trie)
5. Самостоятельная работа (бинпоиск, динамический массив как структура с методами)

25 ноября (анонс)

1. Хеширование, хеш-таблица, хеш-кольцо
2. Дискуссия о разных подходах к реализации словаря
3. Индексирование, отложенное удаление (пометка на удаление)
4. Антипримеры, подготовка к контрольным работам
5. Самостоятельная работа

Примеры
Разобранные антипримеры. Вариант теста от 30 октября позапрошлого года.

2 декабря

1. Контрольная работа с антипримерами
2. Подготовка к зачету (практическая часть)
3. По заявкам слушателей: рассказ о разных задачах и технологиях программирования
4. Самостоятельная работа

9 декабря

1. Практическая часть зачета Код для самостоятельной работы.

Номер Вашего варианта = Ваш номер в таблице выше. Если у Вас нет задания, Вы нашли ошибку или формулировка не до конца ясна, просьба отправить мне запрос по почте. Обозначения: плюсик — задача зачтена, вопрос — решение отправлено на доработку (т.е. я жду исправлений).

Задание I С использованием циклов и условий нарисовать фигурку как в приложенном файле. Фигурка должна быть параметризована одной или двумя константами-параметрами, имеющими смысл размеров. Варианты к заданию I.

Задание II Аналитически и с помощью метода Монте-Карло найдите площадь фигуры, ограниченной линиями. Программа должна уже быть написана в процедурном стиле, т.е. с использованием функций. Число испытаний М-К возьмите 10, 100, 1000 и так далее (сделайте верхнюю границу задаваемой). Программа должна выводить табличку со следующими столбцами: число испытаний, полученная оценка, разность оценки и истинного значения (ошибка), ошибка, умноженная на корень из числа испытаний. Варианты к заданию II.

Задание FP Реализовать функцию, принимающую на вход массив(ы) вещественных данных и указатель на функцию, и применяющую к ним функцию определенным образом. Варианты. Для функции необходимо подобрать информативные примеры и оформить их в виде тестов. Также тесты должны покрывать крайние случаи.

Задание 4 Задание на структуры. Варианты заданий. Задание описано по ссылке, кратко суть. Написать программу «Записная книжка». Программа должна позволять вводить данные, искать и удалять. Варианты отличаются видами поиска и форматом хранения данных.

1. Г. Шилдт. Полный справочник по C++ Довольно классическая книжка, сильно ее рекомендую. Мой стиль и порядок изложения в целом соответствует ей. Последнее издание — четвертое, есть и по-русски, и по-английски. Книга очень известна, хорошо доступна. Однако книга далеко не новая, из-за чего некоторые вещи выглядят устаревшими.
2. C++ Для чайников Несмотря на провокационное название, довольно приличная книга. Хорошее введение для начинающих с правильно поставленными акцентами. Есть русская и английская версия, при этом русский перевод очень приличный. Особенно приятно, что книга новая (точнее, новое переиздание) и она учитывает новые стандарты языка. Однако многие подробности в ней опущены, не следует рассматривать ее как руководство.
3. The C++ Programming Language (4th Edition) Новое издание легендарной книги от создателя языка. Очень достойный и исчерпывающий источник, но для начинающих, пожалуй, тяжеловата.
4. http://cplusplus.com/ Всякая инфа по языку и документация по использованию встроенной библиотеки с примерами. Коротко и удобно.
5. http://en.cppreference.com/w/ Аналогично предыдущему ресурсу.
6. C++11 Standard latest draft Последний черновой вариант¹⁾ актуального стандарта C++. Чтение не очень захватывающее, документ пропитан духом формализма. Но позволяет точно ответить на вопрос «А как это должно быть на самом деле?» ²⁾
7. C++14 Standard latest draft Последний черновой вариант новейшего (будущего) стандарта C++
8. C++11/14 compiler and library shootout Сводная таблица по поддержке новых возможностей различными компиляторами.
9. MSDN C++ Позволяет ответить на вопрос «А как же оно на самом деле работает» применительно к майкрософтовской реализации C++ (Visual C++). В целом, удобная онлайн-справка по языку и Visual Studio IDE. Некоторыми признается вообще лучшей документацией по языку.