Geum.ru

Программа дисциплины «Программирование»

Вид материалаПрограмма дисциплины

Содержание


Тема 2. Основы программирования на языке высокого уровня (4 ч.)
Тема 3. Тестирование и отладка программ (4 ч.)
Тема 4. Методы разработки алгоритмов, рекурсия и итерация (2 ч.)
Тема 5. Ввод/вывод и работа с файлами (2 ч.)
Тема 6. Работа с массивами, строками и записями (4 ч.)
Тема 7. Рекурсивные типы данных и динамическое распределение памяти (16 ч.)
Тема 8. Сортировка и поиск (12 ч.)
Тема 9. Алгоритмы на графах (4 ч.)
Методические рекомендации (материалы) преподавателю
Рекомендации по использованию информационных технологий
Тематический расчет часов
Наименование разделов и тем (с разбивкой по модулям)
Всего за модуль
Всего за модуль
Всего за модуль
Всего за модуль
Подобный материал:
1   2   3   4   5   6   7
Тематика заданий по различным формам текущего контроля:

Тематика контрольных работ:
  1. Теоретические основы программирования.
  2. Оценка сложности и способы записи алгоритмов.
  3. Основные алгоритмы и структуры данных.

Перечень примерных заданий представлен в приложении.

Тематика домашних заданий:
  1. Основы программирования на языке Pascal: массивы, строки, записи, рекурсия и итерация.
  2. Рекурсивные типы данных и динамическое распределение памяти.
  3. Сортировка и поиск.

Перечень примерных заданий представлен в приложении.

Перечень вопросов для самоконтроля студентов:

Перечень вопросов для самоконтроля студентов представлен в приложении.

Тематика практических занятий:

Примерный перечень заданий, выполняемых на практических занятиях приведен в приложении.

План практических занятий

Тема 1. Решение задач с помощью компьютера (2 ч.)

Основные этапы компьютерного решения задач. Постановка задачи и спецификация программы, способы записи алгоритма. Программа на языке высокого уровня. Понятия тестирования и отладки. Критерии качества программы. Диалоговые программы, дружественность интерфейса. Стиль программирования.

Тема 2. Основы программирования на языке высокого уровня (4 ч.)

Лексика языка. Описание синтаксиса языка. Стандартные типы данных. Операции и стандартные функции. Операторы и основные управляющие структуры: итерация, ветвление, повторение. Нисходящее программирование и пошаговая детализация и использование процедур и функции: построение, описание данных, глобальные и локальные переменные, способы передачи параметров. Блочная структура. Понятие типа данных. Классификация языков по типизации. Классификация типов данных. Идентичность типов. Идентичность типов в языке Pascal. Числовые типы. Тип Boolean. Тип Char и тип String. Типы данных, определяемые пользователем: перечисления, диапазоны, множества, массивы, записи, файлы. Типизированные константы. Реализация процедур и функций.

Тема 3. Тестирование и отладка программ (4 ч.)

Принципы тестирования. Полнота тестирования. Критерии черного ящика. Критерии белого ящика. МГТ. Ошибкоопасные ситуации при работе с файлами. Ошибкоопасные ситуации при обращении к данным. Ошибкоопасные ситуации при вычислениях. Ошибкоопасные ситуации при передаче управления и вызовах подпрограмм. Безмашинное тестирование. Оценка количества ошибок в программе. Мера доверия к миллсовой модели оценки количества ошибок в программе. Оценка количества необходимых тестов.

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

Тема 4. Методы разработки алгоритмов, рекурсия и итерация (2 ч.)

Разработка рекурсивных процедур и функций. Вычисление факториала. Последовательность чисел Фибоначчи. Бинарный поиск и решение уравнений методом деления отрезка пополам. Использование процедурных типов.

Тема 5. Ввод/вывод и работа с файлами (2 ч.)

Ввод данных с клавиатуры. Вывод данных на экран.

Файлы. Виды файлов. Методы доступа.

Текстовые файлы. Файлы записей.

Триада для работы с файлом. Синхронизация. Буферизация. Блокирование. Двоичные файлы в Турбо-Паскале. Потоковые файлы в Турбо-Паскале.

Тема 6. Работа с массивами, строками и записями (4 ч.)

Описание и использование массивов. Операции над элементами массивов и над массивами. Тип String и операции над строками. Функции для работы со строками. Реализация машины Тьюринга и нормальных алгорифмов Маркова.

Тема 7. Рекурсивные типы данных и динамическое распределение памяти (16 ч.)

Динамические структуры данных. Списки: основные виды, способы организации, создание списков и операции над списками. Линейные списки. Нелинейные структуры данных, их классификация. Понятие графов и деревьев. Ориентированные графы. Упорядочение данных и бинарные деревья, их представление в памяти компьютера и применение. Реализация интерпретатора выражений с использованием деревьев. Графы и способы их представления: матричное представление, представление списками.

Тема 8. Сортировка и поиск (12 ч.)

Запись, ключ и информационная часть. Ключи простые и составные, лексикографический порядок; ключи первичные и вторичные; хранимые и вычислимые. Хранение ключей отдельно от информационной части.

Сортировка внутренняя и внешняя, записей и ключей, массивов и списков, линейная и нелинейная, простая и комбинированная, оптимальная по памяти и по времени. Самоупорядочивающиеся списки.

Методы внутренней сортировки: вставки (простые и бинарные), выбор, обмен (стандартный, пузырек, шейкер, просеивание), подсчет, распределительная сортировка. Сортировка Шелла. Сортировка Хоара (варианты Вирта и Кнута).

Внешняя сортировка. Предварительное упорядочивание блоков внутренней сортировкой. Сбалансированное слияние. Трехленточное слияние. Четырехленточное слияние. P-путевое слияние. Многофазная сортировка. Распределение начальных серий по N лентам (Фиббоначиева сортировка). Естественное слияние.

Сравнение сложности алгоритмов.

Методы поиска: последовательный и быстрый поиск, бинарный (двоичный), блочный, многоуровневый блочный. Их применение для внутреннего и внешнего поиска.

Использование деревьев в задачах поиска, деревья поиска.

Хэширование и разработка хэш-функций, удовлетворяющих требованиям. Методы борьбы с коллизиями: метод цепочек, рехэширование. Виды функций рехэширования. Первичные и вторичные скопления.

Механизм бэктрекинга. Пример: формирование набора чисел с заданной суммой. Поиск одного решения. Поиск всех решений. Варианты организации режима возвратов. Схема реализации бэктрекинга на языке Pascal. Реализация перебора с возвратом: формирование набора чисел с заданной суммой, задача о 8 ферзях, задача об устойчивых браках. Поиск одного решения и всех решений. Внимание на глобальную оптимизацию. В задаче о 8 ферзях – на структурирование информации (вместо того, чтобы проверять каждую клеточку по отдельности, манипулируем горизонталями, вертикалями и диагоналями), в задаче об устойчивых браках – на сокращение перебора.

Тема 9. Алгоритмы на графах (4 ч.)

Представление графов в памяти компьютера и операции над графами: создание, добавление, поиск и удаление вершин и дуг. Алгоритмы поиска на графах кратчайших путей, минимального сечения, построения остовного дерева.
  1. Методические рекомендации (материалы) преподавателю:

На лекциях используется «проблемный» подход к изложению материала: материал каждой лекции иллюстрируется примерами, рассматриваются нестандартные ситуации, требующие решения с использованием рассматриваемого материала. При этом студенты должны активно участвовать в обсуждении вопросов, выработке решений, предлагаемые студентами решения, обсуждаются, анализируются и оцениваются в ходе лекции. Предлагается рассматривать не только «верные», оптимальные решения, но и решения, приводящие к ошибкам.

По каждому рассматриваемому на лекции вопросу следует предложить задачи для самостоятельного решения и вопросы для самостоятельного изучения с использованием материалов, размещенных на сервере.

На лабораторных занятиях используются следующие методы обучения и контроля усвоения материала:
    1. выполнение лабораторных работ по теме занятия сопровождается контрольным опросом;
    2. обсуждение различных вариантов решения, предложенных студентами, сравнение решений, анализ возможных ситуаций.
  1. Методические указания студентам:

Для решения практических задач и выполнения домашних заданий, для подготовки к контрольным работам рекомендуется использовать следующие основные источники:
  1. Королев Л.Н., Миков А.И. Информатика. Введение в компьютерные науки. М.: Высшая школа, 2009.
  2. Плаксин М.А. Тестирование и отладка программ – для профессионалов будущих и настоящих. М.: БИНОМ. Лаборатория базовых знаний, 2007.

При разработке программ на языке Pascal рекомендуется использовать справочную систему системы программирования, примеры и рекомендации по решению задач, приведенные в электронных пособиях по курсу, указанных в списке дополнительной литературы.

Студенту рекомендуется следующая схема подготовки к практическому занятию:
  1. проработать конспект лекций;
  2. проанализировать основную и дополнительную литературу, рекомендованную по изучаемому разделу;
  3. проанализировать варианты решений, предложенные преподавателем;
  4. при затруднениях сформулировать вопросы к преподавателю.

Студенту рекомендуется следующая схема подготовки к лекции:
  1. проработать конспект лекций;
  2. изучить материал, предложенный для самостоятельного изучения;
  3. выполнить предложенные преподавателем задания;
  4. при затруднениях задать вопросы к преподавателю при проведении индивидуальных консультаций.

Для самостоятельного изучения и подготовки к лекциям предлагается использовать электронные ресурсы, размещаемые на сервере.
  1. Рекомендации по использованию информационных технологий:

Все практические занятия проводятся в компьютерном классе. Программное обеспечение сети должно поддерживать
  1. возможность доступа к материалам для подготовки в различных форматах (документы MS Word, документы в формате HTML, презентации MS Power Point), размещаемым на сервере;
  2. разработки, тестирования, отладки программ, написанных на языке Pascal (Pascal ABC, Free Pascal);
  3. возможность оформления отчетов по выполненным заданиям с помощью текстовых редакторов и электронных таблиц (MS Word и Excel).

Авторы программы: __________________________________________ /Л.Н. Лядова /

__________________________________________ /М.А. Плаксин /

Тематический расчет часов

№
Наименование разделов и тем
(с разбивкой по модулям)
Аудиторные часы
Самостоятельная работа
Всего часов

Лекции
Семинарские или практические занятия
Всего







Модуль 1
16
16
32
40
72





Введение в теорию алгоритмов
2
0
 2
2
4


Решение задач с помощью компьютера
0
2
 2
2
4


Основы программирования на языках высокого уровня

0
4
 4
10
14


Машины Тьюринга
4
2
 6
4
10


Нормальные алгорифмы Маркова
2
2
 4
4
8


Тестирование и отладка программ

0
4
 4
8
12


Вычислимые функции
4
0
 4
4
8


Алгоритмическая неразрешимость
2
0
 2
2
4


Методы разработки алгоритмов
2
2
 4
4
8




Всего за модуль:
 16
 16
 32
 40
 72







Модуль 2
14
14
28
40
68





Рекурсия и итерация

4
4
 8
10
18


Развитие понятия алгоритма

2
0
 2
4
6


Ввод/вывод и работа с файлами

0
2
 2
6
8


Работа с массивами, строками и записями
0
4
 4
10
14


Понятие сложности алгоритма и классы сложности задач
2
0
 2
4
6


Формальные языки и понятие грамматики
4
2
 6
2
8


Способы описания алгоритмических языков
2
2
 4
4
8




Всего за модуль:
 14
 14
 28
 40
 68







Модуль 3
16
16
32
40
72





Рекурсивные данные и динамическое распределение памяти
4
4
 8
6
14


Операции над линейными списками
4
4
 8
10
18


Операции над бинарными деревьями
4
4
 8
12
20


Представление графов и операции над графами
4
4
 8
12
20




Всего за модуль:
 16
 16
 32
 40
 72







Модуль 4
22
22
44
40
84





Понятие файла
1
0
 1
2
3


Операции над файлами
1
2
 3
4
7


Основные понятия, задачи сортировки и поиска

1
0
 1
4
5


Сортировка массивов
1
4
 5
6
11


Внешние сортировки
2
4
 6
6
12


Поиск и хеширование
4
4
 8
8
16


Алгоритмы на графах
4
4
 8
4
12


Языки программирования
4
2
 6
2
8


Методы трансляции программ
4
2
 6
4
10




Всего за модуль:
 22
 22
 44
 40
 84







Всего за год:
68
68
136
152
288


Авторы программы: __________________________________________ /Л.Н. Лядова /

__________________________________________ /М.А. Плаксин /