1. Записи
2. Массивы.
3. Адресация в многомерных массивах: C-style, FORTRAN-style, Java-style.
4. Стеки, очереди и их применение в различных задачах.
5. Реализация стека с помощью динамического массива.
6. Связные списки: структура и свойства.
7. Операции над списками.
8. Двусвязные списки, кольцевые списки, двусвязные кольцевые списки.
9. Данные как «белый ящик» и как «черный ящик».
10. Отличия абстрактных типов данных от структур данных.
11. Очередь с приоритетом.

1. Программирование как борьба со сложностью.
2. Программа как один большой черный ящик.
3. Декомпозиция на модули.
4. Пример модульной структуры: скачивалка изображений.
5. На что указывает граф связей между модулями?
6. Модуль = Интерфейс + Реализация.
7. Устройство модулей в C: заголовочный файл, исходный файл, использование модуля.
8. Стандартная библиотека C как набор модулей.
9. Почему интерфейс важнее реализации?
10. Операционная система как интерфейс.
11. Признаки хорошего интерфейса.

1. Поиск подстроки в строке — метод грубой силы и идеи его ускорения.
2. Алгоритм Боуэра-Мура.
3. Алгоритм Рабина-Карпа.

1. Cортировка Шелла.
2. Быстрая сортировка. Процедура разделения массива.
3. Алгоритм выбора k-го элемента.
4. Стабильность сортировок.
5. Сортировка слиянием.
6. Пирамидальная сортировка.
7. Нижняя оценка скорости сортировок, основанных на сравнениях.
8. Линейные сортировки: подсчетом, поразрядная, карманная.

1. Сложность алгоритмов. Нотация O, Ω, Θ.
2. Задача сортировки.
3. Интерфейс функции сортировки в C.
4. Bogosort и bozosort.
5. Сортировка выбором.
6. «Пузырьковая» сортировка.
7. Сортировка вставками.
8. Принцип «Разделяй и властвуй». Примеры: задача о ханойских башнях, получение перестановок, алгоритм Карацубы (умножение длинных чисел).
9. Основная теорема о рекуррентных соотношениях.
10. Поиск в массиве, двоичный поиск.
11. Рекурсия. Удачные и неудачные примеры использования рекурсии.
12. Хвостовая рекурсия.

Сайт с визуализацией сортировок

1. Двоичная система счисления, перевод чисел, битовое представление.
2. Шестнадцатеричная система счисления.
3. Хранение знака: знак в старшем бите (наивный способ).
4. Арифметика по модулю и двоичный дополнительный код.
5. Переполнение.
6. Двоично-десятичный код, Packed BCD.
7. Строки, базовые способы их представления.
8. Действительные числа как рациональные дроби.
9. Представление с фиксированной точкой.
10. Фиксированная точка и двоично-десятичный код.
11. Числа с плавающей точкой. Binary32, binary64, битовое устройство числа, варианты хранимых чисел.
12. Возможные проблемы плавающей арифметики.
13. Пример проблем: сравнение двух "равных" чисел.
14. Пример проблем: вычисление числа π по двум формулам.
15. Иерархия структур и типов данных.

Ссылки:

• Лекция про базовые типы данных с курса "Основы программирования".
• Лекция про динамическую память, указатели на функции, символы и строки с курса "Основы программирования".
• Развернутая и познавательная лекция про тонкости Unicode с Tech Talks @ NSU.

Лекция от 15 марта 2018, прочитанная в рамках курса «Основы программирования»

Лекция о работе с динамической памятью, использовании указателей на функции, символах и их кодировках, о представлении строк в C.

Лекция от 1 марта 2018, прочитанная в рамках курса «Основы программирования»

Базовая информация о представлении целых и вещественных чисел, одномерных массивах, указателях.

1. Организационные и формальные вопросы.
2. Пользователь всегда прав!
3. Что такое язык программирования?
4. Краткая история развития языков программирования: машинные коды, ассемблер, языки высокого уровня.
5. Способы трансляции: компиляция и интерпретация.
6. Виртуальные машины.
7. Парадигмы программирования: императивная, функциональная, логическая.
8. Обзор языков программирования.
9. Язык C, его история.
10. Структура C-программы.
11. Сборка программы: компиляция и линковка.