15.10.2018. № 7. Составные типы данных, стек, очередь, списки

Развернуть

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

08.10.2018. Модули

Развернуть

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

01.10.2018. № 5. Алгоритмы поиска подстроки в строке

Развернуть

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

24.09.2018. № 4. Сортировки: квази-линейные, линейные

Развернуть

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

17.09.2018. № 3. Сложность алгоритмов, алгоритмы сортировки, рекурсивные алгоритмы

Развернуть

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

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

10.09.2018. № 2. Представление примитивных типов данных

Развернуть

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

Ссылки:

09.09.2018. № 2, приквел 2. Динамическая память, указатели на функции, символы и строки

Развернуть

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

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

08.09.2018. № 2, приквел 1. Базовые типы данных

Развернуть

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

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

03.09.2018. № 1. Языки программирования

Развернуть

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

Действия