Материалы 2019-2020 учебного года
Предлагаемый курс лекций предназначен для профильного направления (кафедра “Прикладная математика” СПбГПУ) и поэтому подразумевает знакомство большинства студентов с программированием, которое обычно изучается в школе. Задания ЕГЭ по информатике, например, содержат исходные коды на языках BASIC, Pascal, C, Python и на школьном алгоритмическом языке. Базовая подготовка позволяет не сосредотачиваться на обучении простым концепциям программирования, а преподавать углубленное (“продвинутое”) программирование на таком сложном, гибком и опасном языке как Си.
Тем не менее, преподавание в школах часто оставляет желать лучшего, знания быстро выветриваются из головы, а некоторые студенты приходят абсолютно неподготовленными (либо не знают, куда идут, либо знают, но очень хочется). Чтобы упростить жизнь людям, решившим изучать программирование с нуля, а также как-то подтянуть “средний уровень по больнице”, в курсе встречаются в небольших количествах достаточно простые и вроде бы очевидные вещи, на которые не все обращают внимание самостоятельно.
С чего начать:
Поляков, К. Язык программирования Си. Практический курс (конспект лекций для 7-11 классов) / URL: http://kpolyakov.spb.ru/school/c.htm.
Подбельский, В. Курс программирования на языке Си. / Вадим Подбельский, Сергей Фомин. — ДМК Пресс, 2015. — 384 с.
Прата, С. Язык программирования C. Лекции и упражнения, 6-е издание. / С. Прата. — Вильямс, 2015. — 928 с.
Другие (адекватные?) книги по Си в магазинах (в алфавитном порядке):
Гриффитс, Д. Изучаем программирование на C. / Дэвид Гриффитс, Дон Гриффитс. — Эксмо, 2013. — 624 с.
Дейтел, П. С для программистов с введением в С11. / Пол Дейтел, Харви Дейтел. — ДМК Пресс, 2014. — 544 с.
Дейтел, Х. Как программировать на C. / Харви Дейтел, Пол Дейтел. — М.: Бином-Пресс, 2009. — 910 с.
Керниган, Б. Язык программирования C, 2-е издание. / Брайан Керниган, Деннис Ритчи. — Вильямс, 2008. — 304 с.
Перри, Г. Программирование на С для начинающих, 3-е издание. / Г. Перри. — Эксмо, 2015. — 368 с.
Подбельский, В. Программирование на языке Си. / Вадим Подбельский, Сергей Фомин. — М.: Финансы и статистика, 2005. — 600 с.
Подбельский, В. Практикум по программированию на языке Си. / Вадим Подбельский. — М.: Финансы и статистика, 2004. — 576 с.
Харбисон, С. Язык C с примерами. / Сэмюэл П. Харбисон, Гай Л. Стил. — Бином, 2010. — 528 с.
Кроме того:
Стандарт ANSI X3.159-1989 “Programming Language C” (он же ISO/IEC 9899:1990).
Англоязычная Wikipedia.
Другие общедоступные источники информации.
Обратите внимание, Политех также требует от всех первокурсников с 23 сентября по 20 октября 2019 года пройти курс-тест по информатике, для ИПММ ссылка https://lms.spbstu.ru/enrol/index.php?id=1116
Приветственное занятие. Знакомство с институтом, направлениями, перспективами, курсом, правилами и требованиями преподавателя.
Глава 1. Введение в программирование.
§1.1. Алгоритмы и алгоритмические языки. Алгоритм как последовательность действий. Сложение, умножение, деление в столбик. Алгоритм вычисления квадратного корня. Синус. Способы записи алгоритмов. Алгоритмические языки и языки программирования. Исполнитель. Формальные модели: машина Тьюринга, машина Поста, нормальные алгоритмы Маркова, лямбда-исчисление.
См. также: ПиктоМир. Школьный алгоритмический язык.
§1.2. Модель ЭВМ и машинные коды. Концепция хранимой программы и архитектура фон Неймана. Упрощенная модель ЭВМ. Инструкции, машинные коды. Императивное программирование. Последовательное выполнение и управление потоком команд. Первое поколение языков программирования. Мнемонические команды и языки ассемблера.
См. также: Von Neumann architecture. Machine code.
§1.3. Языки программирования высокого уровня. Языки третьего поколения. Парадигмы программирования. Программа как набор последовательных команд, меняющих состояние. Структурное программирование. Условное выполнение и повторение команд. Подпрограммы. Программирование сверху вниз. Поздние поколения языков программирования.
См. также: Imperative programming. Programming paradigm. Structured programming. Control flow.
§1.4.* Язык Си: быстрый старт (PDF). Назначение языка Си, достоинства и недостатки. Минимальная программа, ее взаимодействие с ОС. Си как процедурный язык. Объявление переменных, диалог с пользователем, вычисление выражений. Арифметические операции и основные математические функции стандартной библиотеки. Ветвление потока управления, повторение действий. Пользовательские функции. Массивы данных. Строки.
§1.5. Метаязыки описания языков программирования. Форма Бэкуса-Наура и её расширение. Синтаксические диаграммы Вирта.
Глава 2*. Представление данных: основы
“People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird.” (D. Knuth)
Глава вынесена в отдельный онлайн курс, который представляет собой взгляд из-за кулис, показывающий как именно данные различных типов (целые и дробные числа, текстовая информация, изображения и другие) кодируются для последующего хранения и обработки в компьютере.
§2.1. Позиционные системы счисления. Число и запись числа. Различные способы записи целых чисел. Позиционные системы счисления, арифметические действия в них. Алгоритм перевода в произвольную систему счисления и обратно, схема Горнера. Двоичная и шестнадцатеричная система счисления. Запись дробных чисел в позиционных системах, схема Горнера для дробей, алгоритмы перевода туда и обратно.
§2.2. Хранение целых чисел. Биты и байты как единицы хранения информации. Неотрицательные числа, их хранение в памяти. Проблема порядка байтов, «endianness». Хранение целых чисел со знаком, возможные альтернативные представления – знаковый бит, смещение, дополнительный код.
§2.3. Хранение вещественных чисел. Точность представления. Вещественные числа с фиксированной точкой. Научная форма записи чисел, плавающая точка. Нормализованные числа и их хранение в памяти, стандарт IEEE-754. Особенности формата с плавающей точкой: представимые числа, арифметические операции, машинное «эпсилон». Денормализованные числа.
§2.4. Хранение нечисловых данных. Категории и атрибуты, перечисления, кодовые таблицы. Буква и изображение буквы. Кодовая таблица ASCII, ее национальные расширения (кодовые страницы). Unicode, UTF-8.
Глава 3. Язык программирования Си в деталях.
§3.1. Алфавит и словарь (+PDF). Символы. Идентификаторы. Зарезервированные слова.
§3.2. Целочисленные и вещественные типы и константы (+PDF). Знаковые и беззнаковые целые типы разного размера, диапазоны значений. Запись в других системах счисления. Модификаторы типа констант. Символьные константы. Вещественные типы разного значения, примерные диапазоны и обеспечиваемая точность представления. Способы записи вещественных констант.
§3.3. Выражения (+PDF). Операнды и операции. Приоритет и ассоциативность. Тип, значение и побочный эффект, неявное преобразование типов в выражении. Порядок вычислений. Операции отношения и логические операции.
§3.4. Побитовые операции и их использование. Операции применяемые к битовому представлению чисел. Операции AND, OR, XOR, NOT; таблицы истинности. Сдвиги SHR/SHL, SAR/SAL. Интерпретация операций, примеры использования. Понятие маски в битовых операциях. Битовые операции в языке Си.
См. также: Bitwise operation. Bit manipulation. Bit twiddling hacks.
§3.5. Команды. Команда вычисления выражения. Команды управления потоком выполнения программы (условное выполнение, циклы и др.). Составная команда.
§3.6. Структура текста программы. Программа как набор описаний. Описание констант, переменных, типов. Функции и прототипы функций. Область видимости и пространство имен глобальных описаний. Локальные области видимости.
§3.7. Препроцессор. Стадия предварительной обработки исходного кода программы. Основные стадии предобработки. Директивы препроцессора. Включение текста из внешних файлов. Определение макроподстановок и использующиеся в них специальные операции препроцессора. Условное включение частей исходного текста. Другие директивы.
§3.8. Указатели. Память и адреса. Определение и инициализация. Арифметика указателей. Имя массива как указатель. Альтернативный доступ к элементам массива. Важное отличие указателей от имен массивов. Массивы указателей и указатели на массивы. Указатели и многомерные массивы. Нетипизированные указатели.
§3.9. Применение указателей. Варианты использования указателей. Модификация переменных в функции. Передача массивов и других данных больших объемов в функции. Обобщенный шаблонный код без использования функций. Последовательная обработка элементов массивов и строк. Динамические массивы и структуры данных.
§3.10. Динамические массивы. Доступные области памяти, динамическая память, ее назначение. Функции стандартной библиотеки для работы с динамической памятью. Особенности использования функции realloc. Создание и использование одномерных динамических массивов. Схемы возможных реализаций многомерных динамических массивов: одномерная развертка, указатель на массивы и массив указателей. Плюсы и минусы каждой схемы, объявление соответствующих переменных, выделение и освобождение памяти.
(Контрольная работа)
§3.11. Основные ошибки при работе с указателями. Классификация ошибок при работе с динамической памятью, примеры. Использование неинициализированных указателей, выход за пределы выделенной памяти (“пропись”), висячие ссылки и утечки памяти. Способы предотвращения ошибок.
См. также: Buffer overflow. Dangling pointer. Memory leak.
(Разбор контрольной работы)
§3.12. Константность и указатели. Ключевое слово const в определениях объектов и указателей. Возможное расположение ключевого слова и различие смыслов соответствующих описаний.
§3.13. Производные типы и их комбинации. Базовые и производные типы в языке Си. Определение новых типов (углублённое повторение). Схема комбинирования производных типов. Указатели на функцию, их предназначение, определение и варианты использования в программе.
§3.14. Потоковый ввод/вывод. Поток данных между программой и устройством или файлом на диске. Потоки в языке Си, стандартные потоки ввода и вывода. Режимы открытия файлов. Перенаправление ввода/вывода в консоли. Функции стандартной библиотеки для работы с потоками, чтение и запись текстовых данных. Буферизованный ввод/вывод.
§3.15. Ошибки ввода/вывода. Общие принципы работы с различными ресурсами, возможность отказов. Обработка ошибок в стандартной библиотеке ввода/вывода. Способы уточнить причину ошибки, тонкости обработки конца файла. Примеры.
§3.16. Чтение и запись бинарных данных. Бинарный режим ввода/вывода. Функции чтения и записи блоков памяти. Отличие бинарного и текстового представления числовых значений. Функции произвольного доступа, изменение текущей позиции в файле.
§3.17. Перечисления. Назначение перечислений. Определение и использование.
(Контрольная работа)
§3.18. Структуры. Составной тип — структуры, их назначение. Определение и инициализация, обращение к отдельным элементам. Частичная инициализация. Расположение в памяти, операция sizeof. Битовые поля, их назначение, синтаксис. Варианты использования битовых полей.
§3.19. Функции с переменным числом аргументов. Секреты функции printf. Синтаксис определения функций с переменным числом аргументов. Проблемы реализации подобных функций: количество и тип параметров. Макросы стандартной библиотеки для работы с неизвестными аргументами. Пример функции. Автоматические преобразования типов. Возможные ошибки и их последствия.
§3.20. Функция main. Запуск программ из командной строки. Передача и прием дополнительных параметров. Возможные прототипы функции main, назначение аргументов и возвращаемого значения.
(Сессия)
Что не успеваем в этом семестре?
§3.xx. Объединения. Составной тип — объединения, их назначение. Определение и инициализация, обращение к отдельным элементам. Частичная инициализация. Расположение в памяти, операция sizeof. Варианты использования объединений.
§3.xx. Существование объектов во времени и в пространстве. Объявления и определения. Области видимости объявлений. Пространства имен. Время и место жизни объектов. Спецификаторы и модификаторы классов памяти.
§3.xx. Рекурсия. Общее понятие рекурсии. Прямая и косвенная рекурсия в математике, пример с факториалом и числами Фибоначчи. Поддержка в языках программирования, возможная реализация, стек вызовов. Достоинства и недостатки рекурсии. Особый вид — хвостовая рекурсия.
См. также: Recursion. Recursion in computer science. Tail call.