Информатика 2011-2012г

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Петрозаводский государственный университет

Математический факультет

Кафедра информатики и математического обеспечения

УТВЕРЖДАЮ

Декан математического факультета

_______________

"_____"__________________2012 г.

Рабочая программа дисциплины

Информатика

Направление подготовки

010100 - Математика

Профиль подготовки

Математика

Квалификация (степень) выпускника

Бакалавр

Форма обучения

очная

Петрозаводск

2012

Общие сведения о дисциплине

Название дисциплины – Информатики

Факультет, на котором преподается данная дисциплина - математический

Направление подготовки – Математика

Квалификация (степень) выпускника - Бакалавр

Цикл дисциплин – естественно-научный

Часть цикла – вариативная

Курс - 2

Семестры – 3, 4

Всего зачетных единиц – 7

Всего часов – 252

Аудиторные занятия 108 часов (лекции 36 часов, лабораторные занятия – 72 часа, практические занятия 0 часов)

Самостоятельная работа – 144 часа

Экзамен - 4 семестр

Зачет – 3 семестр

Составитель рабочей программы – доцент каф. ИМО

1. Цели освоения дисциплины

Целями освоения дисциплины «Информатика» являются подготовка в области применения современной вычислительной техники для решения практических задач обработки данных, математического моделирования, информатики, получение высшего профессионального (на уровне бакалавра) образования, позволяющего выпускнику успешно работать в избранной сфере деятельности с применением современных компьютерных технологий.

2. Место дисциплины в структуре ООП бакалавриата

Дисциплина входит в вариативную часть естественно-научного цикла дисциплин. Для изучения дисциплины требуются предварительные знания на уровне профильного курса «Основы информатики», а также математического анализа, алгебры, аналитической геометрии. Знания и умения, приобретенные студентами в результате изучения дисциплины, будут использоваться при изучении последующего курса «Информатика», а также при изучении курсов компьютерных технологий в математике, численных методов, при изучении некоторых спецкурсов, при выполнении курсовых и дипломных работ, связанных с математическим моделированием и обработкой данных.

3. Компетенции обучающегося, формируемые в результате освоения дисциплины:

В результате освоения дисциплины частично формируются следующие компетенции::

·  способность применять знания на практике (ОК-6);

·  способность приобретать новые знания, используя современные образовательные и информационные технологии (ОК-8);

·  фундаментальная подготовка по основам профессиональных знаний и готовность к использованию их в профессиональной деятельности (ОК-11) - частично;

·  навыки работы с компьютером (ОК-12);

·  базовые знания в областях информатики и современных информационных технологий, навыки использования программных средств и навыки работы в компьютерных сетях, умение создавать базы данных и использовать ресурсы Интернет (ОК-13) - частично;

·  способность к анализу и синтезу (ОК-14) - частично;

·  способность к письменной и устной коммуникации на русском языке (ОК-15) - частично;

·  умение понять поставленную задачу (ПК-2);

·  умение формулировать результат (ПК-3);

·  умение на основе анализа увидеть и корректно сформулировать результат (ПК-5);

·  умение ориентироваться в постановках задач (ПК-8);

·  самостоятельное построение алгоритма и его анализ (ПК-11);

·  понимание того, что фундаментальное знание является основой компьютерных наук (ПК-12) - частично;

·  владение методом алгоритмического моделирования при анализе постановок математических задач (ПК-19) - частично;

·  владение методами математического и алгоритмического моделирования при анализе теоретических проблем и задач (ПК-20) - частично;

·  возможность преподавания физико-математических дисциплин и информатики в средней школе и средних специальных образовательных учреждениях на основе полученного фундаментального образования (ПК-29) - частично.

В результате освоения дисциплины обучающийся должен:

§  Знать:

– основные способы организации данных в файлы;

– абстракции основных структур данных, методы их обработки и реализации;

– основные алгоритмы сортировки и поиска;

– основные понятия объектно-ориентированного программирования;

– возможности создания графических приложений на языке программирования;

§  Уметь:

– организовывать и обрабатывать файлы данных;

– применять сложные структуры данных в различных задачах;

– использовать алгоритмы сортировки и поиска;

– составлять программы построения графических изображений.

§  Владеть:

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

4. Структура и содержание дисциплины «Информатики»

Общая трудоемкость дисциплины составляет 7 зачетных единиц 252 часа (108 аудиторных и 144 самостоятельная работа, из них 36 экзамен).

№ п/п	Раздел Дисциплины	Семестр	Неделя семестра	Виды учебной работы, включая самостоятельную работу студентов, и трудоемкость (в часах)	Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам)
Лек.	Лаб.	Сам.
1	Понятие файла. Текстовый и двоичный поток. Способы организации файлов. Общий алгоритм работы с файлами. Функции для работы с файлами. Использование командной строки для ввода имен файлов.	3	1	1	2	2
2	Способы использования файлов. Ввод/вывод символов. Построчный ввод/вывод. Форматный ввод/вывод. Ввод/вывод записей. Организация базы данных в виде файла.	3	2-3	2	4	6	Прием лабораторных работ
3	Линейные списки, основные свойства, операции. Некоторые специальные списки: стек, очередь, дек. Реализации стека в виде последовательного представления. Объявление указателей на список. Функции управления динамической памятью.	3	4-5	2	4	6	Прием лабораторных работ
4	Построение связанного списка. Обход связного списка. Вставка и удаление элемента в различные позиции связанного списка. Организация стека и очереди в виде связного списка	3	6-7	2	4	6	Прием лабораторных работ
5	Списки с двумя связями. Циклические списки, списки с 1,5 связями. Сложные структуры в динамической памяти.	3	8-9	2	6	8	Прием лабораторных работ
6	Сравнение последовательного и связного представления списков. Применение связанных списков: разреженные матрицы, карта дорог, представление многочленов в аналитических вычислениях.	3	10-11	2	4	6	Прием лабораторных работ
7	Понятие бинарного дерева. Построение двоичного дерева. Рекурсивные и стековые реализации обходов деревьев. Алгоритмы обработки деревьев.	3	12-13	2	4	6	Прием лабораторных работ
8	Произвольные деревья. Соответствие лесов и бинарных деревьев. Сбалансированные и оптимальные деревья. Другие представления деревьев. Cкобочные представления деревьев. Польская запись выражений.	3	14-15	2	6	8	Прием лабораторных работ
9	Понятие вычислительной сложности алгоритмов. Классы алгоритмов сортировки. Сортировка вставками. Метод Шелла. Обменная сортировка. Быстрая сортировка Хоара. Сортировка выбором, слиянием. Внешняя сортировка.		16-18	3	6	8	Прием лабораторных работ Зачет
10	Постановка задачи поиска. Классификация методов поиска. Последовательный поиск. Быстрый последовательный поиск. Поиск в упорядоченной таблице.	4	1-3	2	6	8	Прием лабораторных работ
11	Бинарное упорядоченное дерево. Поиск со вставкой по бинарному дереву. Хеширование. Метод цепочек. Поиск со вставкой по открытой рассеянной таблице.	4	4-5	2	6	8	Прием лабораторных работ
12	Основные теоретические положения ООП. Объектная декомпозиция. Объявление класса. Иерархия классов. Инкапсуляция, наследование, полиморфизм.	4	6-7	2		2	Прием лабораторных работ
13	Основные элементы языка java. Структура программы на языке java. Консольные приложения на java.	4	8-9	2	4	6	Прием лабораторных работ
14	Принципы построения графического интерфейса. Основные графические примитивы в языке java.	4	10-11	2	4	6	Прием лабораторных работ
15	Алгоритмы машинной графики. Преобразование координат. Рекурсии и фракталы. Анимация.	4	12-13	2	4	6	Прием лабораторных работ
16	Компоненты графического приложения. События, слушатели и обработчики событий.	4	14-15	2	4	6	Прием лабораторных работ
17	Разработка графического приложения: построение графика заданной функции с вводом значений параметров.	4	16-17	2	6	8	Прием лабораторных работ
18	Другие парадигмы программирования: логический подход; функциональное программирование	4	18	2		2	Прием лабораторных работ
						36	Экзамен
				36	72	144	Всего 252 часа

5. Образовательные технологии

Сочетание традиционных образовательных технологий в форме лекции с компьютерными автоматизированными информационными технологиями при выполнении лабораторных работ и проведении контрольных мероприятий (экзаменов, зачетов, промежуточного тестирования).

6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.

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

cs. karelia. ru/~budniko/ai-project/index. html

а также проверки и приема текущих лабораторных работ, зачета в конце 3 семестра и экзамена в конце 4 семестра.

Перечень заданий лабораторных работ

Лабораторная работа 1. Текстовые файлы (использовать имена файлов в качестве параметров командной строки).

Некоторые варианты:

1.  Дан текстовый файл, выровненный по левому краю - программа на языке Си. Для каждого символа “{“ вставлять с новой строки по три пробела до соответствующего “}”. Результат записать в новый файл.

2.  Дан текстовый файл - программа на языке Си. Проверить его на соответствие операторных скобок “{“ – “}”. Программа должна быть синтаксически корректной, т. е. символ “}” на должен предшествовать “{“.

3.  Дан текстовый файл - программа на языке Си. Подсчитать, сколько раз имя переменной встречается в программе. Имя ввести. (В одной строке переменная может встречаться более одного раза).

4.  Дан текстовый файл - программа на языке Си. Выполнить процедуру разрезания тех строк, в которых стоит “{“ или “}”, так, чтобы эти символы оказались в отдельной строке. Результат записать в новый файл.

5.  Дан текстовый файл - программа на языке Си. Имя переменной, записанное строчными буквами, заменить на имя из прописных букв. Имя ввести. (В одной строке переменная может встречаться более одного раза). Результат записать в новый файл.

Лабораторная работа 2. Файлы записей.

Работа состоит из двух программ:

1.  Программа, формирующая файл записей. В качестве записей использовать свой вариант работы со структурами. Файл должен содержать 8-10 записей.

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

а) просмотр файла;

б) один пункт задания из работы со структурами;

в) корректировку одного поля i-ой записи (i ввести);

г) выход из программы.

Лабораторная работа 3. Линейный список в динамической памяти.

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

1.  строкового;

2.  символьного;

3.  целочисленного;

4.  вещественного.

Количество элементов списка заранее неизвестно. Список строить в прямом порядке, окончание ввода – введение условного символа. Символ этот в список не включается.

Предусмотреть возможность добавления и удаления элемента:

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

2.  n-м по порядку (кроме первого и последнего), число n ввести;

3.  перед цифрой 5 (кроме первого и последнего);

4.  после буквы “g” (кроме первого и последнего);

5.  предпоследнего элемента (в списке больше двух элементов);

6.  третьего по порядку (в списке больше трех элементов);

7.  второго по порядку (в списке больше двух элементов);

8.  в конце списка;

9.  в начале списка;

Лабораторная работа 4. Бинарные деревья

1.  Построить бинарное дерево одного из типов данных:

а) строкового;

б) целочисленного;

в) вещественного.

2.  Выполнить обход дерева рекурсивным и нерекурсивным (стековым) способами:

а) в прямом порядке;

б) в обратном порядке;

в) в концевом порядке.

3.  При обходе подсчитать:

а) количество неконцевых вершин дерева;

б) количество листьев дерева;

в) количество вершин, имеющих ровно одну не пустую связь;

г) количество вершин, имеющих хотя бы одну не пустую связь;

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

Лабораторная работа 5. Сортировка и поиск.

1.  Создать массив записей (записи считать из файла, заранее созданного). Использовать 8-10 записей, одно из полей взять в качестве ключа.

2.  Выполнить сортировку массива записей по ключу одним из методов:

а) выбором;

б) простыми вставками;

в) методом пузырька.

3.  Выполнить двоичный поиск в упорядоченном массиве записей по ключу.

Лабораторная работа 6. Хеширование.

Работа состоит из двух частей: сортировка и поиск.

Сортировка. Выполнить сортировку массива записей с использованием хеш-функции. В качестве записей взять фамилии студентов всей группы, записанные латиницей, в алфавитном порядке. Для получения ключа использовать 3 и 4 символы. Преобразовать ключ в адрес с использованием заданной хеш-функции согласно своему варианту задания. Способ разрешения коллизий – использование области переполнения. Оценить хеш-функцию (2/3 записей должны располагаться в основной области).

2.  Поиск. Ввести искомый ключ, преобразовать его в адрес. В основной области поиск выполнять по хеш-функции, в области переполнения – последовательный поиск. Отметить, где найдена запись (в основной области или области переполнения) или запись не найдена.

Варианты заданий.

Алгоритмы перемешивания:

a)  метод квадратов;

b)  сдвиг разрядов;

c)  сложение;

d)  выделение разрядов;

e)  преобразование системы счисления ключа.

Окончательное вычисление хеш-функции:

a)  деление по модулю;

b)  умножение на константу.

Лабораторная работа 7. Консольное приложение на языке java.

Разработать класс, содержащий поля данных и метод вычисления. Метод main должен обеспечивать необходимые вызова этого метода для вычисления выражения.

Некоторые варианты:

Найти значение выражения

 (2*5! + 3*8!)/(6! + 4!)

Рассчитать значение y, определив и использовав необходимую функцию

 y=(2+sin2)/(sin5 +5)+(6+sin6)/(sin3 +3)+(1+sin1)/(sin4 +4)

3.  Найти периметр треугольника, заданного координатами своих вершин. Определить функцию для расчета длины отрезка по координатам его вершин.

Лабораторная работа 8. Графическое приложение на языке java.

Некоторые варианты:

Пусть две точки заданы своими координатами (x1,y1) и (x2,y2). Прямая, проходящая через эти две точки, может быть описана следующим параметрическим представлением:

x=x1+(x2-x1)*t и y=y1+(y2-y1)*t.

При t=0 достигается конец отрезка (x1,y1), при t=1 – конец (x2,y2). При 0<T
Даны натуральные числа x1,y1 ,x2,y2, действительное число t (0<t<1). Построить отрезок с координатами концов (x1,y1), (x2,y2) и точку, делящую отрезок в отношении t/(1-t).

а) начертить узор, образованный 20 вложенными квадратами. Стороны первого квадрата параллельны осям координат экрана и равны 60. Вершины каждого последующего квадрата - это точки на сторонах предыдущего квадрата, делящие эти стороны в отношении равном 0,08.

б) из треугольников;

в) из пятиугольников.

2.  Нарисовать «кривые дракона» порядка n.

3.  Изобразить геометрическую фигуру, вращающуюся в трехмерном пространстве относительно вертикальной оси вращения.

Лабораторная работа 9. Разработка графического приложения:

Разработать графическое приложение, представляющее графическое окно. Часть окна отводится под график функции. Окно должно также содержать текстовые поля для ввода коэффициентов функции, кнопку для перерисовки окна. Вверху должен находиться заголовок, а в нижней части окна должно выводиться уравнение функции с конкретными значениями параметров. График должен содержать подписанные и размеченные оси координат. При вводе различных коэффициентов должна выполняться перерисовка осей.

Некоторые варианты:

1.  Улитка Паскаля:

 x=Acos2(t)+Bcos(t)
 y=Acos(t)sin(t)+Bsin(t), A>B, B>0, 0<=t<2Pi

Рассмотреть случаи, когда B>=2A; A<B<2A; A>B

2.  Спирограф

 x=(A-B)cos(t)+Dcos(w)
 y=(A-B)sin(t)-Dsin(w),w=(A/B)t, D<B<A

Угол t меняется от 0 до 2Pi*n, n равно B, деленному на наибольший общий делитель(НОД) B и A.

3.  Эпициклоида

 x=(A+B)cos(t)-Acos((A+B)t/A)
 y=(A+B)sin(t)-Asin((A+B)t/A),A>0, B>0

Рассмотреть следующие случаи:

a)  Если В/А есть целое, положительное число, то 0<= t< 2Pi

b)  Если В/А=p/q, где p и q - целые положительные взаимно простые числа, то 0<= t<2qPi.

4.  Декартов лист

 x =(3At)/(t3+1), y=(3At2)/(t3+1), - ∞< t < + ∞

5.  Циклоида

 x=At-Bsin(t)
 y=A-Bcos(t), 0<= t <=2Pi

Рассмотреть случаи: B>A, B<A, B=A

7. Учебно-методическое и информационное обеспечение дисциплины

а) основная литература:

,  А., Федюк программирования на языке Си. Петрозаводск : Изд-во ПетрГУ, 2010. , Соколов и структуры данных на С++. Петрозаводск, изд-во ПетрГУ, 2008 г.

3.  Богоявленская в программирование. — 2-е изд., стер. — Петрозаводск, 2006.

б) дополнительная литература:

зык программирования С. 2-е изд. СПб.: Невский диалект, 2001. рограммирование на языке Си для персонального компьютера IBM PC. М.: «Радио и связь», 1991. , Фомин на языке Си. М.: Финансы и статистика, 2005. Потопахин С. Освой на примерах. СПб.: БХВ-Петербург, 2006. , ж. Как программировать на С. М.: Бином-Пресс, 2009. рограммирование на языке С (Си). 3-е изд. М.: Издательский дом «Вильямс», 2006. скусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: «Вильямс», , 2007.

8.  скусство программирования для ЭВМ. Т.3. Сортировка и поиск. М.: «Вильямс»,, 2008.

в) программное обеспечение и Интернет-ресурсы:

1. Учебный ресурс по изучению информатики, доступ:

cs. karelia. ru/~budniko/ai-project/index. html

2. Учебный ресурс по основам ООП и Java, доступ:

http://kappa. cs. karelia. ru/~budniko/math1/resurs/index. html

3. В курсе используются следующие свободно-распространяемые программные продукты:

·  ОС на базе ядра Linux (openSUSE 11.3);

·  семейство компиляторов gcc;

·  отладчик gdb;

·  утилита make;

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

8. Материально-техническое обеспечение дисциплины

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

Программа составлена в соответствии с требованиями Федерального государственного образовательного стандарта высшего профессионального образования (ФГОС ВПО) с учетом методических рекомендаций и Примерной основной образовательной программы ВПО по направлению подготовки «Математика», квалификация Бакалавр.

Автор доц. каф. ИМО

Программа рассмотрена и утверждена на заседании кафедры ИМО

«13» апреля 2012 года, протокол № 4.

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

Программа одобрена на заседании учебно-методической комиссии математического факультета от 30 апреля 2012 года, протокол № 8.