Учебно-методический комплекс дисциплины «Теоретические основы информатики» Специальность 050202. 65 «Информатика» icon

Учебно-методический комплекс дисциплины «Теоретические основы информатики» Специальность 050202. 65 «Информатика»


Смотрите также:
Учебно-методический комплекс дисциплины «Компьютерное моделирование» Специальность 050202...
Учебно-методический комплекс дисциплины «компьютерные сети...
Учебно-методический комплекс дисциплины «Исследование операций» Специальность 050202...
Учебно-методический комплекс по специальностям 050202. 65 и 050200. 62 «Информатика» Москва 2008...
Учебно-методический комплекс по дисциплине теоретические основы информатики для специальности...
Учебно-методический комплекс дисциплины «Основы информатики» Специальность 071301...
Учебно-методический комплекс математические понятия в школьном курсе информатики (курс по выбору...
Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” Специальность...
Учебно-методический комплекс по дисциплине «химия» по специальности 050202...
Учебно-методический комплекс по дисциплине «программное обеспечение эвм» для дневного отделения...
Учебно-методический комплекс дисциплины «Математическая логика» специальности 050202...
Учебно-методический комплекс дпп ф...



Загрузка...
страницы:   1   2
скачать
Государственное образовательное учреждение высшего профессионального образования

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


«Утверждаю»

проректор по учебной работе

___________ Шумакова А.В.

«___»_______________ 2011 г.


УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС


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


Специальность 050202.65 «Информатика» c дополнительной специальностью 050201.65 «Математика»



«Разработано»

____________Красильников В.В.

профессор кафедры

прикладной информатики

и информационных технологий

«Утверждено»

на заседании кафедры прикладной информатики и информационных технологий

протокол № ____ от _________2011 г.

Зав. кафедрой ________Тоискин В.С.





«Согласовано»

____________ Сейфулина Г.В.

декан психолого-педагогического факультета


Ставрополь 2011


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


Учебно-методический комплекс разработан в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования для специальности 050202.65 «Информатика» с дополнительной специальностью 050201.65 «Математика» на основе макета, утвержденного Учебно-методическим объединением по специальностям педагогического образования и рекомендательного письма Федеральной службы по надзору в сфере образования и науки от 17.04.2006 №02-55-77ин/ак.

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

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

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

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

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

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

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


^ 1. ТРЕБОВАНИЯ К ОБЯЗАТЕЛЬНОМУ МИНИМУМУ

СОДЕРЖАНИЯ ДИСЦИПЛИНЫ


Код по ГОС ВПО

Название дисциплины и дидактическое содержание

Трудоемкость по ГОС ВПО



ДПП.Ф.О. 8



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

Предмет информатики. Место информатики в системе наук.

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

Математическая кибернетика. Информация и управление. Математические аспекты кибернетики.

108


II. РАБОЧАЯ ПРОГРАММА

  1. ^

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


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

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

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

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

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

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

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


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

После изучения дисциплины студент должен:

  • иметь представление об общих проблемах и задачах теоретической информатики;

  • иметь представление об основных принципах и этапах информационных процессов;

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

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

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

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

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

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

  • знать количественные и статистические меры информации и виды информационных алфавитов; энтропию и количественные меры различных видов сообщений;

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

  • уметь количественно оценивать передаваемую информацию и информационный процесс; строить информационные модели сигналов и сообщений;

  • уметь оценивать скорость, пропускную способность, помехоустойчивость непрерывных и дискретных информационных систем;



^ 3. Объем дисциплины и виды учебной работы

Вид учебной работы

Трудоемкость (час.)

^ Аудиторные занятия:

60

лекции

36

лабораторно-практические занятия

24

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

48

Общая трудоемкость

108


^ 4. Семестры и виды отчетности по дисциплине

Семестр

Вид отчетности

6

Экзамен


^ 5. Содержание дисциплины


5.1. Разделы дисциплины и виды занятий



п/п


Раздел (тема) дисциплины

Лекции

Лабораторно-практические

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


^ Раздел I. Основные понятия теории информации




Тема 1. Предмет информатики, основные понятия

4




2




Тема 2. Количественная оценка информации

4

4

4




Тема 3. Помехоустойчивость и эффективность информационных систем

4

4

6

^ Раздел II. Математические основы информационных процессов




Тема 4. Теория кодирования.

6

4

8




Тема 5. Теория автоматов.

6

4

8




Тема 6. Теория распознавания.

4

4

8

^ Раздел III. Математические аспекты кибернетики




Тема 7. Математическая кибернетика

4




8




Тема 8. Информация и управление

4

4

4




Итого:

36

24

48


^ 5.2. Содержание разделов (тем) дисциплины


Раздел I. Основные понятия теории информации

Тема 1. Предмет информатики, основные понятия

Предмет информатики. Информатика как наука и как вид практической деятельности. Место информатики в системе наук. Понятие информации. Роль информации в современном обществе. Виды информационных процессов. Принципы получения, хранения, обработки и использования информации.

^ Тема 2. Количественная оценка информации

Информационные меры. Количество информации и неопределенность. Энтропия как мера неопределенности. Правила определения энтропии по Шеннону и по Хартли. Основные свойства энтропии.

^ Тема 3. Помехоустойчивость и эффективность информационных систем

Понятие помехоустойчивости и эффективности. Пропускная способность канала. Принципы помехоустойчивого кодирования. Вторая теорема Шеннона. Основы теории оптимального приема. Методы приема и различение сигналов.

^ Раздел II. Математические основы информационных процессов

Тема 4. Теория кодирования.

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

^ Тема 5. Теория автоматов.

Конечные автоматы. Автоматные функции. Состояния автомата. Экви­валентность состояний. Теорема об эквивалентности состояний конечного автомата. Детерминированные функции. Задание детер­минированных функ­ций при помощи деревьев, вес функций. Огра­ниченно-детерми­ни­ро­ванные функции. Преобразование автоматными функциями перио­дических последо­вательностей. Операция суперпозиции. Автоматы Миля и Мура. Реализа­ция автоматных функций.

^ Тема 6. Теория распознавания.

Проблема распознавания. Общая характеристика задач распознавания и их типы. Математическая теория распознавания образов. Постановка задачи распознавания. Алгебраический подход к задаче распознавания. Гео­мет­рические процедуры распознавания. Комбинаторно-логические процедуры рас­поз­навания. Алгоритмы распознавания, основанные на вычислении оценок. Струк­турные методы распознавания. Распознавание и обработка изображений.

^ Раздел III. Математические аспекты кибернетики

Тема 7. Математическая кибернетика

Математические аспекты кибернетики. Авто­ма­ти­ческое регулирование. Программное управление и управление с обратной связью. Оптимальное управление.

Тема 8. Информация и управление

Методы прогнозирования. Теория при­ня­тия решений. Представление знаний в системах искусственного интеллекта.


^ 5.3. Тематическое планирование




п/п

Разделы

Лекции

Лабораторно-практические занятия




Раздел I. Основные понятия теории информации

1. Информация и информатика, их место и роль в современном обществе

2.Понятие информации. Виды информационных процессов

3.Информационные меры

4.Энтропия как мера неопределенности

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

6.Основы теории оптимального приема

1. Расчет энтропии при проведении опытов,

связанных с элементарными событиями.

2. Расчет пропускной способности линий связи.




Раздел II. Математические основы информационных процессов

1.Основы кодирования информации

2. Оптимальные коды

3. Самокорректирую -щиеся коды

4.Основные сведения о конечных автоматах

5. Автоматные функции.

6.Реализация автоматных функций

7. Общая характеристика задач распознавания и их типы.

8. Математическая теория распознавания образов.

1.Решение задач по построению кодов методом Хаффмана

2. Решение задач по построению помехоустойчивых кодов методом Хэмминга

3.Решение задач по построению автоматных функций в табличном и графическом виде.

4. Решение задач по определению меры близости методом измерения Евклидового и Чебышевского расстояний




Раздел III. Математические аспекты кибернетики

1. Математические аспекты кибернетики.

2. Оптимальное управление.

3. Теория принятия решений.

4. Представление знаний в системах искусственного интеллекта.

1.Решение оптимизационных задач методом линейного программирования средствами Excel

2. Решение задач прогнозирования средствами Excel


^ 6. Учебно-методическое обеспечение дисциплины


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


ОСНОВНАЯ

  1. Теоретические основы информатики: учебное пособие для студ. высш. учеб. заведений /В.Л. Матросов, В.А. Горелик., С.А. Жданов и др. – М.: «Академия», 2009. – 352 с. (12 экз.)

  2. Могилев, А.В. Информатика: учеб. пособие. / А.В. Могилев, Е.К. Хеннер, Н.И. Пак; под ред. А.В. Могилева. – 3-е изд. стер. – М.: «Академия», 2008. – 336 с. (Высшее профессиональное образование). (10 экз).

  3. Угринович, Н.Д. Информатика и ИКТ. Базовый уровень: учебник для 11 класса /Н.Д. Угринович – 4-е изд. – М.: БИНОМ. Лаборатория знаний. 2010. - 187 с.: ил. (9 экз).

  4. Пантюхин, П.Я. Компьютерная графика. В 2-х частях. Часть 1: Учебное пособие. – М.: ИД «ФОРУМ»: ИНФРА-М, 2008. – 88 с.: ил. +СD (1 экз)

  5. Петров, М.И. Компьютерная графика: Учебник для вузов/М.Н. Петров, В.П. Молочков – СПб.: Питер, 2004 – 811с. (20 экз)

  6. Мельников, В.П. Информационная безопасность и защита информации: учеб. пособие для студ. выс. учеб. заведений /В.П. Мельников, С.А. Клейменов, А.М. Петраков: под ред. С.А. Клейменова. – М.: «Академия», 2006. – 336 с. (10 экз).

  7. Деев, В.Н. Информатика: Учеб. пособие /под ред. И.М. Александрова. – М.: Изд-во «Дашков и Ко», 2007. – 160 с. (25 экз).

  8. Филимонова, Е.В. Математика и информатика: Учебник /Е.Н. Филимонова. – 2-е изд. – М.: Изд-во «Дашков и Ко», 2008. – 480 с. (10 экз)

  9. Стариченко, Б.Е. Теоретические основы информатики: Учебное пособие для вузов/Б.Е. Стариченко – М.: Горячая линия – Телеком, 2004 – 312с. (1 экз)


ДОПОЛНИТЕЛЬНАЯ


  1. Саак, А.Э. Информационные технологии управления: Учебник для вузов. 2-е изд. (+СD). – СПб.: Питер, 2008. – 320 с.: ил. (2 экз).

  2. Симонович С.В. Общая информатика. Новое издание. Универсальный курс – Спб.: Питер, 2007. – 428 с.: ил. (1 экз).

  3. Белоусова, Л.И. Сборник задач по курсу информатики /под ред. Л.И. Белоусовой. – М.: «Экзамен», 2007. – 253 с. (Серия «Учебно-методический комплект») (1 экз).

  4. Коваленко, А.А. Основы микроэлектроники: учеб. пособие /А.А. Коваленко и др. – М.: «Академия», 2006. – 240 с. (15 экз)

  5. Могилев, А.В. Информатика: Учебное пособие для студентов педагогических вузов/А.В. Могилев, Н.И. Пак, Е.Г. Хеннер – М.: Академия, 2000 – 816с. (51 экз)

  6. Могилев, А.В. Практикум по информатике: Учебное пособие для студентов вузов/А.В. Могилев, Н.И. Пак, Е.К. Хеннер: под ред. Е.К. Хеннера – М.: Академия, 2001 – 608с. (6 экз)

  7. Самсонов Б.Б., Плохов Е.М., Филоненков А.И., Кречет Т.В. Теория информации и кодирование. – Ростов-на-Дону, 2002. – 288 с.

  8. Кузьмин Н.Б., Кедрус В.А. Основы теории информации и кодирования.- К.: Высшая школа, 1997.


^ 6.2. Электронные издания, цифровые образовательные ресурсы


  1. Теория информации Материал из Википедии — свободной энциклопедии //http://ru.wikipedia.org/wiki/Теория_информации.

  2. Единая коллекция цифровых образовательных ресурсов. // http://school-collection.edu.ru/catalog/pupil/?subject=19.

  3. Теоретические основы информатики (электронный учебник) // http://www.tula.net/tgpu/new/New/informatic/g1.htm

  4. Российская система открытого образования. Педагогический виртуальный университет. Теоретические основы информатики (электронный учебник) // http://www.mgopu.ru/PVU/2.1/theorInformatics/

  5. Теоретические основы информатики (видео онлайн) //http://compteacher.ru/nets/481-teoreticheskie-osnovy-informatiki-video-onlayn.html

  6. Основы теории информации. (электронный учебник) //http://teo-inf1.narod.ru/index.html

  7. ГИА СИУ. Теоретические основы информатики. (электронный учебник) // http://giasiu.narod2.ru/p3aa1.html.

  8. Интернет университет информационных технологий. Основы теории информации и криптографии. В.В. Лидовский. //http://www.intuit.ru/department/calculate/infotheory/.


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


  1. Инструментальные средства, реализующие возможности Интернет и мультимедиа технологий.

  2. Системы программирования VisuaBasic for Application

  3. Электронные таблицы Excel.

  4. Электронные средства образовательного назначения, в том числе на CD-ROM.

  5. Компьютерный класс с выходом в Интернет.

  6. Электронная доска.



^ 8. Содержание текущего и итогового контроля


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

Формы контроля: контрольная работа, тесты, рефераты, защита выполненных лабораторно-практических работ.


Содержание контрольных мероприятий

Вопросы для контрольной работы и заданий для самостоятельной работы:

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

  2. Как следует понимать термины «оцифровка изображения» и «оцифровка звука»? Какими устройствами производятся данные операции?

  3. В чем состоит и как проявляется несимметричность непрерывной и дискретной форм представления информации?

  4. Какова энтропия следующих опытов:

    1. бросок монеты;

    2. бросок игральной кости;

    3. вытаскивание наугад одной игральной карты из 36;

    4. бросок двух игральных костей.

  5. Опыты а и р состоят в последовательном извлечении без возврата двух шаров из ящика, в котором изначально находились п белых шаров и т черных. Найдите, Н(α), H(β), Нα(β) и Нβ(α).

  6. Что такое «шенноновские сообщения»? Почему теория информации имеет дело именно с такими сообщениями?

  7. Одинакова ли на Ваш взгляд избыточность литературных и деловых текстов? Почему?

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

  9. Человек может осмысленно читать со скоростью 15 знаков в секунду. Оцените пропускную способность зрительного канала в данном виде деятельности.

  10. Оцените пропускную способность слухового канала радиста, принимающего сигналы азбуки Морзе, если известно, что для распознавания одного элементарного сигнала ему требуется 0,2 с.

  11. При дискретизации аналогового сообщения число градаций при квантовании равно 64, а частота развертки по времени - 200 Гц. Какой пропускной способности требуется канал связи без шумов для передачи данной информации, если используется равномерное двоичное кодирование?

  12. Почему при передаче информации предпочтение отдается равномерному коду?

  13. В чем смысловое отличие понятия «избыточность» для идеальных и реальных каналов передачи информации?

  14. Получено машинное слово, закодированное с использованием кода Хемминга: 100010111100010110011. Устраните ошибку передачи.

  15. Какие действия алгоритмической машины следует считать элементарными?

  16. Решите следующие задачи, используя алгоритмическую машину Поста; во всех задачах в исходном состоянии обозревается крайняя левая ячейка:

a) на ленте находятся два числа N и Q, разделенные одной пустой ячейкой. Напишите программу нахождения суммы N + Q.

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

c) на ленте находятся два числа N и Q (N > Q), разделенные одной пустой ячейкой. Напишите программу нахождения разности N - Q.

d) на ленте ^ N меток. Построить такое же количество меток справа от имеющихся через одну пустую.

е) на ленте находятся два числа N и Q, разделенные одной пустой ячейкой. Напишите программу нахождения произведения ^ NQ.

  1. Нормальный алгоритм имеет алфавит А = {а, b, с} и систему подстановок: асаа, aabbc, bccab. Найти результат применения алгоритма к исходным словам: (1) cbcbba; (2) abccba; (3) accca.


Темы рефератов

  1. Энтропия сообщения. Пропускная способность канала. Теоремы Шеннона.

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

  3. Схемы из функциональных элементов. Сложность схем. Синтез схем из функциональных элементов для индивидуальных функций.

  4. Контактные схемы. Простейшие методы синтеза. Контактное дерево.

  5. Модель АВО: Алгоритмы распознавания, основанные на вычислении оценок.

  6. Дескриптивный подход к распознаванию и анализу изображений.

  7. Анализ различных подходов к введению единицы измерения информации.

  8. История развития информатики как науки.

  9. Наука информатика, ее современное состояние и перспективы развития.

  10. Перспективы развития информатизации общества в России.

  11. История способов накопления, обработки и передачи информации, перспективы их развития.

  12. Понятие «алгоритма» в математике и информатике, история и современное понимание.

  13. Применение методов моделирования при решении различных задач.

  14. Объектно-ориентированные языки программирования.

  15. Проектирование и разработка программ (метод пошаговой детализации).

  16. Библиотека методов численного решения алгебраических уравнений.



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

Форма контроля – экзамен.

Содержание контрольных мероприятий

Примерный перечень вопросов к экзамену:

  1. Объект, предмет, задачи информатики.

  2. Исторические аспекты развития информатики.

  3. Место информатики в системе наук.

  4. Виды информационных процессов, протекающих в образовании.

  5. Принципы получения информации.

  6. Принципы хранения информации.

  7. Принципы обработки и использования информации.

  8. Понятие информации. Схема передачи информации.

  9. Понятие сигнала. Аналоговые и дискретные сигналы.

  10. Процесс преобразования аналогового сигнала в цифровой, основные процессы.

  11. Теорема Котельникова.

  12. Сущность энтропийного подхода к измерению количества информации.

  13. Количественная оценка информации при энтропийном подходе.

  14. Мера информации по Хартли и Шеннону.

  15. Основные свойства энтропии.

  16. Основные понятия теории кодирования.

  17. Виды кодирования. Побуквенное кодирование.

  18. Виды кодирования. Разделимые коды.

  19. Виды кодирования. Префиксные коды.

  20. Оптимальное равномерное кодирование. Префиксные коды.

  21. Оптимальное равномерное кодирование. Оптимальные коды Шеннона-Фано.

  22. Оптимальное равномерное кодирование. Код Хаффмана.

  23. Теоремы Шеннона о кодировании.

  24. Основные способы кодирования информации.

  25. Основные виды алфавитного кодирования.

  26. Системы счисления, классификация, принципы построения.

  27. Теорема Шеннона о кодировании.

  28. Префиксные коды, сущность, принципы формирования.

  29. Префиксный код Шеннона – Фано.

  30. Разновидности помехоустойчивых кодов.

  31. Понятия помехоустойчивость, производительность источника, пропускная способность канала.

  32. Основные виды помехоустойчивых кодов.

  33. Общие принципы использования избыточности.

  34. Связь корректирующей способности кода с кодовым расстоянием. Расстояние Хемминга.

  35. Коды Хемминга, правила кодирования и декодирования.

  36. Понятие автомата, принцип работы автомата.

  37. Способы задания конечных автоматов.

  38. Общие задачи теории автоматов. Формализация алгоритма.

  39. Понятие исполнителя алгоритма.

  40. Формализация понятия алгоритм.

  41. Машина Поста.

  42. Машина Тьюринга.

  43. Нормальные алгоритмы Маркова.

  44. Рекурсивные функции.

  45. Основы теории конечных автоматов.

  46. Способы задания конечных автоматов.

  47. Общие задачи теории автоматов.

  48. Автоматы Мили.

  49. Автоматы Мура.

  50. Основные понятия теории распознавания образов.

  51. Классификация систем распознавания образов.

  52. Основные положения теории распознавания.

  53. Общая характеристика задач распознавания и их типы.

  54. Основные определения. Принципы классификации и типы систем распознавания.

  55. Основные задачи, решаемые в системах распознавания образов.

  56. Модели систем распознавания образов.

  57. Математическая теория распознавания образов. Предмет и математические задачи теории распознавания образов.

  58. Математическая теория распознавания образов. Классификаторы, основанные на байесовской теории решений.

  59. Математическая теория распознавания образов. Понятие решающих функций.

  60. Предмет кибернетики.

  61. Математические аспекты кибернетики.

  62. Сущность математической кибернетики.

  63. Информация и управление. Основные понятия теории принятия решений.

  64. Информация и управление. Представление знаний в системах искусственного интеллекта.

  65. Замкнутые и разомкнутые системы управления, положительная и отрицательная обратные связи в системах управления.

  66. Моделирование рассуждений.



  1. Пусть система может находиться в одном из трех состояний, причем вероятности нахождения в первом и втором состояниях равны соответственно p1=0,3; p2=0,4; p3= 0,3. Найти энтропию системы.

  2. Пусть система может находиться в одном из четырех состояний, причем вероятности нахождения в первом, втором и третьем состояниях равны соответственно p1=0,3; p2=0,2; p3= 0,2. Найти энтропию системы.

  3. Имеются два ящика (системы), в каждом из которых находится по 8 шаров двух цветов. В первом ящике 2 зеленых шара и 6 желтых шаров, а во втором – по 4 шара каждого цвета. Из каждого ящика вытаскивают по одному шару. Что можно сказать о неопределенностях опытов?

  4. Определить избыточность языка (в процентах), состоящего из четырех символов: а, б, в, г, если вероятности их появления составляют: p1=0,3; p2=0,2; p3= 0,2, p4=0,3.

  5. В корзине лежат 10 синих, 5 зелёных, 4 жёлтых и 1 красный шаров. Сколько информации несёт сообщение о том, что из ящика случайным образом достали шар?

  6. Сережа за несколько лет учебы получил по математике 100 оценок: 60 пятерок, 30 четверок, 8 троек и 2 двойки. Допуская, что такое распределение оценок может сохраниться и в дальнейшем, вычислите вероятность получения каждой из оценок. Какое количество информации несет в себе получение оценки по математике?

  7. Осуществить кодирование методом Шеннона - Фано первичного алфавита а1 (0,3); а2 (0,2); а3 (0,2); а4 (0,15) а5 (0,1); а6 (0,05).

  8. Осуществить кодирование методом Шеннона - Фано первичного алфавита а1 (0,4); а2 (0,2); а3 (0,15); а4 (0,15) а5 (0,05); а6 (0,05).

  9. Осуществить кодирование методом Хаффмана первичного алфавита а1 (0,3); а2 (0,2); а3 (0,2); а4 (0,15) а5 (0,1); а6 (0,05).

  10. Осуществить кодирование методом Хаффмана первичного алфавита а1 (0,4); а2 (0,2); а3 (0,15); а4 (0,15) а5 (0,05); а6 (0,05).

  11. Сформировать код Хемминга (7,4) для следующих последовательностей 0010, 0101, 1101.

  12. Сформировать код Хемминга (7,4) для следующих последовательностей 0110, 1100, 1110.

  13. Определить синдромы кодовых слов Хемминга и исправить ошибки для следующих кодовых слов 0001001, 0010010, 0001100.

  14. Определить синдромы кодовых слов Хемминга и исправить ошибки для следующих кодовых слов 1001000, 1000010, 1100001.

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

  16. Составит программу для машины Поста для сложения двух целых неотрицательных чисел.

  17. Составить алгоритм машины Тьюринга, который для алфавита {а,б,в,г} заменяет букву а на букву г, а букву г на букву а.

  18. Составить алгоритм машины Тьюринга, который для алфавита {а,к,о,ф} заменяет слово «кофе» на слово «кафе».

  19. Используя нормальный алгоритм Маркова преобразовать слово 11+11+111 из алфавита {+,1}, используя следующую систему подстановок:

1+ +1

+1 1

1  1.

  1. Описать в табличной форме и форме графа работу автомата «Турникет в метро».

  2. Таблица соединений автомата имеет вид

a1 a2 a3

x1 a2/y2 a3/y3 a1/y3

x2 a1/y3 a1/y1 a2/y2

составить графический алгоритм работы автомата.

  1. Нормальный алгоритм имеет алфавит А = {а, b, с} и систему подстановок: ас → аа, aab → bc, bc → cab. Найти результат применения алгоритма к исходным словам: (1) cbcbba; (2) abccba; (3) accca.

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


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

  1. Алфавитное кодирование.

  2. Помехоустойчивые и самокорректирующиеся коды.

  3. Задачи диагностики конечных автоматов.

  4. Синтез модели эвристического алгоритма распознавания.

  5. Математическая постановка задачи распознавания изображений.

  6. Энтропия сообщения. Пропускная способность канала. Теоремы Шеннона.

  7. Схемы из функциональных элементов. Сложность схем. Синтез схем из функциональных элементов для индивидуальных функций.

  8. Контактные схемы. Простейшие методы синтеза. Контактное дерево.

  9. Модель АВО: Алгоритмы распознавания, основанные на вычислении оценок.

  10. Дескриптивный подход к распознаванию и анализу изображений.

  11. Синтез конечных автоматов.

  12. Комбинаторно-логические процедуры распознавания.

  13. Диалоговые системы оптимизации и имитации.

  14. Виды источников сообщений: дискретные и непрерывные.

  15. Свойства энтропии дискретных непрерывных, простых и сложных сообщений.

  16. Обнаружение сигналов.

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


^ III. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ ПРЕПОДАВАТЕЛЕЙ


Дисциплина основывается на знаниях студентов, полученных при изучении следующих дисциплин: ЕН.Ф.01 Математика; ДПП.Ф.01 Математическая логика, ДПП Ф.05 Теория вероятностей и математическая статистика, ДПП. Ф.05 Теоретические основы информатики, ДПП.Ф.14 Программирование, ДПП.Ф.15 Программное обеспечение ЭВМ, ДПП.Ф.16 Информационные системы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

– фундаментальную – углубление теоретической и общеобразовательной подготовки будущих учителей в области теоретической информатики;

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

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

В качестве компьютерной поддержки курса использовать инструментальную среду разработки программ VisualBasic for Application.

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

Лекции являются одним из основных методов обучения по дисциплине, которые должны решать следующие задачи:

− изложить важнейший материал программы курса, освещающий основные моменты;

− развить у студентов потребность к самостоятельной работе над учебной и научной литературой.

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

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

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

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

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

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

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

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

Варианты тестов входного контроля.

1. Информация - это

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

b) область знания, изучающая способы передачи опыта.

c) характеристика способов взаимодействия отдельных элементов компьютера.

2. Современные информационные технологии - это

  1. компьютер и его периферийные устройства.

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

  3. локальные и глобальные информационные сети.

3. Информатика - это

a) наука о компьютерных системах и информационных сетях.

b) наука о совокупности процессов получения, передачи, обработки, хранения, представления и распространения информации.

c) область знания о современных информационных технологиях.

4. Персональный компьютер - это

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

б) устройство для решения математических задач и применения в обучении.

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

5. К устройствам ввода информации относятся:

а) системный блок, мышь, клавиатура, графопостроитель, микрофон.

б) клавиатура, CD ROM, мышь, стриммер, монитор.

в) мышь, шар, сенсорный экран, микрофон.

6. Алгоритм – это

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

b) способ решения задач, предусматривающий логическое достижение желаемого результата.

c) последовательное выполнение операций, представляющие заданные действия в математической науке.

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

a) корректность и однозначность;

b) общность и многообразие;

c) наличие ввода исходных данных и эффективность.

8. Множество — это

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

b) последовательность символов, принадлежащих конечному множеству символов, или алфавиту.

c) типизированный файл.

Основное содержание лекций с указанием рекомендованной литературы приведено ниже.

Тема 1. Предмет информатики, основные понятия

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

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

Лекция 1.2. Понятие информации. Виды информационных процессов.

Информация и ее свойства. Информация и данные. Формы адекватности информации. Качество информации. Место возникновения. Стабильность. Стадия обработки. Способ отображения. Функция управления.

Тема 2. Количественная оценка информации

Лекция 2.1. Информационные меры

Меры информации. Качественные характеристики информации. Структурные меры. Статистическая мера. Семантическая мера. Синтаксическая мера. Прагматическая мера. Системы счисления

Лекция 2.2. Энтропия как мера неопределенности

Единицы измерения. Свойства энтропии. Энтропия сложного опыта. Условная энтропия. Численное измерение количества информации. Формула Хартли. Информация и алфавит. Проблема распознавания знака. Формула Шеннона.

Тема 3. Помехоустойчивость и эффективность информационных систем

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

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

Лекция 3.2. Основы теории оптимального приема

Способы передачи информации в компьютерных линиях связи. Канал параллельной передачи. Последовательная передача данных. Теорема Котельникова. Дискретизация и квантование сигнала. Приемник Котельникова.

Тема 4. Теория кодирования.

Лекция 4.1. Основы кодирования информации

Постановка задачи кодирования. Виды кодирования. Кодирование различных типов информации. Первая теорема Шеннона. Интерпретации. Абстрактный алфавит. Особенности вторичного алфавита. Способы построения двоичных кодов. Алфавитное неравномерное двоичное кодирование. Равномерное кодирование. Алфавитное кодирование. Международные системы байтового кодирования.

Лекция 4.2. Оптимальные коды

Оптимальное кодирование. Оптимальное равномерное кодирование. Префиксные коды. Оптимальные коды Шеннона-Фано. Код Хаффмана. Особенности кода Грея.

Лекция 4.3. Самокорректирующиеся коды

Разновидности помехоустойчивых кодов. Общие принципы использования избыточности. Теорема Шеннона для каналов с помехами. Связь корректирующей способности кода с кодовым расстоянием. Евклидово расстояние, Хеммингово расстояние. Блоковые и циклические коды.

Тема 5. Теория автоматов.

Лекция 5.1. Основные сведения о конечных автоматах

Понятие автомата, принцип работы автомата. Способы задания конечных автоматов. Общие задачи теории автоматов. Формализация алгоритма. Машина Поста. Машина Тьюринга.

Лекция 5.2. Автоматные функции.

Автоматные языки. Автоматная грамматика. Понятие автоматной функции. Способы задания конечных автоматов: табличный (матрицы переходов и выходов); графический (с помощью графов); аналитический (с помощью формул). Канонические уравнения. Диаграмма Мура.

Лекция 5.3. Реализация автоматных функций

Автоматы Мили и Мура. Устройства с конечной памятью. Потоковые шифраторы.

Тема 6. Теория распознавания.

Лекция 6.1. Общая характеристика задач распознавания и их типы.

Основные определения. Принципы классификации и типы систем распознавания. Системы без обучения. Обучающиеся системы. Самообучающиеся системы. Детерминированные системы. Вероятностные системы. Логические системы. Структурные (лингвистические) системы.

Лекция 6.2. Математическая теория распознавания образов.

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

Тема 7. Математическая кибернетика

Лекция 7.1. Математические аспекты кибернетики.

Сущность математической кибернетики. Предмет кибернетики. Термин «кибернетика» в современном понимании. Сфера кибернетики. Основные понятия теории множеств. Основы дискретной математики. Проверка статистических гипотез о параметрах распределения.

Лекция 7.2. Оптимальное управление.

Кибернетическая система как совокупность управляющей и управляемой частей. Задачи управления: регулирование (стабилизация); выполнение программы; слежение; оптимизация. Замкнутые и разомкнутые системы управления. Положительная и отрицательная обратные связи.

Тема 8. Информация и управление

Лекция 8.1. Теория принятия решений.

Основные понятия теории принятия решений. Роль прогнозирования при принятии решений. Методы принятия решений: простые методы принятия решений; задачи оптимизации при принятии решений; вероятностно-статистические методы принятия решений; экспертные методы принятия решений.

Лекция 8.2. Представление знаний в системах искусственного интеллекта.

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

Целями проведения лабораторно-практических работ являются:

− установление связей теории с практикой в форме экспериментального подтверждения положений теории;

− обучение студентов умению анализировать полученные результаты;

− контроль самостоятельной работы студентов по освоению курса;

− обучение навыкам профессиональной деятельности

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

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

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

Трансляторы с языков высокого уровня.

Соответствующий способ проведения занятий ориентирован на активно программирующих студентов и позволяет, наряду с отработкой навыков моделирования, углубить программистскую подготовку. Недостаток этого способа - относительно высокая трудоемкость, особенно если речь идет об оформлении диалогового интерфейса, адекватного современным требованиям, предъявляемым к прикладным программам. Этот недостаток может быть устранен, если наряду с языком (типа Паскаль) использовать современные средства визуального программирования (типа Delphi, C++).

Офисные пакеты (текстовый редактор и электронные таблицы).

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

Специальные пакеты для решения математических задач.

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

Работы рассчитаны на самостоятельное выполнение студентами, включая разработку программ, их отладку и тестирование. Выбор программного средства – по индивидуальному выбору. Наилучшее решение - использование каждым студентом в ходе реализации практикума нескольких программных средств.

Задания к лабораторно-практическим занятиям.

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

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

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

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

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

Выполнить конкретное задание из своего варианта работы.

Качественно проанализировать результаты моделирования.

Создать текстовый отчет по лабораторной работе, включающий:

− титульный лист (название работы, исполнитель, группа и т.д.);

− постановку задачи и описание задачи;

− результаты тестирования программы;

− результаты, полученные в ходе выполнения задания (в различных формах);

− качественный анализ результатов.

Содержание лабораторных работ приведено в Приложении 1.


^ IV. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ СТУДЕНТОВ


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

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

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

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

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

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

При изучении материала темы №1 «Предмет информатики, основные понятия» обратиться к литературе [1,2,3,9].

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

  1. Почему хранение информации нельзя считать информационным процессом?

  2. Основные разделы информатики.

  3. Основные задачи теоретической информатики.

  4. Что является предметом теоретической информатики.

  5. Что является материальным носителем информации?

  6. Дайте определение понятий «данные», «сообщение», «сигнал».

  7. Формы представления информации.

  8. Формы представления информации.

  9. Эволюция информационных технологий

  10. Классификация информационных систем

Задачи для самостоятельного решения

  1. Разработать обобщенную архитектуру информационной системы СГПИ.

  2. Виды информационных процессов, протекающих в образовании.

  3. Особенности хранения информации в корпоративных информационных системах.

  4. Особенности передачи информации в современных условиях

При изучении материала темы №2 «Количественная оценка информации» обратиться к литературе [1,2,3,9].

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

  1. Почему в определении энтропии как меры неопределенности выбрана логарифмическая зависимость между Н и n? Почему выбран log2 ?

  2. Вопрос имеет два варианта ответа. Возможно ли, чтобы с каждым из ответов была связано различное количество информации?

  3. Возможно ли, чтобы бинарный ответ содержал меньше 1 бита информации?

  4. Дайте объяснение тому, что количество информации на знак алфавита выражается нецелым числом.

  5. Что такое «шенноновские сообщения»? Почему теория информации имеет дело именно с такими сообщениями?

  6. Почему используется «избыточный» язык?

  7. Одинакова ли на Ваш взгляд избыточность литературных и деловых текстов? Почему?

Задачи для самостоятельного решения

  1. Какова энтропия следующих опытов:

(a) бросок монеты;

(b) бросок игральной кости;

(c) вытаскивание наугад одной игральной карты из 36;

(d) бросок двух игральных костей.

  1. Алфавит русского языка содержит 34 буквы (с пробелом), английского - 27. Если считать появление всех букв в тексте одинаковым, то как соотносятся неопределенности, связанные с угадыванием случайно выбранной буквы текста?

  2. Опыт имеет два исхода. Докажите, что энтропия такого опыта максимальна, если вероятности исходов будут обе равны 0,5.

  3. Докажите, что для двух опытов справедливо соотношение: H(α) + Нα(β) = Н(β) + Нβ(α).

  4. Опыты а и р состоят в последовательном извлечении без возврата двух шаров из ящика, в котором изначально находились п белых шаров и т черных. Найдите, Н(α), H(β), Нα(β) и Нβ(α).

  5. Мы отгадываем задуманное кем-то двузначное число.

(a) Какое количество информации требуется для отгадывания всего числа?

(b) Какова оптимальная последовательность вопросов при отгадывании? Каково их минимальное число?

(c) Изменится ли требуемое количество информации, если будем отгадывать не все число сразу, а по очереди: сначала 1-ю цифру числа, затем - 2-ю?

(d) Одинакова ли информация, необходимая для отгадывания 1-ой и 2-ой цифр?

  1. Источник порождает множество шестизнаковых сообщений, каждое из которых содержит 1 знак «*». 2 знака «%» и 3 знака «!». Какое количество информации содержится в каждом (одном) из таких сообщений?

  2. Докажите, что I(а,Р) = I(Р,а).

  3. Какое количество информации содержит каждый из ответов на вопрос, если всего их 3 и все они равновероятны? А если равновероятных ответов n?

При изучении материала темы №3 «Помехоустойчивость и эффективность информационных систем» обратиться к литературе [1,6,9].

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

  1. Структура и назначение элементов информационных систем.

  2. Критерии и показатели эффективности информационных систем.

  3. Понятие помехоустойчивости: качественная и количественная оценки.

  4. Скорость передачи информации и пропускная способность: оценка, сравнение.

  5. Практическое применение второй теоремы Шеннона.

  6. Понятие оптимальности при работе с информацией.

  7. Отношение сигнал/шум и методы его увеличения в информационных системах.

  8. Корреляция как признак различения сигналов.

  9. Сущность оптимального приемника Котельникова.

  10. Почему происходит потеря информации при ее передаче по каналу с шумом?

  11. Почему при передаче информации предпочтение отдается равномерному коду?

  12. В чем смысловое отличие понятия «избыточность» для идеальных и реальных каналов передачи информации?

Задачи для самостоятельного решения

  1. С какой тактовой частотой можно передавать стандартный ТЛФ сигнал.

  2. Определить пропускную способность бинарного канала связи. При этом с вероятностью p каждый из двоичных сигналов может перейти в противоположный сигнал.

  3. Определить пропускную способность стандартного телефонного канала.

  4. Преобразовать заданный алфавит сообщений для обеспечения максимальной скорости передачи.

  5. Измерить пропускную способность в локальной сети между учебными аудиториями главного корпуса СГПИ.

  6. Оцените пропускную способность слухового канала радиста, принимающего сигналы азбуки Морзе, если известно, что для распознавания одного элементарного сигнала ему требуется 0,2 с.

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

  8. При дискретизации аналогового сообщения число градаций при квантовании равно 64, а частота развертки по времени - 200 Гц. Какой пропускной способности требуется канал связи без шумов для передачи данной информации, если используется равномерное двоичное кодирование?

  9. Для передачи телеграфных сообщений, представленных с помощью кода Бодо, используется канал без помех с пропускной способностью 1000 бит/с. Сколько знаков первичного алфавита можно передать за 1 с по данному каналу?

  10. Определите, на какую долю снижается пропускная способность канала с шумом по сравнению с идеальным каналом при двоичном кодировании, если вероятность появления ошибки передачи составляет: (а) 0,001; (b) 0,02; (с) 0,1; (d) 0,5; (е) 0,98. Поясните полученные результаты.

  11. С помощью пакета Excel или MathCAD постройте график зависимости отношения CR/C от вероятности появления ошибки передачи р в канале с шумом.

  12. В чем смысловое отличие понятия «избыточность» для идеальных и реальных каналов передачи информации?

При изучении материала темы №4 «Теория кодирования» обратиться к литературе [1,2,3,7,9].

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

  1. В каких ситуациях код Хемминга не позволит локализовать и исправить ошибку передачи?

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

  3. Правила обработки алфавита при кодировании.

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

  5. Что такое кодирование информации в общем смысле?

  6. Что называется избыточностью кода?

  7. Приведите примеры искусственного повышения избыточности кода.

  8. В чем состоит содержание 1-й и 2-й теорем Шеннона?

  9. В чём заключается сущность помехоустойчивого кодирования?

Задачи для самостоятельного решения.

  1. Оцените число символов алфавита, кодируемого с помощью двоичных последовательностей длиной а) 4 знака; б) 8 знаков; в) 12 знаков; г) 16 знаков.

  2. С помощью кодовой таблицы ASCII декодировать следующее сообщение 01010100 01001111 00100000 01000010 01000101 00100000 01001111 01010010 00100000 01001110 01001111 01010100 00100000 01010100 01001111 00100000 01000010 01000101.

  3. Какое минимальное количество контрольных бит должно передаваться вместе с 16-ю информационными для обеспечения восстановимости информации, если вероятность искажения составляет: (а) 0,001; (b) 0,02; (с) 0,1; (d) 0,5; (е) 0,98? Какова реальная избыточность сообщения в каждом случае?

  4. Получено машинное слово, закодированное с использованием кода Хемминга: 100010111100010110011. Устраните ошибку передачи.

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

  6. Оцените, сколько времени будет передаваться текст объемом в 1 страницу в кодировке ASCII по модемной линии, если несущая частота составляет 1200 Гц и передача производится асинхронно с одним стоповым битом?

  7. 11. Алфавит источника содержит шесть сообщений,передаваемых независимо друг от друга с вероятностями: Р1 = 0,4; Р2 = 0,3; Р3 = 0,1; Р4 = 0,08; Р5 = 0,07; Р6 = 0,05. До какого предела может быть уменьшена средняя длина кодовой комбинации эффективного кода?

  8. Таблица префиксных кодов некоторых русских букв имеет вид

а л м р у ы

10 010 00 11 0110 0111

декодировать сообщение: 00100010000111010101110000110.

  1. Дешифровать данный текст, используя таблицу ASCII-кодов: 8A AE AC AF EC EE E2 A5 E0.

  2. Постройте корректирующий код для передачи двух сообщений:

    1. обнаруживающий одну ошибку;

    2. обнаруживающий и исправляющий одну ошибку;

    3. обнаруживающий две и исправляющий одну ошибку.

  3. Закодируйте целые числа от 5 до 8 кодом Хемминга (7,4), пользуясь уравнениями для проверок.

При изучении материала темы №5 «Теория автоматов» обратиться к литературе [1,2,9].

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

  1. Можно ли считать исполнителем алгоритма: (а) человека, ведущего запись текста под диктовку, (b) компьютер; (с) компьютерную программу, (d) дрессированное животное. Ответы обоснуйте.

  2. Сущность и математическая модель абстрактной теории автоматов.

  3. Способы задания абстрактных автоматов.

  4. Связь между моделями Мили и Мура.

  5. Алгоритм Ауфенкампа-Хона.

  6. Классификация конечных автоматов.

  7. Исторические аспекты развития теории конечных автоматов.

  8. Общие задачи теории автоматов.

Задачи для самостоятельного решения

  1. Решите следующие задачи, используя алгоритмическую машину Поста; во всех задачах в исходном состоянии обозревается крайняя левая ячейка:

a) на ленте находятся два числа N и Q, разделенные одной пустой ячейкой. Напишите программу нахождения суммы N + Q.

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

c) на ленте находятся два числа N и Q (N > Q), разделенные одной пустой ячейкой. Напишите программу нахождения разности N - Q.

d) на ленте N меток. Построить такое же количество меток справа от имеющихся через одну пустую.

е) на ленте находятся два числа N и Q, разделенные одной пустой ячейкой. Напишите программу нахождения произведения NQ.

  1. Решите следующие задачи, используя алгоритмическую машину Тьюринга; во всех задачах в исходном состоянии обозревается крайняя левая ячейка:

a) Сложение двух чисел в унарной системе счисления (например, 1111+11).

b) Дано слово из знаков а и b произвольной длины (например, abb - bab), причем, заранее не известно, какой знак первый (а или b). Необходимо первый знак переместить в конец слова.

c) Добавление 1 к числу в произвольной заданной системе счисления.

d) Перевод целого числа из одной системы счисления в другую.

  1. Нормальный алгоритм имеет алфавит А = {а, b, с} и систему подстановок: асаа, aabbc, bccab. Найти результат применения алгоритма к исходным словам: (1) cbcbba; (2) abccba; (3) accca.

  2. Составьте программу для сложения целых неотрицательных чисел а и и на машине Поста, когда головка находится над числом а, а число b находится правее числа а на некоторое число клеток.

  3. Составьте программу для машины Тьюринга. Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.

При изучении материала темы №6 «Теория распознавания» обратиться к литературе [4,5].

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

  1. Основные методы распознавания и их сущность.

  2. Правило Байеса и распознавание образов.

  3. Основные законы распределения случайных величин в теории распознавания образов.

  4. Алгоритм распознавания лиц.

  5. История вопроса появления технических систем автоматического распознавания и методов их создания.

  6. Терминология и отличительные особенности систем распознавания.

  7. Формулировка задач создания систем распознавания и методы их решения.

  8. Принципы классификации и типы систем распознавания.

  9. Принципы получения случайных величин на ЭВМ.

  10. Модель алгоритма распознавания объектов (явлений, процессов).

  11. История возникновения искусственных систем распознавания.

  12. Персептрон как метод распознавания образов.

  13. Признаки и обобщенные образы классов.

Задачи для самостоятельного решения

  1. Решить задачу распознавание стороной А самолетов стороны В.

  2. Модель алгоритма, реализующего классическое преобразование Хафа.

  3. Разработать модель распознавание штрих-кодов.

  4. Разработать модель системы распознавания в качестве признаков которой используются геометрические размеры объекта. Тогда модель каждого объекта, подлежащего распознаванию, будет представлять в простейшем случае три числа в соответствующем банке данных - длина, ширина, высота (м, дм, см, мм).

При изучении материала темы №7 «Математическая кибернетика» обратиться к литературе [1,2,9].

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

  1. Использование методов математического программирования в кибернетике.

  2. Использование методов теории массового обслуживания в кибернетике.

  3. Использование методов теории игр в кибернетике.

  4. Проблемы искусственного интеллекта.

  5. Понятие абстрактной кибернетической системы.

  6. Функции человека и машины в кибернетических системах.

  7. Охарактеризуйте задачи, решаемые в научном разделе «исследование операций».

  8. Что означает понятие «система»?

  9. Охарактеризуйте задачи, возникающие в системах управления.

  10. Что такое «обратная связь»? Приведите примеры обратной связи в окружающих вас управляемых системах.

  11. Достоинства и недостатки разомкнутых и замкнутых систем управления.

Задачи для самостоятельного решения

  1. Для охраны автостоянки в течение 4-х месяцев требуется m1=3, m2=5, m3=4, m4=2 человек. Перед началом работы имеется m0=2 человек. Администрация планирует в конце каждого месяца, кроме последнего, а также в начале работы корректировать число охранников на величину xk, х4 =0. На прием работника необходимо затратить - 10 у.е., на увольнение - 8 у.е., на содержание избыточного работника - 7 у.е., в случае нехватки персонала - 10 у.е. Требуется найти оптимальное значение хк изменения численности работников, при которых суммарные издержки будут минимальными.

  2. В кучке n > 1 камней. Двое игроков ходят по очереди. За один ход игроку разрешается взять от 1 до k < n камней. Выигрывает тот, кто взял последний камень. При всех k и n определить выигрышную стратегию и игрока, выигрывающего при правильной игре.

  3. Играют двое. У первого есть монеты достоинством в 2 рубля и 5 рублей. Одну из них (по своему выбору) он зажимает в кулаке, а второй игрок пытается угадать, что это за монета. Если тот угадывает, то получает монету, а если нет, то платит первому игроку m копеек. Найдите наибольшее целое m, при котором игра выгодна второму игроку.

  4. Разработать систему «Тест», позволяющую реализовать обучающую функцию тестирования.

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

При изучении материала темы №8 «Информация и управление» обратиться к литературе [1,2,9].

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

  1. История исследований и разработок систем искусственного интеллекта.

  2. Направления применения методов искусственного интеллекта.

  3. Представление знаний в системах искусственного интеллекта.

  4. Основные подходы к представлению знаний.

  5. Особенности машинного представления данных.

  6. Моделирование рассуждений.

  7. Сущность и правила построения фраз Хорна.

  8. "Наивные" модели прогнозирования.

  9. Средние и скользящие средние.

  10. Методы Хольта и Брауна.

  11. Регрессионные методы прогнозирования.

Задачи для самостоятельного решения

  1. Пусть предикат дает (Х,Y,Z) означает, что «X дает Y некоторому объекту Z», а предикат получают (X, Y) означает, что «Y получает Z». Пусть знания об этих отношениях выражаются предложениями

    1. получает(вы, сила):- дает (логика, сила, вы);

    2. дает (логика, сила, вы).

Задача, которую нужно решить, состоит в том, чтобы ответить на вопрос: получаете ли вы силу?

  1. Составить экономико-математическую модель задачи: Для выпуска изделий двух типов А и В на заводе используют сырье четырех видов (I, II, III, IV). Для изготовления изделия А необходимо: 2 ед. сырья первого вида, 1 ед. второго вида, 2 ед. третьего вида и 1 ед. четвертого вида. Для изготовления изделия В требуется: 3 ед. сырья первого вида, 1 ед. второго вида, 1 ед. третьего вида. Запасы сырья составляют: I вида – 21 ед., II вида – 8 ед., III вида – 12 ед., IV вида – 5 ед. Выпуск одного изделия типа А приносит 3 УДЕ прибыли, а одного изделия типа В – 2 УДЕ. Составить план производства, обеспечивающий наибольшую прибыль.

  2. На приобретение оборудования для нового производственного участка общей площадью 375 м2 предприятие обладает необходимым количеством денежных средств. Предприятие может заказать оборудование двух видов: машины первого типа стоимостью 10000 руб., требующие производительную площадь 6 м2 (с учетом проходов), производящие 4000 единиц продукции за смену, и машины второго типа стоимостью 20000 руб., занимающие 10 м2 площади, производящие 5000 единиц продукции за смену. Общая производительность данного производственного участка должна быть не менее 221000 единиц продукции за смену. Построить модель задачи при условии, что оптимальным для предприятия вариантом приобретения оборудования считается тот, который обеспечивает наименьшие общие затраты.

  3. Фирма имеет возможность рекламировать свою продукцию, используя для этого телевидение, радио и газеты. Затраты на рекламу в бюджете фирмы ограничены суммой 8000 руб. в месяц. Опыт прошлых лет показал, что 1 руб., потраченный на телерекламу, дает фирме прибыль в размере 10 руб., а потраченная на рекламу по радио и в газетах – соответственно 4 и 8 руб.



Специальность:

шифр "Название ".






оставить комментарий
страница1/2
Дата04.03.2012
Размер0.63 Mb.
ТипУчебно-методический комплекс, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2
средне
  1
отлично
  2
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх