Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Общие рекомендации по проведению



Министерство образования и науки

Российской Федерации

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

Славянский-на-Кубани

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

(СГПИ)

 
 

 


КАФЕДРА ИНФОРМАТИКИ И МПИ

 

 

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ

 

Учебно-методическое пособие

К практическим занятиям и самостоятельной работе

Для студентов III курса

специальностей «математика» и «информатика»,
педагогических вузов

 

 

Славянск-на-Кубани

Издательский центр СГПИ

 
2011

ББК 32.81

Т33

 

Рекомендовано к печати

Учебно-методическим советом СГПИ

 

Рецензенты:

Дьяченко Л.Г., кандидат педагогических наук,
старший преподаватель кафедры общенаучных дисциплин НПИ КубГТУ

Радченко Н.Е., кандидат педагогических наук,
заведующий кафедрой ТиМПО и ОТД СГПИ.

 

 

Т33

Теоретические основы информатики : учебно-методическое пособие к практическим занятиям и самостоятельной работе для студентов III курса специальностей «математика» и «информатика» педагогических вузов / сост.: Е.П. Бакай, Е.В. Хмара ; Славянский-на-Кубани государственный педагогический институт. – Славянск-на-Кубани : Издательский центр СГПИ, 2011. – 51 с.

 

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

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

 

 

ББК 32.81

 

 

© Славянский-на-Кубани государственный педагогический институт, 2011

 

 
 
 


Содержание

Введение …………………………………………………………………...
Общие рекомендации по проведению практических занятий …….
1. Основы теории кодирования. Измерение информации в сообщениях. Подсчет количества информации ……………….
2. Системы счисления и представление информации в ЭВМ …….
3. Основы теории алгоритмизации задач …………………………….
4. Алгоритмы оптимизации на сетях и графах ……………………….
Литература …………………………………………………………………

Введение

 

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

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

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

Курс "Теоретические основы информатики" рассчитан на изучение в течение 6 семестра 3 курса обучения.

Для изучения выделяются темы:

· «Введение в теоретическую информатику»;

· «Основы теории кодирования»;

· «Системы счисления и представление информации в ЭВМ»;

· «Основы теории алгоритмизации задач»;

· «Основы моделирования»;

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

· «Алгоритмы решения комбинаторных задач».

В результате изучения курса "Теоретические основы информатики" студент должен знать:

− основные теоретические основания информатики (алгоритм, исполнитель алгоритма, виды информации, кодирование информации, информационные технологии, алгоритмически трудные и неразрешимые задачи, сложность задачи, различные виды и типы алгоритмов, основы компьютерного моделирования);

− основы теории кодирования; методы вычисления объема информации;

− теорию систем счисления, формы записи чисел в ЭВМ, методы перевода чисел из одной системы счисления в другую и выполнения математических операций в различных системах счисления;

− основы теории сложности алгоритмов; понятие сложности алгоритма, асимптотической сложности алгоритма, реально выполнимые алгоритмы; основы теории полиномиальных алгоритмов;

− алгоритмы оптимизации на сетях и графах; основные виды жадных алгоритмов; основы теории матроидов;

− основные методы разработки эффективных алгоритмов: метод балансировки, динамическое программирование, изменение представления данных, метод исчерпывающего поиска.

 

В результате изучения курса "Теоретические основы информатики" студент должен уметь:

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

− строить для целых чисел их прямой, обратный и дополнительный код;

− исследовать сложность алгоритмов решения задач, строить верхние и нижние оценки сложности алгоритмов;

− строить эффективные алгоритмы методами балансировки, динамического программирования, подбора представления данных, исчерпывающего поиска;

− использовать для решения прикладных задач графовые алгоритмы оптимизации Прима, Краскала, Дейкстры;

− строить алгоритмы решения базовых комбинаторных задач.

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

 

Общие рекомендации по проведению

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

 

На дисциплину «Теоретические основы информатики» отводится 56 часов в 5-ом семестре для специальности «Математика с доп. специальностью «Информатика» и 72 часа для специальности «Информатика».

На лекциях рассматриваются базовые понятия информатики (информация, алгоритм, сложность алгоритма, моделирование), основы теории систем счислений, основы теории кодирования и ее приложения для ЭВМ, теории сложности алгоритмов и теоретические проблемы алгоритмизации задач, алгоритмы поиска оптимального решения на графах, постановка важнейших проблем теоретической информатики.

На практических занятиях разбираются задачи:

− на вычисление объема информации в различных сообщениях и кодах, структурах данных;

− на запись и преобразование чисел, выполнение математических операций в различных системах счисления, представление информации в стандартных кодах ЭВМ;

− на построение алгоритмов теории кодирования (коды Хафмена, Фано, Хэмминга, Лемпел-Зива, алгоритмы шифрования);

− на построение эффективных алгоритмов поиска оптимального решения (жадные алгоритмы);

− на определение оптимального решения в графовых и сетевых моделях (потоки в сети).

В соответствии с тематическим планированием на практические занятия по специальности «Информатика» выделяется 40 часов, по специальности «Математика с дополнительной специальностью Информатика» – 24 часа. В связи с этим предлагается следующее распределение учебного времени на данный вид занятий:

Содержание практических занятий курса

Тема практического занятия Специальность «Информатика» Специальность «Математика»
1. Основы теории кодирования. Измерение информации в сообщениях. Подсчет количества информации. 4 часа (ПЗ № 1-2) 2 часа (ПЗ № 1)
2. Основы теории кодирования. Вычисление объема графической, текстовой, звуковой информации в ЭВМ. 2 часа (ПЗ № 3) 2 часа (ПЗ № 2)
3. Основы теории кодирования. Восстановление информации и избыточное кодирование. Биты четности, коды Хэмминга. 2 часа (ПЗ № 4) 2 часа (ПЗ № 3)
4. Основы теории кодирования. Оптимальное кодирование. Алгоритмы сжатия информации. Коды Фано, Хафмена и Лемпел-Зива. 4 часа (ПЗ № 5-6) 2 часа (ПЗ № 4)
5. Системы счисления. Системы с основаниями 2, 8, 16. Представление чисел, преобразование чисел. Методы триад и тетрад. 4 часа (ПЗ № 7-8) 2 часа (ПЗ № 5)
6. Системы счисления. Сложение, вычитание, умножение чисел в различных системах счисления. 4 часа (ПЗ № 9-10) 4 часа (ПЗ № 6-7)
7. Представление чисел в памяти ЭВМ. Прямой, обратный и дополнительные коды. Двоично-десятичный код. Нормализованный код. 4 часа (ПЗ № 11-12) 2 часа (ПЗ № 8)
8. Алгоритмизация задач. Запись алгоритмов. Структурные схемы алгоритмов. Псевдокод. Итерационные и рекурсивные алгоритмы. Оценки сложности алгоритмов. 4 часа (ПЗ № 13-14) 2 часа (ПЗ № 9)
9. Жадные алгоритмы на графах. Задача Прима-Краскала. 4 часа (ПЗ № 15-16) 2 часа (ПЗ № 10)
10. Жадные алгоритмы на графах. Задача Дейкстры. 4 часа (ПЗ № 17-18) 2 часа (ПЗ № 11)
11. Алгоритмы оптимизации на графах. Потоки в сетях. Задача Форда-Фалкерсона. 4 часа (ПЗ № 19-20) 2 часа (ПЗ № 12)
  Всего часов

 

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

В качестве итоговой аттестации по дисциплине для специальности «Информатика» выступает экзамен, а для специальности «Математика» – зачет.

Предлагается следующая система оценивания знаний студентов по обеим специальностям.

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.