Формуляр для описания модуля по дисциплине «Информатика»

Название модуля и шифр	Прикладная информатика Inf 1105
Ответственный за модуль	Оспанов Н. М. ,к. ф.-м.н., старший преподаватель кафедры
Тип модуля	общие обязательные
Уровень модуля	BA
Количество часов в неделю	4,5
Количество кредитов	3
Форма обучения	очная
Семестр	1,2
Количество обучающихся	25
Пререквизиты модуля	Знания по данной дисциплине необходимы в дальнейшем при изучении дисциплин по специальности и при выполнении курсовых расчетов.
Содержание модуля	Эффективное освоение этих знаний возможно при условии достаточно глубокого погружения в предметную область: в текстовом процессоре– создание макросов с помощью макрорекордера; электронных таблицах– работа с большими таблицами, создание собственных функций, статистическая обработка данных, решение оптимизационных задач, разработка имитационных моделей, создание баз данных, макросов и др.; электронных таблицах и системах управления базами данных создание пользовательских форм, процедур обработки данных, интеллектуальных отчетов (с элементами обработки), и др. с использованием средств VisualBasicApplication; в системах управления базами данных – работа с моделями DAO(DataAccessObjects– Объекты доступа к данным) иADO(ActiveXDataObjects- Объекты данныхActiveX); в программах работы с электронной почтой – создание процедур автоматизации работы с электронной почтой и планирование индивидуальной деятельности с использованием средств VisualbasicApplication; в средствах работы с аудио- и видеоинформацией - ввод и обработка данных с видеомагнитофона и видеокамеры, оцифровка изображений.
Результаты обучения	В результате обучения студенты владеют прикладными программами в областях, связанных с профессиональной деятельностью.
Форма итогового контроля	Экзамен
Условия для получения кредитов	Выполнение всех видов работ, предусмотренных модулем Положительная оценка за экзамен
Продолжительность модуля	1 семестр
Литература	Вебб Дж. Программирование в Excel2003. - М.: Бином, 2005. - 304c. Карлберг К. Бизнес-анализ с помощью Excel. Киев:Диалектика, 2004.- 546 с. Фрай К., Фриз В., Бакенгем Ф. Программирование в OfficeExcel2003. СПб.: Питер, 2005. - 544c. Каталано Ф., Смит Б. Internet-маркетинг. – СПб.: Диалог, 2005. - 304 с. Хелворсон М. и др. Эффект работы с Microsoft Office 2000. Шафрин Ю.А. Информационные технологии ч.1. основы информ.
Дата обновления

Разработаны презентации на темы:

1.Введение в программирование

2.Алгоритм

3.Логические элементы

4.Основы логики

5.Графы

6.Основы графов

7.База Данных,

8.Этапы решения задач

9.Основы WEB-дизайна

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ЛАБОРАТОРНЫМ РАБОТАМ

Тема 1. Информатика и информационные технологии.

1.1. Введение

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

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

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

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

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

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

аппаратное обеспечение средств вычислительной техники;

программное обеспечение средств вычислительной техники;

средства взаимодействия аппаратного и программного обеспечения;

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

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

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

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

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

В информатике все жестко ориентировано на эффективность. Вопрос, как сделать ту или иную операцию, для информатики является важным, но не основным. Основным же является вопрос, как сделать данную операцию эффективно.

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

Сигнал (от латинского signum — знак) представляет собой любой процесс, несущий информацию.

Сообщение — это информация, представленная в определенной форме и предназначенная для передачи.

Данные — это информация, представленная в формализованном виде и предназначенная для обработки ее техническими средствами, например, ЭВМ.

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

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

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

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

Информационные системы - раздел информатики, связанный с решением вопросов по анализу потоков информации в различных сложных системах, их оптимизации, структурировании, принципах хранения и поиска информации. Информационно-справочные системы, информационно-поисковые системы, гигантские современные глобальные системы хранения и поиска информации (включая широко известный Internet) в последнее десятилетие XX века привлекают внимание все большего круга пользователей. Без теоретического обоснования принципиальных решений в океане информации можно просто захлебнуться. Известным примером решения проблемы на глобальном уровне может служить гипертекстовая поисковая система WWW, а на значительно более низком уровне - справочная система, к услугам которой мы прибегаем, набрав телефонный номер 09'.

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

1.2. Информатика как единство науки и технологии

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

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

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

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

АСУ - автоматизированные системы управления; Например, в образовании используются системы АСУ-ВУЗ.

АСУТП - автоматизированные системы управления технологическими процессами. Например, такая система управляет работой станка с числовым программным управлением (ЧПУ), процессом запуска космического аппарата и т.д.

АСНИ - автоматизированная система научных исследований;

АОС - автоматизированная обучающая система;

САПР-система автоматизированного проектирования

1.3 Системы счисления

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

A_nA_n-1A_n-2 … A₁,A₀,A_-1,A_-2 =

А_nВⁿ + A_n-1B^n-1 + ... + A₁B¹ + А₀В⁰ + A_-1B^-1 + А_-2В^-2 + ...

(знак «точка» отделяет целую часть числа от дробной; знак «звездочка» здесь и ниже используется для обозначения операции умножения). Таким образом, значение каждого знака в числе зависит от позиции, которую занимает знак в записи числа. Именно поэтому такие системы счисления называют позиционными.

23,43(₁₀) = 2*10¹ + З*10° + 4*10^-1 + З*10^-2

692(₁₀) = 6* 10² + 9*10¹ + 2.

1101(₂)= 1*2³ + 1*2²+0*2¹+ 1*2°;

112(₃) = l*3²+ 1*3¹ +2*3°;

341,5(₈) =3*8²+ 4*8¹ +1*8° +5*8^-1;

A1F4(₁₆) = A*16² + 1*16¹ + F*16° + 4*16^-1.

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

Отметим, что кроме рассмотренных выше позиционных систем счисления существуют такие, в которых значение знака не зависит от того места, которое он занимает в числе. Такие системы счисления называются непозиционными. Наиболее известным примером непозиционной системы является римская. В этой системе используется 7 знаков (I, V, X, L, С, D, М), которые соответствуют следующим величинам:

1(1) V(5) X(10) L(50) С (100) D(500) M(1000)

Примеры: III (три), LIX (пятьдесят девять), DLV (пятьсот пятьдесят пять).

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

Таблицы сложения в других системах счисления.

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

Сложение в восьмеричной системе

                

Сложение в шестнадцатеричной системе

ПРАВИЛО При сложении цифры суммируются по разрядам, и если при этом возникает избыток, то он переносится влево.

Тесты к теме

1.Определение информации по Е.К. Балапанову:

А) Информация - достоверные, полные, ясные сведения об окружающем нас мире.

B) Информация - сведения о ком-то или о чем-то, представленные в форме знаков и сигналов.

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

D)Информация - сведения об окружающем нас мире представленная в виде текста, рисунка, звука.

E)Информация - тексты, рисунки, фотографии, электрические сигналы.

2. Информатика изучает-

1. Законы и методы переработки и накопления информации

2. Методы обработки информации

3. Механическую и физическую формы движения

4. Правила использования игровых программ

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

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

информация:

1. Слов, числа, рисунки, а также программы, управляющие работой компьютеров.

2. Только числа управляющие работой компьютеров.

3. Символы, рисунки

4. Кибернетика изучает:

1. Законы развития рисунки, а также программы, управляющие работой компьютеров.

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

1. общественных отношений

2. Законы получения, хранения, передачи информации в сложных управляющих системах

3. Физические законы

4. Экономические законы

5. Законы механики

5. Система счисления – это:

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

B) Представление чисел с постоянными положением запятой.

С) подстановка чисел вместо букв.

Д) Представление чисел в экспоненциальной форме.

Е) способ перестановки чисел.

6. Информацию, отражающею истинное положение дел, называются:

1. актуальной

2. понятной

3. достоверной

4. полной

5. объективной

7. Информатика – это наука о:

1. методах сбора, обработки, хранения информации.

2. навигации в «океане» информации.

3. применении компьютера в учебном процессе.

4. сортировке данных

5. расположении информации на технических носителях.

8.В чем не измеряется информация ?

1. в битах

2. в килобайтах

3. в байтах

4. в мегабайтах

5. в мегагерцах

9 Какой раздел информатики разрабатывает общие принципы построения

вычислительных систем?

.

A) Вычислительная техника.

B) Искусственный интеллект.

C) Программирование.

D) Системы проектирования.

E) Экспертные системы.

10Лицензионное програмное обеспечение защищенно:

1. Физическим лицом создавшим данное програмное обеспечение:

2. Частным

3. в килобайтах

4. в мегагерцах

5. в мегабайта

11. Программы, управляющие работой компьютера называют

1. Software

2. Hardware

3. RAM ( Random Access Memory )

4. ROM (Read Only Memory)

5. CD-ROM

Тема 2. Операции с числами двоичной системы.Структура современной информатики. Системы счисления

2.1.Информация, ее виды и свойства

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

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

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

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

По способу передачи и восприятия различают информацию:

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

Аудиальную – передается звуками;

Тактильную – передается ощцщениями;

Органо-лептическую – передается запахами и вкусом;

Машинную – передается средствами ВТ.

Человеку свойственно субъективное восприятие информации через некоторый набор ее свойств: важность, достоверность, своевременность, доступность и т.д. В этом смысле одно и то же сообщение, передаваемое от источника к получателю, может передавать информацию в разной степени. Так, например, вы хотите сообщить о неисправности компьютера. Для инженера из группы технического обслуживания сообщение «компьютер сломался» явно содержит больше информации, чем для вахтера. Но, в свою очередь, для инженера сообщение «не включается дисплей» содержит информации больше, чем первое. Как видно, одно и то же сообщение для различных пользователей несет различную информацию.

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

2. 2Непрерывная и дискретная информация

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

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

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

Единицы количества информации

Определить понятие «количество информации» довольно сложно. В решении этой проблемы существуют два основных подхода. Исторически они возникли почти одновременно, конце 40-х годов XX века. Работы Джон фон Неймана по созданию ЭВМ привели к объемному подходу измерения количества информации, а один из основоположников кибернетики американский математик Клод Шеннон развил вероятностный подход к измерению количества информации.

Объемный подход

В двоичной системе счисления знаки 0 и 1 будем называть битами (от английского выражения Binary digits - двоичные цифры). Отметим, что создатели компьютеров отдают предпочтение именно двоичной системе счисления потому, что в техническом устройстве наиболее просто реализовать два противоположных физических состояния: некоторый физический элемент, имеющий два различных состояния: намагниченность в двух противоположных направлениях; прибор, пропускающий или нет электрический ток; конденсатор, заряженный или незаряженный и т.п. В компьютере бит является наименьшей возможной единицей информации. Объем информации, записанной двоичными знаками в памяти компьютера или на внешнем носителе информации подсчитывается просто по количеству требуемых для такой записи двоичных символов. При этом, в частности, невозможно нецелое число битов (в отличие от вероятностного подхода).

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

2.3 Кодирование информации

Абстрактный алфавит

Информация передается в виде сообщений. Дискретная информация записывается с помощью некоторого конечного набора знаков, которые будем называть буквами, не вкладывая в это слово привычного ограниченного значения (типа «русские буквы» или «латинские буквы»). Буква в данном расширенном понимании - любой из знаков, которые некоторым соглашением установлены для общения. Например, при привычной передаче сообщений на русском языке такими знаками будут русские буквы - прописные и строчные, знаки препинания, пробел; если в тексте есть числа - то и цифры. Вообще, буквой будем называть элемент некоторого конечного множества (набора) отличных друг от друга знаков. Множество знаков, в котором определен их порядок, назовем алфавитом (общеизвестен порядок знаков в русском алфавите: А, Б,..., Я).

Рассмотрим некоторые примеры алфавитов.

1, Алфавит прописных русских букв:

А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

2. Алфавит Морзе:

3. Алфавит клавиатурных символов ПЭВМ IBM (русифицированная клавиатура):

5. Алфавит арабских цифр:

0123456789

6. Алфавит шестнадцатиричных цифр:

0123456789ABCDEF

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

7. Алфавит двоичных цифр:0 1

Алфавит 7 является одним из примеров, так называемых, «двоичных» алфавитов, т.е. алфавитов, состоящих из двух знаков. Другими примерами являются двоичные алфавиты 8 и 9:

8. Двоичный алфавит «точка, «тире»:. _

9. Двоичный алфавит «плюс», «минус»: + -

10. Алфавит прописных латинских букв:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

11. Алфавит римской системы счисления:

I V Х L С D М

12. Алфавит языка блок-схем изображения алгоритмов:

КОДОВАЯ ТАБЛИЦА – это внутреннее представление символов клавиатуры. Во всем мире используют таблицу ASC II (Аmerican Standart Code for Iformation, Interchange). Для хранения 2-чного кода одного символа выделен 1 байт = 8 бит. Учитывая, что 1 бит = 0 или 1, то количество разных сочетаний в 1 байте = 2⁸ = 256. Следовательно, с помощью 1 байта можно получить 256 различных двоичных комбинаций – символов, которые составляют таблицу ASC II.

Для сокращения записи используют 16-чную систему, состоящую из 16 символов: 10 цифр + A, B, C, D, E, F. Каждый символ в таблице ASC II кодируется с помощью 8 2-чных или двух 16-чных (1 разряд = 4 бит) чисел. Стандарт ASC II определяет первые 128 символов: цифры, буквы лат. алфавита (0-127). 2-я половина (128-255) – национальные символы, псевдографику и математические  символы. 

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

Примеры кодовых таблиц:

КОИ-7, КОИ-8 – кодирование русских букв и символов (семи-, восьми -битное кодирование)

1) #154 неразрывный пробел.

Рис.1 Кодировка КОИ8-Р

ASCII –American Standard Code for Information Interchange (американский стандарт кодов для обмена информацией) – это восьмиразрядная кодовая таблица, в ней закодировано 256 символов (127- стандартные коды символов английского языка, спецсимволы, цифры, а коды от 128 до 255 – национальный стандарт, алфавит языка, символы псевдографики, научные символы, коды от 0 до 32 отведены не символам, а функциональным клавишам).

1) #32 - пробел.

Рис. 2 Международная кодировка ASCII

Unicode – стандарт, согласно которому для представления каждого символа используется 2 байта. (можно кодировать математические символы, русские, английские, греческие, и даже китайские). C его помощью можно закодировать не 256, а 65536 различных символов. Полная спецификация стандарта Unicode включает в себя все существующие, вымершие и искусственно созданные алфавиты мира, а также множество математических, музыкальных, химических и прочих символов

СР1251 - наиболее распространенной в настоящее время является кодировка Microsoft Windows, ("CP" означает "Code Page", "кодовая страница").

1) #160 неразрывный пробел,

2)  #173 мягкий перенос.

Рис. 3 Кодировка CP1251

СР866 - кодировка под MS DOS

1) #255 неразрывный пробел.

Рис. 4 Кодировка СР866

Мас – кодировка в ПК фирмы Apple, работающих под управлением операционной системы Mac OS.

#202 неразрывный пробел.

Рис. 5 Кодировка Mac

ISO 8859-5 -Международная организация по стандартизации (International Standards Organization, ISO) утвердила в качестве стандарта для русского языка еще одну кодировку.

 1) Коды 128-159 не используются;

2)  #160 неразрывный пробел,

3)  #173 мягкий перенос.

Тесты к теме

1. Укажите, что из перечисленного является "мозгом" компьютера?

A.Процессор.

B .CD-R

C.Монитор.

D.Клавиатура..

E .Оперативная память.

2.В чем не измеряется информация ?

A.в битах

B.в килобайтах

C.в байтах

D.в мегабайтах

E.в мегагерцах

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

информация:

1. Слов, числа, рисунки, а также программы, управляющие работой компьютеров.

2. Только числа управляющие работой компьютеров.

3. Символы, рисунки

4. Только рисунки, а также программы, управляющие работой компьютеров.

5. Слов, числа, рисунки, а также программы, управляющие работой монитора.

4. Информатика – это наука о:

A.методах сбора, обработки, хранения информации.

B.навигации в «океане» информации.

C.применении компьютера в учебном процессе.

D.сортировке данных

E.расположении информации на технических носителях.

5.В чем не измеряется информация ?

A.в битах

B.в килобайтах

C.в байтах

D.в мегабайтах

E.в мегагерцах

6.Лицензионное програмное обеспечение защищенно:

A.Физическим лицом создавшим данное програмное обеспечение:

B.Частным

C.в килобайтах

D.в мегагерцах

E.в мегабайта

7.Принцип хранимой памяти-это:

A.Во время исполнения программа хранится в оперативной памяти вместе с данными

B.Во время исполнения программа хранится в оперативной памяти

C.Во время исполнения программы данные хранятся в оперативной памяти

D.Адресуемость памяти ЭВМ и хранение данных на диске

E.Адресуемость памяти ЭВМ

8.Уровень програмного обеспечения, который обеспечивает непосредственное

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

A.Прикладной

B.Основной

C.Служебный

D.Системный

E.Базовый

9. Информацию, отражающею истинное положение дел, называются:

1. актуальной

2. понятной

3. достоверной

4. полной

5. объективной

10. Информатика — это:

A) Наука, изучающая структуру и общие свойства информации и

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

B) Совокупность Аппаратных и программных средств вычислительной техники.

C) Обрабатываемые компьютером данные.

D) Совокупность средств вычислительной техники.

Е) Программное обеспечение компьютеров

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

3.1. Множество. Алгебра множеств

Введем обозначения.

R – множество действительных чисел.

X e R – элемент X принадлежит множеству R.

Равные множества – множества, состоящие из одинаковых элементов.

A = B – множество А равно множеству B.

0 – пустое множество.

A<= C – Множество А является подмножеством множества С.

Если А не равно С и А <= C, то А < С. (строго).

Если A <= C и C <= А, то А = С.

Пустое множество 0 является подмножеством любого множества.

Существуют конечные и бесконечные множества. Пусть n – число элементов данного множества А. Это число называется мощностью данного множества.

У множества рациональных чисел мощность является счетной (т.е. все элементы можно пронумеровать).

У множества иррациональных чисел мощность – континиум. Обозначается (С).

Основное правило комбинаторики (показано на примере)

Пусть имеется палочка, разделенная на 3 части. Первую ее часть можно раскрасить n способами, вторую – m, третью – k. Всего способов раскраски палочки – n*m*k.

Аналогично с множествами U = {a1,a2… an-1, an}

Пусть U = {a1, a2, a3} Выпишем множество всех подмножеств множества U.

P(U) = {0, a1, a2, a3, a1a2, a1a3, a2a3, a1a2a3}. Мощность множества U равна 3, а мощность P(U) равна 8.

Методом математической индукции доказывается, что при произвольной мощности n множества U, мощность множества P(U) равна 2n.

Операции над множествами

1. Объединение множеств (A U B). Элемент, принадлежащий полученному множеству, принадлежит множеству А ИЛИ множеству В.

2. Пересечение множеств (A n B). Элемент, принадлежащий полученному множеству, принадлежит множеству А И множеству В.

3. Дополнение множества А. (С = А ) – не А. Все элементы, принадлежащие универсальному множеству, не принадлежат множеству А.

Свойства операций над множествами.

1. A U B = B U A – коммутативность. A n B = B n A

2. (A U B) U C = A U (B U C), A n (B n C) = (A n B) n C – ассоциативность.

3. (A U B) n C = (A n C) u (B n C), (AnB) U C = (A U C) n (B U C) – дистрибутивность.

4. Поглощение A U A = A, A n A = A.

5. Существование универсальных границ. А U 0 = A A n 0 = 0 A u U = U A n U = A

6. Двойное дополнение A = A

7. A U A = U A n A = 0

8. Законы двойственности или закон Де – Моргана (AUB) = A n B (AnB) = A U B

3.2. Теория булевых функций. Булева алгебра.

Определение. Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (аксиомы булевой алгебры). Названия операций пока не введены.

1. X & Y = Y&X, X V Y = Y V X – коммутативность.

2. (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.

3. (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.

4. Поглощение – X & X = X, X V X = X.

5. Свойства констант X & 0 = 0 X & I = X, где I – аналог универсального множества.

6. Инвальтивность (X*)* = X

7. Дополнимость X V X* = I, X & X* = 0.

8. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Булева алгебра всех подмножеств данного множества.

U = {a1, a2… an) [U] = N [P(U)] = 2n

Легко показать, что свойства операций над множествами совпадают со свойствами (аксиомами) булевой алгебры. То есть, множество P(U) с операциями объединения, пересечения и дополнения является булевой алгеброй.

Oбъединение эквивалентно V, пересечение - &, дополнение - *, пустое множество – 0, а универсальное – I.

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

Булева алгебра характеристических векторов.

Пусть A <= U, A <- P(U) ? - характеристический вектор этого подмножества.

?A = {?1, ?2 ..?n) n = [P(U)]

?i = 1, если ai <- A (принадлежит).

?i = 0, если ai не принадлежит A.

U = {1 2 3 4 5 6 7 8 9} A = {2 4 6 8} B = {1 2 7}

?A = {0 1 0 1 0 1 0 1 0} ?B = {1 1 0 0 0 0 1 0 0} или

?A = 010101010 – скобки не нужны ?A= 110000100

Характеристические векторы размерностью n называются булевыми векторами. Они располагаются в вершинах n – мерного булева куба. Номером булевого вектора является число в двоичном представлении, которым он является

1101 – номер.

Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (если они отличаются только одной координатой). Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.

0 – нулевой вектор. I – вектор из одних единиц.

|XY |X&Y |X V Y |

|00 |0 |0 |

|01 |0 |1 |

|10 |0 |1 |

|11 |1 |1 |

Отрицание X = 0 Y = 0 Х = 1 Y= 1

Для размерности n операции над векторами производятся по координатно. Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.

Утверждение Между множеством всех подмножеств множества U и булевым кубом Bn, где n= =[U] можно становить взаимное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный.

Следствие Множество всех характеристических векторов является булевой алгеброй.

Булева алгебра высказываний (алгебра логики)

Высказыванием об элементах множества U называется любое утверждение об элементах множества U, которое для каждого элемента либо истинно, либо ложно.

U = {1 2 3 4 5 6 7 8 9}

A = «число четное» B = «число, меньшее пяти»

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

SA = {2 4 6 8} SB = {1 2 3 4}

Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным.

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

3.3. Операции над высказываниями

Дизъюнкция высказываний (V, ИЛИ, OR). Дизъюнкция высказываний – высказывание, истинное тогда, когда истинно хотя бы одно из высказываний.

Конъюнкция высказываний (&, И, AND). Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания.

Отрицание высказываний (- над буквой, НЕ, NOT). Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.

|A B |A & B A V B |Not A |

|Л Л |Л |Л |И |

|Л И |Л |И И |

|И Л |Л |И |Л |

|И И |И |И |Л |

Л – ложно.

И – истинно.

Утверждение (основа всей алгебры логики) Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует

операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения.

Следствие. Множество классов эквивалентных высказываний является булевой алгеброй.

Теорема Существуют 3 булевых алгебры: 1. P(U) 2. Bn 3. Множество классов эквивалентных высказываний. Три булевых алгебры являются изоморфными, если между их элементами можно установить такое однозначное соответствие, при котором операции сохраняются.

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

Тесты к теме

1. Логический элемент «И» выполняет:

А) Логические умножение.

B) Сложение.

С) Деление.

Д) Вычитание.

Е) Сравнение.

2.Какая из операций является отрицанием?

A) NOT.

B) OR.

C) AND.

D) DIV.

E) MOD.

3.По стадии обработки информация подразделяется на:

А) первичную, вторичную, промежуточную и результатную

B) текстовую и графическую

С) Входную , выходную, внутреннюю и внешнюю.

Д) плановую, нормативно-справочную, учетную и оперативную.

Е) переменную и постоянную.

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

А) Логические

B) Динамические

С) Статистические

Д) Текстовые

Е) Математические

5. Информацию, независящую от личного мнения или суждения, можно назвать:

А) достоверной

B) актуальной

С) объективной

Д) полезной

Е) понятной.

6. Книга, дискета, жесткие диски служат для:

А) хранение информации.

B) создания информации.

С) передачи информации.

Д) сбора информации.

Е) обработки информации

7.Законы и методы переработки и накопления информации изучает:

А) информатика.

B) логика

С) кибернетика

Д) статистика Е) динамика

8. Что означает требование определенности (детерминированности) алгоритма?

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

2. Алгоритм не должен содержать скрытых ошибок

3. Действия алгоритма могут быть определены неоднозначно

4. Алгоритм пригоден для решения любого класса задач

5. Результат не должен быть получен за заданное число шагов

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

A.Слов, числа, рисунки, а также программы, управляющие работой компьютеров.

B.Только числа управляющие работой компьютеров.

C.Символы, рисунки

D.Только рисунки, а также программы, управляющие работой компьютеров.

E.Слов, числа, рисунки, а также программы, управляющие работой монитора.

10. Кибернетика изучает:

A.Законы получения, хранения, передачи информации в сложных управляющих системах

B.Законы развития общественных отношений

C. Физические законы

D. Экономические законы

E.Законы механики

Тема 4. Основы дискретной математики

4.1. Понятие графа

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

В математике определение графа дается так:

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

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

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

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

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

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)

Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)

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

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

2. Степени вершин и подсчет числа ребер.

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

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

рис.5

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А. На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

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

Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

Доказательство:

Эта закономерность очевидна уже после рассмотрения любого полного графа. Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n—1 ребро, что и требовалось доказать.

Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива не только для полного, но и для любого графа.

Доказательство:

Действительно, каждое ребро графа связывает две вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число ребер 2R (R — число ребер графа), т. к. каждое ребро было подсчитано дважды, что и требовалось доказать.

ТЕОРЕМА. Число нечетных вершин любого графа четно.

Доказательство:

Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как K1 + 2К2 + ЗК3 + ...+ nКn. С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1) Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + ...):K1 + 2К2 + ЗК3 +К4 + 5К5 + ... + nК = 2R, (К1 + К3 + К5 +...) + (2K2 + 2Х3 +4K4 + 4К5 + ...)=2R Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число. Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2

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

3. Эйлеровы графы.

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6)

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 3 (вытекает из рассмотренной нами теоремы). Невозможно начертить граф с нечетным числом нечетных вершин. Закономерность 4. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. Закономерность 5. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».

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

рис.6 (Эйлеровы графы)

4. Связные графы

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

Граф называется несвязным, если это условие не выполняется.

рис.7рис.8

На рисунке 7, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным. (рис.8) Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом. Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа. (рис.8)

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

ТЕОРЕМА. Граф является эйлеровым тогда и только тогда, когда он связен и имеет не более двух нечетных вершин.

Доказательство:

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

Деревья

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

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

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а). В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

такая последовательность ребер, по которой можно проложить маршрут между этими вершинами.

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

рис.9а;б

Висячей вершиной называется вершина, из которой выходит ровно одно ребро. (рис.10)

рис.10 (кружком обведены висячие вершины)

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

Свойство 2. Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

Доказательство:

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

*Дерево – это граф, в котором две любые вершины соединены ровно одним простым путём.

ЛЕММА (о висячей вершине) В каждом дереве есть висячая вершина.

Доказательство:

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

ТЕОРЕМА. В дереве число вершин на одну больше числа ребер.

Доказательство:

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

4.2. Изоморфизм. Плоские графы и теорема Эйлера.

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

Докажем, что графы изображенные на рисунке 11 изоморфны.

рис.11

Пронумеруем вершины первого и второго графов от 1и до 4.(рис.12)

рис.12

В первом графе соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4; заметим, что во втором графе также соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4, следовательно, данные графы изоморфны.

Для того, чтобы выяснить, изоморфны ли два графа, нужно убедиться в том, что у них:

одинаковое количество вершин

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

ТЕОРЕМА Эйлера. Для правильно нарисованного связного плоского графа имеет равенство: V-E+F=2, где V – число вершин, E - число рёбер, F – число кусков. (равенство V-E+F=2 обычно называют формулой Эйлера)

Доказательство:

Будем удалять рёбра графа до тех пор, пока не получим дерево. Посмотрим, как при удалении очередного ребра изменяются величины V, E и F. Ясно, что число вершин не изменяется, а количество рёбер уменьшается на один. Число кусков также уменьшается на один, так как при удалении ребра два примыкающих к нему куска сливаются в один. Поэтому V-E+F при такой операции не изменяется. Так как для полученного дерева V-E=1 и F=1, то V-E+F=2 и, следовательно, для исходного графа также выполняется это равенство. Значит, теорема доказана.

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

ТЕОРЕМА Понтрягина – Куратовского: Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами. (В основном используется старинных задач о домах и колодцах, суть которой сводится к выяснению вопроса — является ли рассматриваемый граф плоским или нет, рис.13)

рис.13

4.3. Ориентированные графы

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

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

рис.14

Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие: Ст.вх.А=2, Ст.вых.А=1 Ст.вх.В=2, Ст.вых.В=0 Ст.вх.Д=1, Ст.вых.Д=3

Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер

A1A2, A2A3, ..., Аn-1Аn в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз. На ниже приведенном рисунке показаны примеры путей в ориентированном графе. Причем, первые два пути— простые — ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым, т. к. через вершину Г путь «проходил» дважды. (рис.15) рис.15 Ориентированным циклом называется замкнутый путь в ориентированном графе. На предыдущем рисунке приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.

рис.16

Так, на рисунке 16 пути от А к Д могут быть различны и иметь различную длину. Первый путь имеет длину 2, второй - 3, а третий — 4.

Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними.

Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.

рис.17

Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным (обозначают значком бесконечности). Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞

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

Тесты к теме

1. Логический элемент «И» выполняет:

А) Логические умножение.

B) Сложение.

С) Деление.

Д) Вычитание.

Е) Сравнение.

2. Законы и методы переработки и накопления информации изучает:

А) информатика.

B) логика

С) кибернетика

Д) статистика Е) динамика

3. Книга, дискета, жесткие диски служат для:

А) хранение информации.

B) создания информации.

С) передачи информации.

Д) сбора информации.

Е) обработки информации.

4. Информацию, независящую от личного мнения или суждения, можно назвать:

А) достоверной

B) актуальной

С) объективной

Д) полезной

Е) понятной.

5. Какая из операций является отрицанием?

A) NOT.

B) OR.

C) AND.

D) DIV.

E) MOD.

6. Наиболее сложные задачи управления и принятия решений решают:

А) Операционные системы.

B) Системы искусственного интеллекта.

С) Системы бухгалтерского расчета.

Д) Сетевые технологии

Е) Экономические и пакеты

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

А) Логические

B) Динамические

С) Статистические

Д) Текстовые

Е) Математические

8.По стадии обработки информация подразделяется на:

А) первичную, вторичную, промежуточную и результатную

B) текстовую и графическую

С) Входную , выходную, внутреннюю и внешнюю.

Д) плановую, нормативно-справочную, учетную и оперативную.

Е) переменную и постоянную.

9. 1 Мбайт информации – это:

А) 1024 Кбайта

B) 1024 байта

С) 1 млн байтов

Д) 1000 Кбайта

Е) 1 млрд бит.

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

А) Вычислительная техника

B) прграммирование

С) системы проектирования

Д) экспертные системы

Е) искусственный интеллект.

11. Под обменом информацией понимается:

A.Перемещение её из одного накопителя в другой.

B. Её прием или передача.

C.Перевод её на машинный язык.

D.Перемещение из внешней памяти во внутреннюю.

E.Кодирование информации.

Тема 5. Логические элементы компьютера

5.1.Логические операции. Логические формулы.

Определение

LOGOS (греч.) - слово, понятие, рассуждение, разум.

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

Основными формами абстрактного мышления являются: понятия, суждения, умозаключения.

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

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

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

Логика (формальная) - наука о законах и формах правильного мышления.

Математическая логика - изучает логические связи и отношения, лежащие в основе логического (дедуктивного) вывода.

Этапы развития логики

I. АРИСТОТЕЛЬ (384-322 гг. до н.э., древнегреческий философ) - основоположник логики.

Написал книги «Категории», «Первая аналитика», «Вторая аналитика».

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

Например:

1. Все млекопитающие имеют скелет. Все киты - млекопитающие. Следовательно, все киты имеют скелет.

2. Все квадраты - ромбы. Все ромбы - параллелограммы. Следовательно, все квадраты - параллелограммы.

Аристотель выделил все правильные формы силлогизмов, которые можно составить из рассуждений вида: «Все А суть В»; «Некоторые А суть В»; «Все А не суть В»; «Некоторые А не суть В».

Логика, основанная на теории силлогизмов называется классической.

II. Декарт Рене (1596-1650, французский философ, математик). Рекомендовал в логике использовать математические методы.

III. Лейбниц Г.В. (1646-1716, немецкий философ и математик) - предложил использовать в логике математическую символику и впервые высказал мысль о возможности применения в ней двоичной системы счисления. Ему принадлежит идея логического исчисления, то есть четко сформулированные правила действий со словами и предложениями, сродни арифметическим правилам действий с числами. В соответствии с этими правилами простые элементы логических рассуждений (понятия) обозначаются буквами, сложные элементы (предложения) – формулами, а умозаключения – уравнениями. «Единственное средство улучшить наши умозаключения – сделать их, как у математиков, наглядными, и если среди людей возникнет спор, нужно сказать «Посчитаем!»; тогда без особых формальностей можно будет увидеть, кто прав», - писал Лейбниц.

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

IV. Джордж Буль (1815-1864, ирландский математик и логик) - основоположник математической логики. В 1847 г. Джордж Буль в работе «Математический анализ логики» изложил основы булевой алгебры. Разработал алфавит, орфографию и грамматику.

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

Развитие идей Буля привело к созданию современной математической логики, которая включает в себя алгебру множеств, алгебру высказываний, алгебру релейных схем (реле – это переключатель в электрических схемах), без которых было бы невозможным проектирование и программирование вычислительных машин. Именно булева алгебра лежит в основе работы компьютера.

V. Вклад в становление и развитие математической логики внесли также:

Аугустус де Морган (1806 - 1871);

Уильям Стенли Джевонс (1835 – 1882, английский экономист, статистик и философ-логик);

Платон Сергеевич Порецкий (1846-1907 – русский математик);

Чарлз Сандерс Пирс (1839-1914, американский философ, логик, математик и естествоиспытатель, «Исследования по логике» (1883)) и др.

3. Применение математической логики.

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

2) В гуманитарных науках (логика, криминалистика).

3) Математическая логика является средством для изучения деятельности мозга - для решения этой самой важной проблемы биологии и науки вообще.

4) Идеи и аппарат логики используется в кибернетике, ВТ и электротехнике (построены компьютеры на основе законов математической логики).

1938 г. – американский математик и инженер Клод Шеннон связал Булеву алгебру (аппарат математической логики), двоичную систему кодирования и релейно-контактные переключательные схемы, заложив основы будущих ЭВМ.

5) Идеи и аппарат логики используется в программировании, базах данных и экспертных системах. (PROLOG – язык логического программирования)

4. Алгебра высказываний. Простые и сложные высказывания.

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

Высказывание - это повествовательное предложение, о котором можно сказать, что оно истинно или ложно.

Высказываниями не являются:

1) восклицательные и вопросительные предложения.

2) определения.

3) предложения типа: «он сероглаз»; «x²-4x+3=0».

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

Основные операции алгебры высказываний.

Инверсия (логическое отрицание) - присоединение частицы «не» к сказуемому данного простого высказывания или присоединение слов «неверно что. . .» ко всему высказыванию.

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

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

Дизъюнкция двух логических высказываний ложна тогда и только тогда, когда оба высказывания ложны.

Конъюнкция (логическое умножение) - соединение двух высказываний А и В в одно с помощью союза «и».

Конъюнкция двух логических высказываний истинна тогда и только тогда,

когда оба высказывания истинны.

Импликация - логическая операция, соответствующая союзу «если ... , то...»

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

Эквиваленция - логическая операция, соответствующая союзу «тогда и только тогда, когда …».

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

Приоритет логических операций:

инверсия;

конъюнкция;

дизъюнкция;

импликация и эквивалентность.

Логическая операция	Обозначения	Эквивалент в русском языке
Инверсия (логическое отрицание)	НЕ, NOT, ,	не; неверно, что ...
Конъюнкция (логическое умножение)	И, AND, , &, • , 	и; а; но
Дизъюнкция (логическое сложение)	ИЛИ, OR, , +, , 	Или; Либо…, либо … Или…, или…
Импликация (логическое следование)	, , 	если ..., то ...; из ... следует ...; ... достаточно для ...; для ... , необходимо ...
Эквиваленция (логическое равенство)	, , , 	... если и только если ...; ... тогда и только тогда, когда ...; … в том и только в том случае, когда ...; необходимо и достаточно