Раздел «Образование».FirstTerm:
Первый семестр Второй семестр Третий семестр Четвертый семестр


Первый семестр: Основы информатики. Алгоритмы и алгоритмические языки

Содержание:

I Понятие алгоритма

  1. Интуитивное понятие алгоритма. Свойства алгоритмов. Понятие об исполнителе алгоритма.
  2. Уточнение понятия алгоритма. Алгоритм как преобразование слов из заданного алфавита. Машина Тьюринга. Тезис Тьюринга и его обоснование Нормальные алгорифмы Маркова. Множество вычислимых функций и его свойства.
  3. Алгоритмическая сложность. Связь понятия алгоритма с понятием функции. Ассимптотическая сложность простейших алгоритмов.
  4. Характеристика алгоритмических языков и их исполнителей. Понятие трансляции.
  5. Понятие о формальных языках. Способы строгого описания формальных языков, понятие о метаязыках. Алфавит, синтаксис и семантика алгоритмического языка. Описание синтаксиса языка с помощью металингвистических формул и синтаксических диаграмм.

II Язык программирования

  1. Общие характеристики языков программирования. Алфавит, имена, служебные слова, стандартные имена, числа, текстовые константы, разделители.
  2. Структура программы на Паскале. Заголовок программы. Блок. Типы данных, их классификация. Переменные и константы. Скалярные типы данных и операции над ними, старшинство операций, стандартные функции. Выражения и правила их вычисления. Оператор присваивания. Перечисляемые и ограниченные типы данных.
  3. Простые и сложные операторы. Пустой, составной, условный операторы и оператор перехода. Метки. Оператор варианта.
  4. Файлы Стандартные процедуры и функции ввода-вывода. Операторы цикла. Программирование рекуррентных соотношений. Составные типы данных. Массивы.
  5. Описание процедуры и оператор процедуры. Формальные и фактические параметры. Способы передачи параметров. Локализация имен, разрешение коллизий. Функции, побочные эффекты.
  6. Итерации и рекурсии.
  7. Комбинированный тип. Оператор присоединения. Множества. Ссылочный тип данных. Динамические переменные.

III Алгоритмы и структуры данных

  1. Абстрактные структуры данных. Понятие интерфейса. Стек. Очередь. Деревья поиска: простЫе, АВЛ, красно-черные. Очередь с приоритетом и её различные реализации на основе а) неупорялоченного массива пар; б) двоичная куча в) дерево поиска.
  2. Оценки алгоритмической сложности.
  3. Классические алгоритмы и методы: жадные алгоритмы, динамическое программирование, переборные алгоритмы.

IV Этапы разработки программ

  1. Проектирование, прототипирование, разработка, отладка и тестирование.
  2. TDD и MDD

Attachment sort Action Size Date Who Comment
programm-1_semestr.doc manage 152.0 K 02 Jun 2008 - 22:33 ArtemVoroztsov