Лицей 84 (личная):
Основы программирования
: Информация
Опубликован: 16.09.2005 | Уровень: для всех | Доступ: свободно | ВУЗ: Московский государственный университет имени М.В.Ломоносова
Курс предназначен для обучения основам программирования. Рассматриваются основные понятия программирования - алгоритма, исполнителя, алгоритмического языка, переменной, основные типы данных, управляющие конструкции алгоритмического языка и т.п. Излагаются общие приемы программирования, основанные на применении математики, такие, как вычисление функций на последовательностях с помощью применения теории индуктивных функций и схема построения цикла с помощью инварианта.
Рассматриваются общие принципы устройства и работы компьютера, типичные команды и регистры процессора, методы адресации, способы вызова функций и передачи параметров и т.п. Приводятся примеры записи программ как на виртуальном Ассемблере RTL, так и на Ассемблере процессора Intel 80386. Кратко рассмотрены аппаратные средства поддержки многозадачности.
Значительная часть курса посвящена основам языка Си. Помимо основ языка, в ней приведено много примеров реализации алгоритмов на Си, таких как вычисление корня функции, приведение матрицы к ступенчатому виду методом Гаусса, работа с файлами и текстами и т.п.
Последние лекции посвящены структурам данных и их реализациям. Рассматриваются структуры последовательного и прямого доступа, такие как стек, очередь, список, дерево, множество и нагруженное множество, а также их непрерывные и ссылочные реализации. Значительное место уделено реализациям множества с помощью бинарного поиска, на базе сбалансированных деревьев и с помощью хеш-функции.
Курс полезен студентам и преподавателям ВУЗов.
Цель: Обучение основам программирования.
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 138 минут | Общее понятие алгоритма. Управляющие конструкции алгоритмического языка. Понятие переменной
Рассматривается общее понятие алгоритма и дается краткий обзор существующих алгоритмических языков. Вводится неформальный алгоритмический язык - псевдокод, максимально приближенный к естественному языку. Рассматриваются основные конструкции алгоритмического языка - алгоритм, ветвление, цикл; приводятся простейшие примеры программ на псевдокоде. Определяется понятие переменной.
Оглавление | - |
Тест 118 минут | - | |
Лекция 233 минуты | Типы переменных. Целые и вещественные переменные, представление целых и вещественных чисел в компьютере
Определяется понятие типа переменной как множества значений, которые она может принимать, и набора операций, которые можно совершать со значениями. Рассматриваются наиболее важные базовые типы алгоритмического языка - целые и вещественные числа. Подчеркивается особенность представления целых чисел в компьютере как элементов кольца вычетов, рассматривается интерпретация элементов кольца вычетов как неотрицательных чисел или чисел со знаком. Приводится представление вещественных чисел в компьютере в плавающей форме, рассматриваются особенности арифметики плавающих чисел.
Оглавление | - |
Тест 218 минут | - | |
Лекция 321 минута | Символьные и логические переменные и выражения. Массивы и текстовые строки
Рассматриваются символьные переменные и способы кодирования символов. Вводится логический тип и логические выражения, подчеркивается отличие логических выражений от арифметических: сокращенное вычисление результата. Определяется конструкция массива. Рассматриваются возможные способы представления текстовых строк.
Оглавление | - |
Тест 318 минут | - | |
Лекция 442 минуты | Вычисление функций на последовательностях
Вычисление функции на последовательности элементов встречается как фрагмент в большинстве реальных программ. Рассматривается общая схема вычисления функций на последовательностях, основанная на понятии индуктивной функции и индуктивного расширения. Применение общей схемы иллюстрируется на примерах - вычисление суммы и максимума последовательности, схема Горнера вычисления значения многочлена и его производной и т.п.
Оглавление | - |
Тест 418 минут | - | |
Лекция 533 минуты | Построение цикла с помощью инварианта
Рассматривается схема построения цикла "пока" с помощью инварианта, т.е. утверждения, которое сохраняется при каждом выполнении тела цикла. Применение этой схемы дает возможность сознательно строить алгоритм и доказывать правильность его работы по тексту, не прибегая к тестированию. Применение схемы иллюстрируется на примерах: алгоритм Евклида вычисления наибольшего общего делителя, алгоритм быстрого возведения в степень, расширенный алгоритм Евклида, приближенное вычисление логарифма без использования разложения в ряд.
Оглавление | - |
Тест 518 минут | - | |
Лекция 641 минута | Устройство компьютера. Оперативная память, процессор, регистры процессора. Аппаратный стек
Рассматривается устройство компьютера, построенного по фон-Неймановской архитектуре. Приводятся основные составные части компьютера: процессор, оперативная память, шина, внешние устройства. Рассматриваются общие принципы построения и работы процессора, указываются важнейшие регистры процессора и алгоритм его работы. Дается классификация CISC и RISC-процессоров. Рассматривается аппаратный стек и его использование в командах вызова подпрограмм и для размещения локальных переменных.
Оглавление | - |
Тест 618 минут | - | |
Лекция 737 минут | Машинно-независимый Ассемблер RTL и Ассемблер Intel 80x86. Внешние устройства и прерывания. Виртуальная память и поддержка параллельных задач
Рассматривается способ записи программ на языке RTL (Register Transfer Language), представляющем собой Ассемблер, не зависящий от команд конкретного процессора. Приводятся примеры записи программ на RTL и на Ассемблере процессора Intel 80386. Кратко рассматриваются более сложные принципы работы компьютера: взаимодействие с внешними устройствами, асинхронные и синхронные прерывания, использование виртуальной памяти для поддержки параллельных задач, процессы, нити и их синхронизация.
Оглавление | - |
Тест 718 минут | - | |
Лекция 81 час 36 минут | Основы языка Си: структура Си-программы, базовые типы и конструирование новых типов, операции и выражения
Лекция посвящена введению в язык Си. Объясняются общие принципы построения Си-программы: разбиение проекта на h- и c-файлы, т.е. разделение интерфейса и реализации, использование препроцессора. Приводятся базовые типы языка Си, конструкции массива и указателя, позволяющие строить новые типы, а также модификаторы типов. Рассматриваются всевозможные операции и выражения языка Си.
Оглавление | - |
Тест 818 минут | - | |
Лекция 91 час 37 минут | Управляющие конструкции языка Си. Представление программ в виде функций. Работа с памятью. Структуры
Рассматриваются управляющие конструкции языка Си: ветвления "if-else" и "if-else if", циклы "while" и "for". Приводятся также конструкции, которых лучше избегать: "switch", "do-while", "goto". Рассматривается представление программы в виде набора функций, прототипы функций, методы передачи входных и выходных параметров. Перечисляются различные виды памяти: статическая, стековая, динамическая (куча) и способы работы с памятью в Си. Вводится составной тип данных "структура". Материал иллюстрируется многочисленными примерами программ: решение квадратного уравнения, вычисление квадратного корня, вычисление НОД двух чисел и расширенный алгоритм Евклида, печать N первых простых чисел, рекурсивный обход дерева и др.
Оглавление | - |
Тест 918 минут | - | |
Лекция 101 час 58 минут | Технология программирования на Си: представление матриц, работа с файлами и с текстами
Приводятся правильные и неправильные способы реализации матриц и многомерных массивов на языке Си. Работа с матрицами иллюстрируется на примере приведения матрицы к ступенчатому виду методом Гаусса. Рассматриваются методы работы с файлами, использующие функции ввода-вывода из стандартной библиотеки ANSI. Приводятся способы работы с символами и текстовыми строками с помощью функций стандартной библиотеки. Материал иллюстрируется примерами, включающими программу "wc" подсчета символов, слов и строк в файле и программу "Записная книжка", которая позволяет находить телефон человека по его имени, а также сохранять и модифицировать содержимое книжки.
Оглавление | - |
Тест 1018 минут | - | |
Лекция 111 час 16 минут | Структуры данных: общее понятие, реализация. Простейшие структуры данных: очередь, стек. Использование стека и обратная польская запись
Дается общее понятие структуры данных как исполнителя, который организует работу с данными: хранение, добавление и удаление, поиск и т.п. Рассматриваются реализации одних структур на базе других, в частности, реализации на базе массива. Приводятся наиболее важные из простейших структур данных: очередь и стек, а также их непрерывные реализации на базе массива. Даются многочисленные примеры использования стека в программировании. Рассматривается обратная польская запись формулы (знак операции после аргументов) и способ ее вычисления на стековой машине. В качестве примера использования обратной польской записи рассматривается графический язык PostScript. Материал иллюстрируется проектом "Cтековый калькулятор", реализованным на языке Си.
Оглавление | - |
Тест 1118 минут | - | |
Лекция 1258 минут | Ссылочные реализации структур данных. Списки и деревья. Реализации множества: с помощью бинарного поиска, на базе сбалансированных деревьев, хеширование
Рассматриваются ссылочные реализации структур данных, в которых элементы хранятся в произвольном порядке, при этом каждый элемент хранит ссылки на соседей. Ссылочные реализации позволяют избавиться от массовых операций при удалении или добавлении элементов в середине структуры. Приводятся типичные примеры структур, для которых применяются ссылочные реализации: одно- и двунаправленные списки, деревья. Рассматривается важнейшая структура данных: множество и нагруженное множество. Приводятся различные способы реализации множества: 1) непрерывная реализация с последовательным или с бинарным поиском; 2) ссылочная реализация множества на базе упорядоченного бинарного дерева, при этом используются сбалансированные AVL-деревья или красно-черные деревья; 3) реализация на базе хеш-функции и массива подмножеств.
Оглавление | - |
Тест 1218 минут | - | |
5 часов | - |
