Инспектор
Вы можете этот курс.
Основы программирования: Информация
Автор: Владимир Борисенко | Московский государственный университет имени М.В.Ломоносова
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 205 студентам
Уровень:
Для всех
Длительность:
15:06:00
Студентов:
15630
Выпускников:
1105
Качество курса:
4.26 | 4.03
Курс предназначен для обучения основам программирования. Рассматриваются основные понятия программирования - алгоритма, исполнителя, алгоритмического языка, переменной, основные типы данных, управляющие конструкции алгоритмического языка и т.п. Излагаются общие приемы программирования, основанные на применении математики, такие, как вычисление функций на последовательностях с помощью применения теории индуктивных функций и схема построения цикла с помощью инварианта.
Рассматриваются общие принципы устройства и работы компьютера, типичные команды и регистры процессора, методы адресации, способы вызова функций и передачи параметров и т.п. Приводятся примеры записи программ как на виртуальном Ассемблере RTL, так и на Ассемблере процессора Intel 80386. Кратко рассмотрены аппаратные средства поддержки многозадачности.
Значительная часть курса посвящена основам языка Си. Помимо основ языка, в ней приведено много примеров реализации алгоритмов на Си, таких как вычисление корня функции, приведение матрицы к ступенчатому виду методом Гаусса, работа с файлами и текстами и т.п.
Последние лекции посвящены структурам данных и их реализациям. Рассматриваются структуры последовательного и прямого доступа, такие как стек, очередь, список, дерево, множество и нагруженное множество, а также их непрерывные и ссылочные реализации. Значительное место уделено реализациям множества с помощью бинарного поиска, на базе сбалансированных деревьев и с помощью хеш-функции.
Курс полезен студентам и преподавателям ВУЗов.
Темы: Программирование
Специальности: Программист
ISBN: 978-5-9556-0039-0
Теги: 80x86, AVL, DST, endianness, fread, gcd, java, алгоритмы, библиотеки, бинарный поиск, вычисления, компиляторы, обратная польская запись, операционные системы, поиск, потоки, программирование, процессоры, ссылочная реализация, стековый калькулятор, структуры данных, указатели, форматы, элементы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 1
38 минут
Общее понятие алгоритма. Управляющие конструкции алгоритмического языка. Понятие переменной
Рассматривается общее понятие алгоритма и дается краткий обзор существующих алгоритмических языков. Вводится неформальный алгоритмический язык - псевдокод, максимально приближенный к естественному языку. Рассматриваются основные конструкции алгоритмического языка - алгоритм, ветвление, цикл; приводятся простейшие примеры программ на псевдокоде. Определяется понятие переменной.
Оглавление
-
Лекция 2
33 минуты
Типы переменных. Целые и вещественные переменные, представление целых и вещественных чисел в компьютере
Определяется понятие типа переменной как множества значений, которые она может принимать, и набора операций, которые можно совершать со значениями. Рассматриваются наиболее важные базовые типы алгоритмического языка - целые и вещественные числа. Подчеркивается особенность представления целых чисел в компьютере как элементов кольца вычетов, рассматривается интерпретация элементов кольца вычетов как неотрицательных чисел или чисел со знаком. Приводится представление вещественных чисел в компьютере в плавающей форме, рассматриваются особенности арифметики плавающих чисел.
Оглавление
-
Лекция 3
21 минута
Символьные и логические переменные и выражения. Массивы и текстовые строки
Рассматриваются символьные переменные и способы кодирования символов. Вводится логический тип и логические выражения, подчеркивается отличие логических выражений от арифметических: сокращенное вычисление результата. Определяется конструкция массива. Рассматриваются возможные способы представления текстовых строк.
Оглавление
-
Лекция 4
42 минуты
Вычисление функций на последовательностях
Вычисление функции на последовательности элементов встречается как фрагмент в большинстве реальных программ. Рассматривается общая схема вычисления функций на последовательностях, основанная на понятии индуктивной функции и индуктивного расширения. Применение общей схемы иллюстрируется на примерах - вычисление суммы и максимума последовательности, схема Горнера вычисления значения многочлена и его производной и т.п.
Оглавление
-
Лекция 5
33 минуты
Построение цикла с помощью инварианта
Рассматривается схема построения цикла "пока" с помощью инварианта, т.е. утверждения, которое сохраняется при каждом выполнении тела цикла. Применение этой схемы дает возможность сознательно строить алгоритм и доказывать правильность его работы по тексту, не прибегая к тестированию. Применение схемы иллюстрируется на примерах: алгоритм Евклида вычисления наибольшего общего делителя, алгоритм быстрого возведения в степень, расширенный алгоритм Евклида, приближенное вычисление логарифма без использования разложения в ряд.
Оглавление
-
Лекция 6
41 минута
Устройство компьютера. Оперативная память, процессор, регистры процессора. Аппаратный стек
Рассматривается устройство компьютера, построенного по фон-Неймановской архитектуре. Приводятся основные составные части компьютера: процессор, оперативная память, шина, внешние устройства. Рассматриваются общие принципы построения и работы процессора, указываются важнейшие регистры процессора и алгоритм его работы. Дается классификация CISC и RISC-процессоров. Рассматривается аппаратный стек и его использование в командах вызова подпрограмм и для размещения локальных переменных.
Оглавление
-
Лекция 7
37 минут
Машинно-независимый Ассемблер RTL и Ассемблер Intel 80x86. Внешние устройства и прерывания. Виртуальная память и поддержка параллельных задач
Рассматривается способ записи программ на языке RTL (Register Transfer Language), представляющем собой Ассемблер, не зависящий от команд конкретного процессора. Приводятся примеры записи программ на RTL и на Ассемблере процессора Intel 80386. Кратко рассматриваются более сложные принципы работы компьютера: взаимодействие с внешними устройствами, асинхронные и синхронные прерывания, использование виртуальной памяти для поддержки параллельных задач, процессы, нити и их синхронизация.
Оглавление
-
Лекция 8
1 час 36 минут
Основы языка Си: структура Си-программы, базовые типы и конструирование новых типов, операции и выражения
Лекция посвящена введению в язык Си. Объясняются общие принципы построения Си-программы: разбиение проекта на h- и c-файлы, т.е. разделение интерфейса и реализации, использование препроцессора. Приводятся базовые типы языка Си, конструкции массива и указателя, позволяющие строить новые типы, а также модификаторы типов. Рассматриваются всевозможные операции и выражения языка Си.
Оглавление
-
Лекция 9
1 час 37 минут
Управляющие конструкции языка Си. Представление программ в виде функций. Работа с памятью. Структуры
Рассматриваются управляющие конструкции языка Си: ветвления "if-else" и "if-else if", циклы "while" и "for". Приводятся также конструкции, которых лучше избегать: "switch", "do-while", "goto". Рассматривается представление программы в виде набора функций, прототипы функций, методы передачи входных и выходных параметров. Перечисляются различные виды памяти: статическая, стековая, динамическая (куча) и способы работы с памятью в Си. Вводится составной тип данных "структура". Материал иллюстрируется многочисленными примерами программ: решение квадратного уравнения, вычисление квадратного корня, вычисление НОД двух чисел и расширенный алгоритм Евклида, печать N первых простых чисел, рекурсивный обход дерева и др.
Оглавление
-
Лекция 10
1 час 58 минут
Технология программирования на Си: представление матриц, работа с файлами и с текстами
Приводятся правильные и неправильные способы реализации матриц и многомерных массивов на языке Си. Работа с матрицами иллюстрируется на примере приведения матрицы к ступенчатому виду методом Гаусса. Рассматриваются методы работы с файлами, использующие функции ввода-вывода из стандартной библиотеки ANSI. Приводятся способы работы с символами и текстовыми строками с помощью функций стандартной библиотеки. Материал иллюстрируется примерами, включающими программу "wc" подсчета символов, слов и строк в файле и программу "Записная книжка", которая позволяет находить телефон человека по его имени, а также сохранять и модифицировать содержимое книжки.
Оглавление
-
Лекция 11
1 час 16 минут
Структуры данных: общее понятие, реализация. Простейшие структуры данных: очередь, стек. Использование стека и обратная польская запись
Дается общее понятие структуры данных как исполнителя, который организует работу с данными: хранение, добавление и удаление, поиск и т.п. Рассматриваются реализации одних структур на базе других, в частности, реализации на базе массива. Приводятся наиболее важные из простейших структур данных: очередь и стек, а также их непрерывные реализации на базе массива. Даются многочисленные примеры использования стека в программировании. Рассматривается обратная польская запись формулы (знак операции после аргументов) и способ ее вычисления на стековой машине. В качестве примера использования обратной польской записи рассматривается графический язык PostScript. Материал иллюстрируется проектом "Cтековый калькулятор", реализованным на языке Си.
Оглавление
-
Лекция 12
58 минут
Ссылочные реализации структур данных. Списки и деревья. Реализации множества: с помощью бинарного поиска, на базе сбалансированных деревьев, хеширование
Рассматриваются ссылочные реализации структур данных, в которых элементы хранятся в произвольном порядке, при этом каждый элемент хранит ссылки на соседей. Ссылочные реализации позволяют избавиться от массовых операций при удалении или добавлении элементов в середине структуры. Приводятся типичные примеры структур, для которых применяются ссылочные реализации: одно- и двунаправленные списки, деревья. Рассматривается важнейшая структура данных: множество и нагруженное множество. Приводятся различные способы реализации множества: 1) непрерывная реализация с последовательным или с бинарным поиском; 2) ссылочная реализация множества на базе упорядоченного бинарного дерева, при этом используются сбалансированные AVL-деревья или красно-черные деревья; 3) реализация на базе хеш-функции и массива подмножеств.
Оглавление
-
