Главная страница 1
Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

"Иркутский государственный педагогический университет"

Факультет математики, физики и информатики

Утверждено

на заседании совета факультета

математики, физики и информатики

протокол №­­­­­­_____от __________200 г.

Председатель совета________________

(Кузьмина Н.Д.)




УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ

ДС.Ф.00. Нестандартные задачи по программированию


Специальность: 050202 Информатика

Квалификация: Учитель информатики

Курс: 2

Семестр: 3

Форма обучения: очная
Количество часов на дисциплину: 96 час.

Количество аудиторных часов: 48 час.; из них:

Лекций: 48 час.

Самостоятельная работа: 48 час.
Итоговый контроль: зачет
I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

Место дисциплины

Дисциплина "Нестандартные задачи по программированию" является дисциплиной, формирующей профессиональное образование в программе подготовки учителя информатики.

Цель дисциплины


Сформировать у студентов более глубокое понимание основ программирования.

Задачи дисциплины

Задачи курса — обеспечить углубленное изучение базовых методов программирования и стандартных алгоритмов, познакомить студентов с нестандартными методами программирования.


Принципы отбора содержания и организации учебного материала

Учебный материал представлен тремя разделами: базовые методы программирования, стандартные алгоритмы и нестандартные приемы программирования. При построении содержания избрана стратегия повторения и углубленного изучения основ программирования с последующим переходом к более сложным и нестандартным методам.


Требования к освоению содержания дисциплины

Студент должен знать основные подходы к программированию, статические и динамические структуры данных, алгоритмы поиска, сортировки, алгоритмы на графах.

Студент должен уметь разрабатывать и реализовывать алгоритмы для конкретных задач и применять на практике различные структуры данных.

Студент должен владеть как основными методами программирования, так и нестандартными.


Виды контроля

Текущий — проводится по каждой учебной единице в форме проверки лабораторного задания.

Итоговый — проводится в форме зачета.
Планирование содержания дисциплины



Название модуля

Часы аудиторных занятий

Часы самостоятельной работы

Всего часов

Лекции

Лабор.

занятия


1

Базовые методы программирования

16




16

32

2

Стандартные алгоритмы

16




16

32

3

Нестандартные приемы программирования

16




16

32



II. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Модуль №1 Базовые методы программирования.
1). Основные подходы к программированию.

Процедурное программирование. Объектно-ориентированное программирование. Обобщенное программирование. Рекурсия.

2). Статические и динамические структуры данных.

Базовые типы данных. Структуры. Списки. Деревья.


Модуль №2 Нестандартные методы программирования.

1). Алгоритмы сортировки.

Сортировка и определение сложности алгоритмов сортировки. Сортировка вставками. Пузырьковая сортировка. Сортировка выбором. Быстрая сортировка. Сортировка слиянием. Пирамидальная сортировка. Сортировка перечислением. Сортировка всплытием. Сортировка бинарным поиском. Алгоритмы сортировки использующие структуру элементов: цифровая сортировка, корневая сортировка.

2). Алгоритмы на графах.

Алгоритмы обхода графов произвольно, в глубину, в ширину. Алгоритмы поиска кратчайшего пути. Алгоритмы поиска остовного дерева графа.

3). Алгоритмы решения переборных задач.

Жадные алгоритмы. Метод ветвей и границ. Алгоритмы решения задачи коммивояжера.
Модуль №3 Нестандартные приемы программирования.

Динамическое программирование. Численные алгоритмы. Эвристические алгоритмы. Генетические алгоритмы.


Основные понятия.

Алгоритм. Процедура. Рекурсия. Динамические типы данных. Граф.



III. ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
Задания для самостоятельной работы: по каждой из тем студент получает индивидуальное задание.
Контроль. Решенные задачи сдаются на проверку преподавателю.
IV. КОНТРОЛЬ КАЧЕСТВА ОСВОЕНИЯ ДИСЦИПЛИНЫ

1. Текущий контроль.

Проводится по каждой учебной единице в форме проверки лабораторного и самостоятельного задания.



2. Итоговый контроль.

Проводится в форме зачета.


Задания на зачет


  1. Реализовать быструю сортировку массива.

  2. Реализовать сортировку массива слиянием.

  3. Дан неубывающий массив целых положительных чисел: a[1] ≤ a[2] ... ≤ a[n]. Найти наименьшее целое положительное число, не представимое в виде суммы нескольких элементов этого массива (каждый элемент массива может быть использован не более одного раза). Число действий должно быть порядка n.

  4. Реализовать алгоритм Дейкстры нахождения кратчайшего пути из вершины i в вершину j.

  5. Реализовать алгоритм Флойда поиска всех кратчайших путей в графе.

  6. Реализовать алгоритм проверки связности графа.

  7. Найти клетку на поле размером m*n клеток, из которой за k или меньше ходов коня можно достичь как можно больше других клеток. Если таких клеток несколько, вывести любую из них.

  8. Дети решили проложить веревочный телеграф, который связал бы все дома, в которых они живут. Всего домов N. Даны координаты каждого дома в целых числах (Xi,Yi). Какие дома нужно соединить, чтобы связь была между всеми домами (возможно, через другие дома), а общая длина всех веревок была как можно меньше? (решить с помощью алгоритма Прима).

  9. Решить предыдущую задачу с помощью алгоритма Крускала.

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

  • Два целых числа: W и P.

  • Список труб. Каждая труба описывается тремя числами – номерами станций начала и конца трубы и стоимостью этой трубы.

Выходные данные: одна строка, содержащая стоимость конструирования системы распределения воды.

  1. Администратору необходимо объединить N хабов в сеть. Каждый хаб должен быть достижим от любого другого хаба (возможно, через промежуточные хабы). Имеются кабели различных типов и короткие кабели дешевле, поэтому требуется сделать такой план сети, чтобы максимальная длина используемых кабелей была как можно меньше. При этом не каждую пару хабов можно соединить. Ввод: N – число хабов, M – количество возможных соединений хабов. По каждой строке на возможное соединение: номера двух хабов, которые могут быть соединены, и длина кабеля. Вывод: максимальная длина кабеля, количество кабелей и по паре чисел на каждый кабель – номера хабов, соединенных этим кабелем.



V. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
1. Рекомендуемая литература.


  1. Шень А. Программирование: Теоремы и задачи. – М.: МЦМНО. – 1995. – 264 с.

  2. Баррон Д. Рекурсивные методы в программировании. – М.: Мир. – 1974.

  3. Алексеев В.Е., Таланов В. А. Графы и алгоритмы. Структуры данных. Модели вычислений. – М.: Издательство: Интернет-Университет инф.тех. – 2006. – 320 с.

  4. Топп У. Структуры данных в C++. – М.: "Издательство БИНОМ". – 2000. – 816 с.

  5. Страуструп Б. Язык программирования C++. – М.; СПб.: "Издательство БИНОМ"-"Невский Диалект". – 2001. – 1099 с.


2. Электронно-программные средства.
Библиотека книг по программированию на электронном носителе (имеется на кафедре математической информатики).

Составитель: ассистент кафедры математической информатики Казимиров А.С.

Утверждено

на заседании кафедры

математической информатики

(протокол № ___ от __________ 200_ г.)
Зав. кафедрой ______________________

Н.А. Перязев


Утверждено

на заседании УМС факультета

математики, физики и информатики



(протокол № ___ от ___________ 200_ г.)
Председатель УМС___________________

Н.Д. Кузьмина


Смотрите также:
Специальность: 050202 Информатика Квалификация: Учитель информатики Курс: 2 Семестр: 3 Форма обучения: очная Количество часов на дисциплину: 96 час. Количество аудиторных часов: 48 час.; из них: Лекций: 48 час
68.72kb.
1 стр.
Тематическое планирование По истории Класс 11 Учитель Дадыкина Ирина Николаевна
673.57kb.
4 стр.
Лекции, час. Самостоятельная и индивидуальная работа, час Итого часов по теме Итого количество баллов
74.25kb.
1 стр.
Курсовая подготовка* (целевые курсы пк количество часов 24, 36, 72, 108 час.)
74.62kb.
1 стр.
Пояснительная записка Целью курса «Информационные технологии в науке и образовании»
60.72kb.
1 стр.
Тематический план изучения дисциплины «Современный русский язык» № Тема Лекции час. Практические час. Самостоят и индивид работа Итого часов по теме
71.37kb.
1 стр.
Тематический план лекций по общей химии (осенний семестр) 2007-2008уч год № пп Тема лекций и их содержание Количество часов 4. 5 6 7 8
28.75kb.
1 стр.
Лекции (часов) Лабораторн и семинар занятия (час) Индив и самостоят работа (час) Формы контроля
83.85kb.
1 стр.
Тематическое планирование по математике Класс 2 Учитель : Сыропятова Диана Филипповна Количество часов: Всего 136 часов; в неделю 4 часа
233.22kb.
1 стр.
Учебно-методический комплекс на базе специального образования г. Ростов на Дону 2007 г. Печатается по решению кафедры гражданского права
180.06kb.
1 стр.
Программа предусматривает 18 часов лекций и 16 часов семинарских (практических) занятий. По окончании курса проводится зачет
127.1kb.
1 стр.
Учебный курс «Семья как объект социальной политики»
69.12kb.
1 стр.