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

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

---

FAQ

• Что? — Курс по программированию на С/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. Компилятор. Оптимизатор. Debug/Release сборка.
2. Немного о стандартах. Стандарт/Платформа+Компилятор/Undefined Behavour.
3. Структура программы, объявления, заголовочные файлы. Hello, world. Элементарный вывод. Комментарии, отступы, оформление кода.
4. Переменные (начало).

16 сентября
- Переменные. Понятие о строгой типизации. Основные целочисленные типы, unsigned, производные типы; size_t. Вещественные типы. Символ как целочисленный тип. Арифметика, приоритеты операций. Побитовые операции. Переполнение. Приведение типа.

NaN, INFINITY. Примеры переполнений. Sizeof. cfloat, climits, limits.

2. const и #define. Препроцессор.
3. Управляющие конструкции языка.
4. Логические выражения.
5. Блоки, область видимости.

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

23 сентября
- Статические массивы, инициализация, многомерные массивы.

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

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

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

//7 октября //

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

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

14 октября

1. Символы и строки. Различные представления символов, кодировки.
2. C-строки, функции для работы с ними.
3. Определения класса символа ().
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	II	FP	4
1. Корчажников Федор	+	+	?
2. Круглова Валентина	+	+	+	?
3. Сальников Дмитрий	+	+	+	?
4. Ширинкина Дарья	+	+	+	+
5. Ролдугин Пётр	+	?	?
6. Григорьева Ирина	+	+	?	?
7. Агеев Владимир	+	+	+
8. Гориславский Ростислав

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

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

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

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

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

Посещаемость

	9.09	16.9	23.9	30.9	7.10	14.10	21.10	28.10	11.11	18.11	25.11	02.12
1. Корчажников Федор	+	+	+	+	+	+	+	+	+	+	+
2. Круглова Валентина	+	+	+	+	+	+	+	+	+	+	+
3. Сальников Дмитрий	+	+	+	+	+	+	+	+	+	+	+
4. Ширинкина Дарья	+	+	+	+	+	+	+	+	+	+	+
5. Ролдугин Пётр	+	+	+	+	+	+	+/-	+	+	+	+
6. Григорьева Ирина	+	+	+	+	+	+	+	+	+	+	+
7. Агеев Владимир	+	+	+	+	+	+	+	+	+	+	+
8. Гориславский Ростислав	-	-	+	-	-	-	-	-	-	+	+

Литература (и другие источники)

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

++

1. C++11/14 compiler and library shootout Сводная таблица по поддержке новых возможностей различными компиляторами.
2. MSDN C++ Позволяет ответить на вопрос “А как же оно на самом деле работает” применительно к майкрософтовской реализации C++ (Visual C++). В целом, удобная онлайн-справка по языку и Visual Studio IDE. Некоторыми признается вообще лучшей документацией по языку.

---

1. за окончательный вариант стандарта ISO требует весьма круглую сумму денег, но последний черновик отличается от окончательно варианта в исключительно мелких деталях (если не ошибаюсь, двумя опечатками), поэтому простые смертные обычно довольствуются этим самым черновиком. Впрочем, существуют и другие пути получения финальной версии стандарта ↩

2. Ключевое слово здесь должно. Дело в том, что на данный момент поддержка распространенными компиляторами Стандарта является далеко неполной ↩