Учебная программа дисциплины дс. Ф. 00. Нестандартные задачи по программированию Специальность: 050202 Информатика

Вид материала

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

Содержание Специальность: 050202 Информатика I. организационно-методический раздел Цель дисциплины Принципы отбора содержания и организации учебного материала Требования к освоению содержания дисциплины Виды контроля Планирование содержания дисциплины Ii. содержание дисциплины Модуль №2 Нестандартные методы программирования. Модуль №3 Нестандартные приемы программирования. Iii. организация самостоятельной работы Iv. контроль качества освоения дисциплины 2. Итоговый контроль. V. учебно-методическое обеспечение дисциплины 2. Электронно-программные средства.

Подобный материал:

• Учебная программа (Syllabus) Дисциплина: Международное право Специальность Специальность:, 409.7kb.
• Учебная программа курса для специальности 050203. 65 Физика с дополнительной специальностью, 127.56kb.
• Учебная программа (Syllabus) Дисциплина: «Информатика» Специальность Вычислительная, 323.55kb.
• Учебная программа (Syllabus) Дисциплина: inf1105,Информатика, 320.74kb.
• Рабочая программа по дисциплине Численные методы для специальности 050202 Информатика,, 229.53kb.
• Учебная программа курса для специальности 050203. 65 Физика с дополнительной специальностью, 283.66kb.
• Учебная программа (Syllabus) Дисциплина: «Основы геополитики» Специальность 050202, 365.05kb.
• Учебная программа (Syllabus) Дисциплина: «Современные конфликты и методы их урегулирования», 356.18kb.
• Учебная программа (Syllabus) Дисциплина: «Международное право» Специальность: 050202, 415.85kb.
• Учебная программа дисциплины ен. Ф 01 Математика и информатика Специальность: 031200, 139.17kb.

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

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

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

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

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


Утверждено

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

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

протокол №­­­­­­_____от __________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.
  
• Список труб. Каждая труба описывается тремя числами – номерами станций начала и конца трубы и стоимостью этой трубы.
  

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

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

V. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ


1. Рекомендуемая литература.

1. Шень А. Программирование: Теоремы и задачи. – М.: МЦМНО. – 1995. – 264 с.
   
2. Баррон Д. Рекурсивные методы в программировании. – М.: Мир. – 1974.
   
3. Алексеев В.Е., Таланов В. А. Графы и алгоритмы. Структуры данных. Модели вычислений. – М.: Издательство: Интернет-Университет инф.тех. – 2006. – 320 с.
   
4. Топп У. Структуры данных в C++. – М.: "Издательство БИНОМ". – 2000. – 816 с.
   
5. Страуструп Б. Язык программирования C++. – М.; СПб.: "Издательство БИНОМ"-"Невский Диалект". – 2001. – 1099 с.
   

2. Электронно-программные средства.


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

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

Утверждено

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

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

(протокол № ___ от __________ 200_ г.)


Зав. кафедрой ______________________

Н.А. Перязев


Утверждено

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

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

(протокол № ___ от ___________ 200_ г.)


Председатель УМС___________________

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