Основы программирования

Основы программирования

Общее понятие алгоритма
Алгоритмические языки
Управляющие конструкции алгоритмического языка
Понятие переменной

Основы программирования

Типы переменных
Целочисленные переменные
Кольцо вычетов по модулю m



Интерпретация положительных и отрицательных чисел
Вещественные переменные
Машинный эпсилон
Запись вещественных констант

Основы программирования

Символьные переменные
Логические переменные и выражения

Массивы
Текстовые строки

Основы программирования

Значения "минус" и "плюс бесконечность"
Схема Горнера
Арифметический цикл
Индуктивные функции на последовательностях и индуктивные расширения

Основы программирования

Общая схема
Алгоритм Евклида вычисления наибольшего общего делителя
Быстрое возведение в степень
Вычисление логарифма без использования разложения в ряд

Расширенный алгоритм Евклида
Нахождение корня функции методом деления отрезка пополам

Основы программирования

Устройство компьютера
Оперативная память
Процессор
CISC и RISC-процессоры
Алгоритм работы компьютера

Аппаратный стек
Команды вызова подпрограммы call и возврата return
Аппаратный стек и локальные переменные подпрограммы

Основы программирования

RTL: машинно-независимый Ассемблер
Примеры программ на RTL и Ассемблере Intel 80x86
Вычисление наибольшего общего делителя
Суммирование массива

Внешние устройства и аппаратные прерывания
Виртуальная память и поддержка параллельных задач
Страничная организация памяти
Переключение между процессами и нитями

Основы программирования

Основы языка Си
Структура Си-программы
Функции
Программа "Hello, World!"

Типы переменных
Базовые типы
Целочисленные типы
Тип int
Тип char
Типы short и long
Модификатор unsigned
Вещественные типы
Логический тип
Оператор sizeof

Тип void
Конструирование новых типов
Массивы
Указатели
Сложные описания
Строки
Модификатор const
Модификатор volatile
Оператор typedef
Выражения

Оператор присваивания
Арифметические операции
Операции увеличения и уменьшения
Операции "увеличить на", "домножить на" и т.п.
Логические операции
Операции сравнения
Побитовые логические операции

Операции сдвига
Арифметика указателей
Связь между указателями и массивами
Операция приведения типа

Основы программирования

Управляющие конструкции
Фигурные скобки
Оператор if
Выбор из нескольких возможностей: if...else if...
Пример: решение квадратного уравнения

Цикл while
Пример: вычисление квадратного корня методом деления отрезка пополам
Выход из цикла break, переход на конец цикла continue
Оператор перехода на метку goto
Цикл for
Операция "запятая" и цикл for
Конструкции, которые лучше не использовать
Цикл do...while
Оператор switch (вычисляемый goto)

Прототипы функций
Пример: вычисление наибольшего общего делителя
Передача параметров функциям
Пример: расширенный алгоритм Евклида
Работа с памятью
Статическая память
Стековая, или локальная, память
Динамическая память, или куча

Пример: печать n первых простых чисел
Операторы new и delete языка C++
Структуры
Структуры и указатели
Пример: рекурсивный обход дерева
Структуры и оператор определения типа typedef

Основы программирования

Представление матриц и многомерных массивов

Пример: приведение матрицы к ступенчатому виду методом Гаусса
Работа с файлами
Открытие файла: функция fopen
Константа NULL
Диагностика ошибок: функция perror

Функции бинарного чтения и записи fread и fwrite
Закрытие файла: функция fclose
Пример: подсчет числа символов и строк в текстовом файле
Форматный ввод-вывод: функции fscanf и fprintf
Понятие потока ввода или вывода
Функции scanf и printf ввода и вывода в стандартные потоки

Функции текстового преобразования sscanf и sprintf
Другие полезные функции ввода-вывода
Работа с текстами
Определение типов символов
Работа с текстовыми строками
Копирование строк
Работа с произвольными массивами байтов

Сравнение строк
Поиск
Пример: программа "Записная книжка"

Аргументы командной строки
Разработка больших проектов

Основы программирования

Структуры данных
Общее понятие структуры данных
Массив как базовая структура
Реализация одних структур на базе других
Простейшие структуры данных. Стек. Очередь
Очередь
Реализация очереди на базе массива

Стек
Использование стека в программировании
Реализация стека на базе массива
Реализация стека на языке Си
Использование функции assert для проверки утверждений и ситуация отказ
Стековый калькулятор и обратная польская запись формулы

Реализация стекового калькулятора на Си
Язык PostScript

Основы программирования

Ссылочные реализации структур данных
Массовые операции
Список
Ссылочная реализация списка

Деревья и графы
Множество
Реализации множества: последовательный и бинарный поиск, хеширование
Бинарный поиск
Реализации множества на базе деревьев
AVL-деревья

Красно-черные деревья
Хеширование
Циклы для каждого и итераторы