Опубликован: 16.09.2005 | Уровень: для всех | Доступ: платный | ВУЗ: Московский государственный университет имени М.В.Ломоносова
Курс предназначен для обучения основам программирования. Рассматриваются основные понятия программирования - алгоритма, исполнителя, алгоритмического языка, переменной, основные типы данных, управляющие конструкции алгоритмического языка и т.п. Излагаются общие приемы программирования, основанные на применении математики, такие, как вычисление функций на последовательностях с помощью применения теории индуктивных функций и схема построения цикла с помощью инварианта.
Рассматриваются общие принципы устройства и работы компьютера, типичные команды и регистры процессора, методы адресации, способы вызова функций и передачи параметров и т.п. Приводятся примеры записи программ как на виртуальном Ассемблере RTL, так и на Ассемблере процессора Intel 80386. Кратко рассмотрены аппаратные средства поддержки многозадачности. Значительная часть курса посвящена основам языка Си. Помимо основ языка, в ней приведено много примеров реализации алгоритмов на Си, таких как вычисление корня функции, приведение матрицы к ступенчатому виду методом Гаусса, работа с файлами и текстами и т.п. Последние лекции посвящены структурам данных и их реализациям. Рассматриваются структуры последовательного и прямого доступа, такие как стек, очередь, список, дерево, множество и нагруженное множество, а также их непрерывные и ссылочные реализации. Значительное место уделено реализациям множества с помощью бинарного поиска, на базе сбалансированных деревьев и с помощью хеш-функции. Курс полезен студентам и преподавателям ВУЗов.
Цель: Обучение основам программирования.

План занятий

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

                          Здравствуйте!

                          Записался на ваш курс, но не понимаю как произвести оплату.

                          Надо ли писать заявление и, если да, то куда отправлять?

                          как я получу диплом о профессиональной переподготовке?

                          Денис Шестериков
                          Денис Шестериков
                          Россия
                          Сергей Мамойленко
                          Сергей Мамойленко
                          Россия, Московский государственный институт стали и сплавов (Технологический университет), 2000