Учебно- методический комплекс учебной дисциплины дпп. 04"Теоретические основы информатики" подготовки бакалавра по направлению 050200 «Физико-математическое образование» Работа принята в фонд учебно-методического управления пи юфу

Вид материалаУчебно-методический комплекс

Содержание


г.Ростов-на-Дону 2008г.
Кузнецова Т.К.
Пояснительная записка
Концептуальные основы дисциплины
Цели изучения учебной дисциплины
Организация изучения дисциплины
Тематический план
Содержание курса лекций
Содержание лабораторных занятий
Методические рекомендации для преподавателей
Методические рекомендации для студентов
Контрольные вопросы и задания для самостоятельной работы по теме: «Элементы теории информации»
Контрольные вопросы и задания для самостоятельной работы по теме: «Понятие алгоритма и рекурсивный подход в программировании»
N меток. Построить такое же количество меток справа от имеющихся через одну пустую. е) на ленте находятся два числа N
While ... do
Контрольные вопросы и задания для самостоятельной работы по теме: «Моделирование как основной метод научного познания»
ТЕСТ для проверки уровня знаний по дисциплине
Шкала оценки
Критерии оценки самостоятельной работы
Ключевые понятия учебной дисциплины (глоссарий)
...
Полное содержание
Подобный материал:
  1   2   3


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Федеральное государственное образовательное учреждение высшего профессионального образования

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Педагогический институт


Кафедра информатики




"Утверждаю"______________

Руководитель ПИ ЮФУ, д.п.н., профессор В.И. Мареев


Учебно- методический комплекс учебной дисциплины




ДПП.04“Теоретические основы информатики”


подготовки бакалавра

по направлению 050200 «Физико-математическое образование»


Работа принята в фонд учебно-методического управления ПИ ЮФУ


__________________________________________________200_ г.
^

г.Ростов-на-Дону

2008г.




Составитель:

Канд. техн. наук, доцент Морозов В. А.


УМК утвержден на заседании кафедры информатики

протокол № 6 от «06» марта 2008 г.


Заведующий кафедрой информатики:

кандидат физико-математических наук, доцент^ Кузнецова Т.К.


УМК утвержден ученым советом ПИ ЮФУ

Пр.№____ от "____" __________________2008г.


Председатель ученого совета,

Руководитель Пи ЮФУ, д.п.н., профессор В.И. Мареев

^ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Общая характеристика дисциплины и ее основных функций

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

Дисциплина «Теоретические основы информатики» является инвариантным компонентом подготовки бакалавра физико-математического образования и магистра профильной подготовки «Информатика в образовании».

«ТОИ» - бурно развивающаяся ветвь информатики, прогресс в развитии которой очевиден. Ее роль и место определяются в основном следующими факторами:

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

- требуется постоянное научное сопровождение увеличивающегося объема практических разработок, связанных с созданием, внедрением и эксплуатацией информационных систем. Все прикладные аспекты и решения основываются на построенном таким образом теоретическом фундаменте и, ели угодно, являются его следствием;

- особенностью дисциплины ТОИ, состоящей в том, что прикладная ее составляющая оказывается востребованной многими людьми, в том числе весьма далекими от научной сферы;

- тем, что ТОИ – наука мировоззренческая уже хотя бы потому, что предметом ее изучения является одна из исходных категорий мироздания – информация. Естественно, студенты должны осознать фундаментальность и универсальность законов, применяемых при обработке и представлении информации.

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

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

Дисциплина «Теоретические основы информатики» является одним из основных элементов блока ДПП профильной подготовки бакалавров физико-математического направления в образовании и магистров профильной подготовки информатика в образовании (индекс ДПП. 04). Содержание дисциплины определяется государственным образовательным стандартом высшего профессионального образования и содержит такие разделы, как основные понятия теории информации, элементы теории кодирования, представления и обработка чисел в вычислительных системах, системы счисления, элементы теории алгоритмов, частично-рекурсивные функции, формализация понятия алгоритма и его представления, элементы теории конечных автоматов.

^ Концептуальные основы дисциплины

«Теоретические основы информатики»

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

Концепция гуманизации высшего профессионального образования, особенно актуальная для негуманитарных его направлений, к которым в том числе относится и высшее педагогико - информационное образование. Эта концепция является одной из основ реализации современного принципа образования – принципа гуманизации.

Концепция личностно-ориентированного обучения и воспитания, базирующаяся на принципах природо- и культуросообразности, находит реальное воплощение в сфере высшего педагогико – информационного образования, в том числе и в подготовке по дисциплине «Теоретические основы информатики».

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

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

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

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

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

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

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

^ Цели изучения учебной дисциплины

Целью изучения дисциплины ТОИ является:

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

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

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

- оказание влияния на формирование у студентов информационной, аналитической и методической культуры; на формирование культурной, профессиональной и гражданской самоидентификации личности студента;

- формирование у студентов адекватной системы ценностных ориентиров, прежде всего системы общенациональных ценностей.

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

- математическое моделирование для фиксации результатов познавательного процесса в виде знаковых и математических моделей;

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

- методы эффективного программирования для реализации алгоритмов на различного рода вычислительных и информационных системах;

- выполнение и анализ результатов вычислительного эксперимента для получения новых знаний об изучаемом объекте (предмете, процессе, явлении реального мира) с помощью современных вычислительных систем;

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

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

- получить знания об информации, ее видах, формах, единицах измерения и способах их введения;

- знать современные информационные технологи, их назначение, характеристики и перспективы развития, а также основные положения концепции информатизации современного общества;

- понимать значение вычислительных систем как универсальных средств обработки информации;

- уметь применять различные формы представления алгоритмов и преобразовывать алгоритмы из одной формы в другую;

- знать методы и способы формализации алгоритма, элементы теории графов;

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

^ Организация изучения дисциплины

Данный курс является обязательным и читается всем студентам, специализирующимся в области информационных технологий (3-й курс, V и VI семестры).

Основные организационные формы реализации учебно-методического комплекса – лекции и лабораторные занятия. Для контроля усвоения применятся тестирование и экзамены.

В лекционном курсе необходимо изложить основные разделы учебной дисциплины ТОИ и обеспечить усвоение студентами основных понятий, положений и методов.

В ходе лабораторных работ основные понятия и методы закрепляются в ходе решения специально подобранных задач на компьютере.


^ Тематический план



Название тем


Количество часов


Лекции


Лаборат.


Самост


Всего


1.

Информация, информатика и информационные процессы в обществе.


4

2

4

10

2.

ЭВМ как универсальное средство обработки информации.


4

6

4

14

3.

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


4

10

8

22

4.


Рекурсивный подход в программировании.


8

10

8

26

5.

Основные методы разработки эффективных алгоритмов.


8

8

10

26

6.


Основные понятия теории графов.


6


8


8


22


7.

Моделирование как основной метод научного познания. Различные виды моделей.


8

10

8

26

8.

Алгоритмы оптимизации на сетях и графах. Понятие жадного алгоритма. Матроиды. Теорема Радо-Эдмондса. Приближенные комбинаторные алгоритмы, оценки их точности. Аппроксимируемость трудных задач.

12

18

12

42

Итого:


54


72


72


198



^ СОДЕРЖАНИЕ КУРСА ЛЕКЦИЙ

Лекция № 1 (4 часа)

Информация, информатика и информационные процессы в обществе

Информатика как наука о технологии обработки информации. Ее цель, задачи, объект, предмет. Информация, ее виды, формы и единицы измерения. Представление информации в компьютере. Характеристика основных исторических этапов развития процессов сбора, передачи, обработки и накопления информации. Информационные системы, их функционирование. Современные информационные технологии, их характеристика и перспективы развития. Основные положения концепции информатизации общества.

Лекция № 1.1. Информация и информатика, их место и роль в современной науке и образовании

Цель: дать характеристику информации и информатики в современной науке и в образовании будущего специалиста в области информационных технологий, охарактеризовать основные исторические этапы развития процессов сбора, передачи, обработки и накопления информации.
  1. Информатика как наука о технологии работы с информацией, ее предмет, цель и задачи.
  2. Современное представление об информации, ее виды, формы и единицы измерения.
  3. Характеристика основных исторических этапов развития процессов сбора, передачи, обработки и накопления информации.
    1. Появление письменности и ее роль. «Бумажные» технологии, их возникновение и развитие. Развитие средств передачи информации. Предпосылки к появлению первых компьютеров.

Лекция № 1.2. Информационные процессы в современном обществе

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

Лекция № 2 (4 часа)

ЭВМ как универсальное средство обработки информации

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

Компьютер как универсальное средство обработки информации

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

Лекция № 3 (4 часа)

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

Алгоритм, понятие алгоритма, его основные свойства. Назначение алгоритмов. Виды алгоритмов. Линейные и разветвленные алгоритмы. Графический алгоритм. Элементы графического алгоритма. Численные алгоритмы, логические алгоритмы игр. Уточнение понятия алгоритма, 3 основные направления. Применение алгоритмов для решения различных задач.

Лекция № 3.1. (2 часа) Алгоритм, его виды свойства

Цель: дать понятие алгоритма, показать его сферу применения алгоритмов и раскрыть его свойства.
  1. Понятие алгоритма и его применение.
  2. Основные свойства алгоритма.
  3. Виды алгоритмов. Линейный алгоритм. Разветвляющийся алгоритм.
    1. Циклический алгоритм (с предусловием, с постусловием, с заранее определенным числом повторений, с выходом по условию). Рекурсивный алгоритм.

Лекция № 3.2. (2 часа) Формализация понятия алгоритма

Цель: показать необходимость формализации понятия алгоритма и показать методы осуществления такой формализации.
  1. Формальное представление алгоритма как метод доказательства его существования.
  2. Словесная запись алгоритма на формальном и неформальном языках.
  3. Графическая запись алгоритма и ее основные элементы.
  4. Способы формализации понятия алгоритма.
  5. Моделирование с помощью вычислимых и частично вычислимых функций. Применение абстрактных машин Тьюринга и Поста. Нормальный алгоритм Маркова.

Лекция № 4 (8 часов)

Рекурсивный подход в программировании

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

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

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

Лекция № 4.1. (4 часа) Рекурсивный подход при реализации алгоритмов

Цель: охарактеризовать рекурсивный подход к доказательству существования алгоритма.
  1. Понятие вычислимости и вычислимой функции.
  2. Определение класса рекурсивных целочисленных функций. Частично рекурсивные и общерекурсивные функции.
  3. Схема примитивной рекурсии.
    1. Суперпозиция функций. Операция минимизации. Программирование рекурсивных функций. Рекурсия как способ понижения размерности задачи.
    2. Рекурсия в эвристических алгоритмах.

Лекция № 4.2. (4 часа) Меры сложности алгоритмов

Цель: охарактеризовать различные подходы к измерению сложности алгоритмов, дать понятия неразрешимой алгоритмической проблемы, «трудной» задачи и полиноминального алгоритма.
  1. Основная гипотеза теории алгоритмов (тезис Чёрча).
  2. Применение абстрактных машин и нормальных алгоритмов Маркова при оценке сложности алгоритма.
  3. Средняя и асимптотическая сложность алгоритма. Сравнение рекурсии и итерации.
  4. Неразрешимые алгоритмические проблемы. Понятие «трудной» задачи.
  5. Полиномиальная сложность. Совпадение классов полиномиальных и реально выполнимых алгоритмов.

Лекция № 5 (8 часов)

Основные методы разработки эффективных алгоритмов

Основные понятия структур данных. Массивы как структуры данных. Метод балансировки. Динамическое программирование (списки, стек, очередь, двусвязный список, деревья). Файловые типы данных (типизированные, текстовые, нетипизированные файлы). Сортировки файлов.

Лекция № 5.1. (4 часа) Оценка сложности алгоритмов и методы ее оценки

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

Лекция № 5.2. (2 часа) Способы решения «трудных» задач

Цель: показать методы оценки сложности «трудных» задач и способы их приближенного решения.
  1. Приблизительный расчет времени решения прикладных задач при полиномиальной и экспоненциальной степенях асимптотической сложности.
  2. Способы решения «трудных» задач.
  3. Поиск в глубину и его асимптотическая сложность.
  4. Поиск в ширину и мера его асимптотической сложности.

Лекция № 5.3. (2 часа) Основные методы разработки эффективных алгоритмов

Цель: дать понятие о структурах данных и об их эффективном использовании при программировании.
  1. Основные понятия структур данных, массивы и их виды. Метод балансировки.
  2. динамическое программирование как один из способов уменьшения емкостной сложности задачи.
  3. Файловые типы данных. Сортировка файлов.

Лекция № 6 (6 часов)

Основные понятия теории графов

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

Лекция № 6.1. (2 часа) Основные определения и понятия теории графов

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

  1. Общие определения графа, способы его задания.
  2. Геометрическое представление графов. Изоморфизм.
  3. Пути, цепи, контуры, циклы. Части графа. Матрицы графов.

Лекция № 6.2. (4 часа) Применение теории графов при решении прикладных задач

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

Лекция № 7 (8 часов)

Моделирование как основной метод научного познания

Моделирование как необходимый этап познания сущности изучаемого явления или процесса при разработке его теории. Гипотезы как необходимые признаки, определяющие свойства разрабатываемой модели, явления или процесса. Различные виды моделей. Математическое моделирование. Дискретный характер ЭВМ.

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

Лекция № 8 (12 часов)

Алгоритмы оптимизации на сетях и графах

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

Лекция № 8.1. (2 часа) Алгоритмы оптимизации обработки информации

Цель: охарактеризовать способы оптимального кодирования и декодирования различных видов информации.
  1. Кодирование числовой и текстовой информации.
  2. Кодирование и декодирование звуковой и графической информации. Теорема отсчетов (теорема В. А.Котельникова).
  3. Технология дискретизации непрерывного сигнала посредством развертки по времени и квантования по видам и величине. Примеры.

Лекция № 8.2. (2 часа) Применение теории минимизации булевых функций

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

Лекция № 8.3. (2 часа) Нормирование и оценка функциональных свойств алгоритма

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

Лекция № 8.4. (4 часа) Алгоритмы оптимизации на сетях и графах

Цель: охарактеризовать прикладные методы оптимизации на сетях и графах.
  1. Понятие оптимизации в программировании. Оптимизация на сетях и графах.
  2. Понятие «жадного» алгоритма.
  3. Применение «жадного» алгоритма для аппроксимации при решении «трудных» задач.

Лекция № 8.5. (2 часа) Оптимизация построения алгоритмов

Цель: показать методы алгоритмизации и возможности построения системы автоматизированного алгоритмирования.
  1. Структурная теорема и пути стандартизации процедур обработки информации в алгоритмах.
  2. Концептуальные основы проблемной ориентации алгоритмов информационных технологий.
  3. Проблема автоматизированного алгоритмирования.