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. Сборка программы: компиляция и линковка.

Действия