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

Развернуть

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

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

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

Развернуть

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

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

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

Развернуть

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

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

11.09.2017. № 2. Сборка программы, представление примитивных типов данных

Развернуть

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

Ссылки:

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

Развернуть

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

19.12.2016. Все лекции 2016

Развернуть

Архив содержит все лекции ОПК 2016-го года и две лекции с прошлосеместрового ОП.

Действия