Раздел «Основы логики и логические основы компьютера» в ЕГЭ по информатике

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ДАЛЬНЕВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ» (ГОУ ВПО ДВГГУ) Кафедра информатики и информационных технологий Н.В. Ганжусь, студентка 254 гр. РАЗДЕЛ «ОСНОВЫ ЛОГИКИ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА»  В ЕГЭ ПО ИНФОРМАТИКЕ выпускная квалификационная работа по специальности 030100 – информатика Оценка___________________                                    Научный руководитель: Дата защиты___ __________2011 г.                           старший преподаватель     Протокол № ______                                                     кафедры информатики и ИТ Председатель ГАК ____________                               ________ Пишкова Н.Е. 2 Хабаровск 2011 ОГЛАВЛЕНИЕ Введение................................................................................................................3 Глава 1. Основные сведения о ЕГЭ по информатике...................................7 1.1. Инструкция (структура) экзаменационной работы по информатике.........7 1.2. Содержание ЕГЭ по информатике................................................................9 1.3. Кодификатор по информатике......................................................................15 Глава 2. Теоретические основы раздела «Основы логики и  логические основы компьютера» .....................................................................19 2.1. Формы мышления............................................................................................19 2.2. Алгебра логики...............................................................................................23 2.2.1. Логические операции...................................................................................23 2.2.2. Логические выражения и функции.............................................................25 2.2.3. Логические законы.......................................................................................29 2.3. Логические основы устройства компьютера................................................31 2.3.1. Базовые логические элементы....................................................................31 2.3.2. Сумматор двоичных чисел..........................................................................34 2.3.3. Триггер..........................................................................................................38 Глава 3. Учебно­методические материалы для подготовки к ЕГЭ по  разделу «Основы логики и логические основы компьютера».....................40 3.1.   Анализ   заданий   ЕГЭ,   представленных   в   различных   учебно­методических пособиях, сборниках..............................................................................................40 3.2. Электронный образовательный ресурс «Способы решения логических задач» ­ как средство при подготовке к ЕГЭ..................................................................56 3.3. Разбор заданий ЕГЭ........................................................................................58 Заключение...........................................................................................................84 Список литературы.............................................................................................85 Приложения..........................................................................................................87 3 ВВЕДЕНИЕ Век   современных   технологий   затрагивает   абсолютно   все   сферы   жизни человека. В том числе, изменяется и процесс обучения. Не только в том смысле, что вводятся новые способы оценки знаний, онлайн дневники и журналы, но и приоритеты и акценты в процессах обучения изменяются. На протяжении уже нескольких   лет   очень   востребованным   и   нужным   предметом   является информатика,   а   также   внесение   ее   в   перечень   предметов   Единого Государственного Экзамена. Единый   Государственный   Экзамен   (ЕГЭ)  –  основная   форма государственной аттестации выпускников школ Российской Федерации. Подготовка к ЕГЭ по информатике стала актуальной с введением  этого предмета в перечень экзаменов по выбору, сдаваемых по  окончанию  средней общеобразовательной  школы   и  необходимых   при   поступлении   в   некоторые ВУЗы, в том числе и гуманитарные. Информатику сдают учащиеся, желающие стать студентами факультетов, тесно связанных с компьютерами и такими специальностями, как веб­дизайн, веб­программирование. Экзамен проверяет знания и умения выпускников на различных уровнях (базовый, профильный, высокий). Содержание экзаменационного материала включает основные темы курса информатики   и   информационных   технологий,   объединенные   в   тематические блоки.  Одним  из  них  является   раздел  «Основы   логики».  Данному   разделу   и подготовке   к   ЕГЭ   по   нему   посвящена   выпускная   квалификационная   работа 4 «Раздел   «Основы   логики   и   логические   основы   компьютера»   в   ЕГЭ   по информатике». Таким образом, становится  актуальным   вопрос подготовки школьников выпускных   классов   к   сдаче   Единого   Государственного   Экзамена   по информатике.   Кроме   того,   разделу   «Основы   логики   и   логические   основы компьютера» уделяется недостаточное внимание, хотя материал несет в себе большую методическую и познавательную нагрузку. Данный раздел неразрывно связан   с   такими   разделами   как   «Алгоритмизация   и   программирование», «Моделирование и формализация», «Базы данных». Практические задания по разделу одни из сложных в курсе информатики, не все учащиеся их усваивают и понимают, что в дальнейшем приводит к проблемам при изучении других тем, а также при сдаче ЕГЭ по информатике. Выполнение   ЕГЭ   по   данному   разделу   требует   от   учащихся   следующих знаний и умений:  знать основные элементы математической логики; создавать и  преобразовывать логические выражения; формировать для логической функции таблицу истинности и логическую схему; решать логические задачи. Объектом   исследования  является   процесс   подготовки   к   ЕГЭ   по информатике по теме «Основы логики и  логические основы компьютера». Предмет   исследования  –   организация   подбора   учебно­методических материалов по теме «Основы логики и   логические основы компьютера», для подготовки к сдаче ЕГЭ. Цель   работы  –   комплексное,   системное   изучение   заданий   ЕГЭ   по информатике по разделу «Основы логики и логические основы компьютера», а также   анализ   теоретического   и   учебно­методических   материалов   для 5 подготовки к ЕГЭ с разбором заданий  по данному разделу в частях А, В, С.  Исходя из цели,  поставлены следующие задачи исследования: 1) изучить методическую, учебную и специальную литературу, источники Internet по теме исследования. 2) проанализировать   основные   сведения   (положения)   о   ЕГЭ   по информатике. 3) рассмотреть и провести теоретический анализ раздела «Основы логики и логические основы компьютера». 4) рассмотреть и проанализировать различные типы заданий по разделу «Основы   логики   и   логические   основы   компьютера»,   выносимые   на   ЕГЭ; выделить   основные   трудности   при   их   решении;   выполнить   подборку   за последние годы. Структура   работы  представлена   следующим   образом:   введение,   три главы, заключение, список использованной литературы и источников Интернет, приложения. Первая   глава   содержит   в   себе   общие   сведения   о   ЕГЭ   по   информатике (инструкция, содержание, кодификатор). Вторая глава содержит теоретические основы раздела «Основы логики и логические   основы   компьютера»,   объединяющая   три   основные   части:   формы мышления, алгебра логики и логические основы устройства компьютера. И наконец, в третьей главе представлены учебно­методические материалы для   подготовки   к   ЕГЭ   по   разделу     «Основы   логики   и   логические   основы компьютера»:   анализ   заданий   ЕГЭ   в   сборниках,   учебно­методических материалах; способы решения логических задач; разбор заданий, вошедших в вопросы на ЕГЭ из раздела «Основы логики» в частях А, В, С. Приложения включают в себя — описание материалов, представленных на CD­диске: 6 ЭОР «Способы решения логических задач»; Презентация «Логика»; Электронный учебник «Логика в ЕГЭ» («Подготовка к ЕГЭ по логике»); Задачи   ЕГЭ   «Основы   логики»   (интерактивный   задачник   по   книге Сафонова «Готовимся к ЕГЭ»); Задания по логике (представлены задания из сборника экзаменационных заданий ЕГЭ 2009г. П.А. Якушкин, в конце даны ответы); Логика   (Logic:   программа­тренажер   для   обучения   основам математической логики); Логика   в   вопросах   ЕГЭ   (решение   заданий,   представленных   в   ЕГЭ,   с представленными заданиями для тренировки). Важным в выпускной квалификационной работе является самостоятельная разработка некоторых приложений (ЭОР «Способы решения логических задач»; Электронный   учебник   «Логика   в   ЕГЭ»;   задания   по   логике)   в   электронном варианте. 7 ГЛАВА 1. ОСНОВНЫЕ СВЕДЕНИЯ О ЕГЭ ПО ИНФОРМАТИКЕ В процессе написания дипломной работы, были рассмотрены документы, в которых определены общие сведения (положения) о ЕГЭ по информатике; они представлены в данной главе: 1. 2. 3. инструкция (структура) экзаменационной работы по информатике; содержание ЕГЭ по информатике; кодификатор по информатике. 1.1. ИНСТРУКЦИЯ (СТРУКТУРА) ЭКЗАМЕНАЦИОННОЙ РАБОТЫ ПО ИНФОРМАТИКЕ  С 2009 года Единый Государственный Экзамен (ЕГЭ) является основной формой итоговой государственной аттестации в школе для всех выпускников школ Российской Федерации. Назначение   ЕГЭ  –   оценить   общеобразовательную   подготовку   по информатике и ИКТ выпускников XI классов общеобразовательных учреждений с   целью   проведения   итоговой   аттестации   выпускников   общеобразовательных учреждений   и   конкурсного   отбора  абитуриентов  в   учреждения   среднего   и высшего профессионального образования. ЕГЭ проводится с использованием заданий стандартизированной  формы – контрольных   измерительных   материалов   (КИМ).   Для   записи   ответов   результаты   выполнения   заданий используются   специальные   бланки, обрабатываются автоматизировано, с использованием компьютеров. Содержание, формат и организация экзамена определяются утверждаемым ежегодно   комплексом   документов,   важнейшим   из   которых   является инструкция. Инструкция (структура) экзаменационной работы Общее число заданий в экзаменационной работе – 32. 8 Экзаменационная работа состоит из трёх частей.  Часть   1   (А)  содержит   18   заданий   базового,   повышенного   и   высокого уровней   сложности.   В   этой   части   собраны   задания   с   выбором   ответа, подразумевающие выбор одного правильного ответа из четырех предложенных. Часть 2 (В)  содержит 10 заданий базового, повышенного и высокого уровней сложности.   В   этой   части   собраны   задания   с   краткой   формой   ответа, подразумевающие   самостоятельное   формулирование   и   ввод   ответа   в   виде последовательности   символов.  Часть   3   (С)  содержит   4   задания,   первое   из которых   повышенного   уровня   сложности,  остальные   три   задания  –  высокого уровня сложности.  На выполнение экзаменационной работы отводится 4 часа (240 минут). На выполнение заданий Части 1 (А) и Части 2 (В) рекомендуется отводить 1,5 часа (90 минут). На выполнение заданий Части 3 (С) рекомендуется отводить 2,5 часа (150 минут). В экзаменационных заданиях используются следующие соглашения по теме «Основы логики и логические основы компьютера»: 1.   Обозначения   для   логических   связок   (операций):   ­   отрицание   (инверсия, логическое   НЕ)   обозначается  ¬   (например,   ¬   А);  ­   конъюнкция   (логическое умножение, логическое И) обозначается /\, & (например, А /\ В, либо А & В);    ­ дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/, | (например,   А   \/   В,   либо   А   |   В);   ­   следование   (импликация)   обозначается  → (например, А   В);→   ­ символ 1 используется для обозначения истины (истинного высказывания); символ 0 — для обозначения лжи (ложного высказывания). 2.   Два   логических   выражения,   содержащих   переменные,   называются равносильными, если значения этих выражений совпадают при любых значениях переменных. Так, выражения А  →  В и (¬А) \/ В равносильны; а выражения А /\ В 9 и А \/ В — нет (значения выражений разные, например, А=1, В=0). 3. Приоритеты   логических   операций:   инверсия   (отрицание),   конъюнкция (логическое   умножение),   дизъюнкция   (логическое   сложение),   импликация (следование), эквивалентность (равносильность). 1.2. СОДЕРЖАНИЕ ЕГЭ ПО ИНФОРМАТИКЕ Содержание   экзаменационной   работы   рассчитано   на   выпускников   XI классов   общеобразовательных   учреждений,   изучавших   курс   информатики   и ИКТ,   в   соответствии   с   обязательным   минимумом   содержания   среднего (полного)   общего   образования   по   информатике,   по   учебникам   и   учебно­ методическим комплектам к ним, имеющим гриф Министерства образования и науки Российской Федерации. Содержание заданий разработано по основным темам курса информатики и информационных технологий, объединенным в следующие тематические блоки: «Информация   и   её   кодирование»,   «Алгоритмизация   и   программирование»,   «Моделирование   и   компьютерный   эксперимент», «Основы   логики», «Программные   средства   информационных   и   коммуникационных   технологий», «Технология   обработки   графической   и   звуковой   информации»,   «Технология обработки   информации   в   электронных   таблицах»,   «Технология   хранения, поиска   и   сортировки   информации   в  базах   данных», «Телекоммуникационные технологии».  Часть 1 (A) экзаменационной  работы содержит задания, большинство из которых  относятся   к  базовому     и   повышенному   уровням   сложности,  и   одно задание высокого уровня. Часть 2 (B) содержит в основном задания повышенного уровня, а также по одному заданию базового и высокого уровней сложности. Задания Части 3 (С) относятся к повышенному и высокому уровням. Всего: базовый ­17, повышенный ­10, высокий ­5. 10 Распределение заданий по частям экзаменационной работы представлено в таблице 1.  Таблица 1. Распределение заданий по частям экзаменационной работы  Части работы Число заданий Максимальный первичный балл Процент максимального первичного балла за задания данной части от максимального первичного балла за всю работу (=40) Часть 1 Часть 2 Часть 3 Итого 18 10 4 32 18 10 12 40 45% 25% 30% 100% Тип заданий С выбором ответа С кратким ответом С развернутым ответом  Распределение   заданий   экзаменационной   работы   по   содержанию   и видам   деятельности.  Отбор   содержания,   подлежащего   проверке   в экзаменационных   работах   ЕГЭ   2009г.,   2010г.   осуществлялся   на   основе обязательного   минимума  содержания   среднего  (полного)   общего   образования федерального   компонента   государственного   образовательного   стандарта. Распределение заданий по разделам курса информатики и ИКТ представлено в таблице 2. Таблица 2. Распределение заданий по разделам курса информатики и ИКТ Название раздела № п/п Часть 1 Часть 2 Часть 3 Вся работа Количество заданий 1 Информация и ее кодирование 2 Алгоритмизация и программирование 3 Основы логики 4 Моделирование 5 Программные средства  ИКТ 6 Технология   обработки   графической   и звуковой информации 7 9 5 1 1 1 6 5 3 1 1 1 2 2 2 0 0 0 0 2 0 0 0 0 7 Технология   обработки   информации   в электронных таблицах 8 Технология   хранения,   поиска   и сортировки информации в базах данных 9 Телекоммуникационные технологии 10 Технология программирования Итого: 2 1 3 2 32 2 1 0 0 20 0 0 2 0 8 11 0 0 0 2 4 В КИМ по информатике и ИКТ не включены задания, требующие простого воспроизведения   знания   терминов,   понятий,   величин,   правил   (такие   задания слишком просты для выполнения). При выполнении любого из заданий КИМ от экзаменуемого требуется решить какую­либо задачу: либо прямо использовать известное   правило,   алгоритм,   умение,   либо   выбрать   из   общего   количества изученных   понятий   и   алгоритмов   наиболее   подходящее   и   применить   его   в известной либо новой ситуации. По разделу «Основы логики» выполняются задания на базовом (часть А — 3 задания) и повышенном (часть В — 2 задания) уровнях. Материал, проверяемый ЕГЭ На уровне  воспроизведения знаний  (первая часть: 6 заданий)  по разделу «Основы   логики   и   логические   основы   компьютера»   проверяется   такой фундаментальный   теоретический   материал, математической логики.   как:   основные   элементы Материал на проверку сформированности умений применять свои знания в стандартной ситуации, входящий во все три части экзаменационной работы (17   заданий),   включает:  создавать   и   преобразовывать   логические   выражения; формировать для логической функции таблицу истинности и логическую схему. Материал на проверку сформированности  умений применять свои знания в новой ситуации (9 заданий) входит во все три части экзаменационной работы. Это следующие сложные умения: решать логические задачи. 12 План экзаменационной работы ЕГЭ по информатике и ИКТ Обозначение заданий в работе и бланке ответов: А – задания с выбором ответа,   В   –   задания   с   кратким   ответом,   С   –   задания   с   развернутым ответом. Уровни сложности задания: Б – базовый (примерный интервал выполнения задания – 60%­90%), П – повышенный (40%­60%), В – высокий (менее 40%). Таблица 3. Порядок следования заданий в КИМ  Обозначен ие задания в работе А1 А2 А3 А4 А5 А6 Проверяемые элементы содержания Кодирование текстовой  информации. Кодировка ASCII. Основные кодировки  кириллицы Умение подсчитывать  информационный объем  сообщения Знания о системах счисления и  двоичном представлении  информации в памяти  компьютера Умения выполнять  арифметические операции в  двоичной, восьмеричной и  шестнадцатеричной системах  счисления Использование переменных.  Объявление переменной (тип,  имя, значение). Локальные и  глобальные переменные Работа с массивами  (заполнение, считывание,  поиск, сортировка, массовые  Коды содержания по кодификатору Уровень сложности задания Макс. балл 1.1.8 1.1.4 1.1.7 1.1.7 1.2.3 1.2.4 Б П Б Б Б П 1 1 1 1 1 1 операции и др.)  Знание основных понятий и  законов математической  логики Умения строить и  преобразовывать логические  выражения Умения строить таблицы  истинности и логические схемы Умение представлять и  считывать данные в разных  типах информационных  моделей (схемы, карты,  таблицы, графики и формулы) Умение кодировать и  декодировать информацию  Формальное исполнение  алгоритма, записанного на  естественном языке Знания о файловой системе  организации данных Знание технологии хранения,  поиска и сортировки  информации в базах данных  Знание технологии обработки  графической информации  Знание технологии обработки  информации в электронных  таблицах  Знания о визуализации данных  с помощью диаграмм и  графиков  Умение исполнить алгоритм  для конкретного исполнителя с фиксированным набором  команд  Знания о методах измерения  1.3.1 1.3.2 1.3.3 1.4.2 1.1.5 1.2.1 2.2.3 2.6.1 / 2.6.2 / 2.6.3 / 2.6.4 2.4.1 / 2.4.2 / 2.4.3 / 2.5.1 / 2.5.2 2.5.3 1.2.1 / 1.2.2 1.1.3 А7 А8 А9 А10 А11 А12 А13 А14 А15 А16 А17 А18 В1 П Б Б Б Б Б Б Б П Б Б В Б 13 1 1 1 1 1 1 1 1 1 1 1 1 1 количества информации  Знание и умение использовать  основные алгоритмические  конструкции: следование,  ветвление, цикл  Представление числовой  информации в памяти  компьютера. Перевод,  сложение и умножение в  разных системах счисления  Умение строить и  преобразовывать логические  выражения  Умение исполнять алгоритм в  среде формального  исполнителя  Умение строить и  преобразовывать логические  выражения  Умение определять скорость  передачи информации при  заданной пропускной  способности канала  Умение исполнять алгоритм,  записанный на естественном  языке  Знание базовых принципов  организации и  функционирования  компьютерных сетей,  адресации в сети  Умение осуществлять поиск  информации в Интернет  Умение прочесть фрагмент  программы на языке  программирования и исправить допущенные ошибки  Умения написать короткую  (10–15 строк) простую  1.2.2 1.1.7 1.3.2 1.2.2 1.3.2 1.1.6 1.2.1 2.7.1 2.7.3 2.8.1 / 2.8.2 1.2.4 / 2.8.3 В2 В3 В4 В5 В6 В7 В8 В9 В10 С1 С2 14 1 1 1 1 1 1 1 1 1 3 2 Б П В Б П П П Б П П В 15 программу обработки массива  на языке программирования  или записать алгоритм на  естественном языке  Умение построить дерево игры по заданному алгоритму и  обосновать выигрышную  стратегию (логическая задача)  Умения создавать собственные программы (30–50 строк) для  решения задач средней  сложности С3 С4 1.2.1 2.8.3 В В 3 4 16 1.3. КОДИФИКАТОР ПО ИНФОРМАТИКЕ Кодификатор   составлен   на   базе   стандарта   обязательного   минимума содержания   среднего  (полного)   общего   образования   по   информатике   и   ИКТ (приказ   Минобразования   России   №   1089   от   05.03.2004г.).   В   кодификаторе каждый контролируемый элемент содержания имеет свой порядковый номер. В   таблице   4   жирным   шрифтом   указаны   крупные   блоки   содержания, которые ниже разбиты на более мелкие элементы. Каждому заданию присвоен номер того элемента содержания в кодификаторе, на проверку которого оно нацелено   прежде   всего.   Если   задание   проверяет   содержание   всего   крупного блока, указывается сокращенный номер элемента. Таблица 4. Кодификатор по разделам информатики и ИКТ Код Элементы содержания, проверяемые заданиями КИМ Код блока 1 1.1 контроли руемого элемента ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ И СИСТЕМЫ Информация и ее кодирование 1.1.1 Различные подходы к определению понятия «информация». Виды информационных процессов. Информационный аспект в деятельности человека. Язык как способ представления и передачи информации. Методы измерения количества информации: вероятностный и алфавитный. Единицы   измерения   количества   информации.   Числовые параметры объектов и процессов: объем памяти (хранение информации), скорость обработки информации. Процесс передачи информации. Виды и свойства источников и   приемников   информации.   Сигнал,   кодирование   и декодирование. Скорость передачи информации и пропускная способность канала связи. 1.1.2 1.1.3 1.1.4 1.1.5 1.1.6 17 1.1.7 1.2.2 1.2.3 1.2.4 1.2.5 Представление   числовой   информации.   Операции   в   разных системах счисления. Кодирование текстовой информации. Кодировка ASCII.  1.1.8 Алгоритмизация и программирование 1.2.1 Алгоритмы,   виды   алгоритмов,   описания   алгоритмов. Формальное исполнение алгоритма. Использование   основных   алгоритмических   конструкций: следование, ветвление, цикл. Использование   переменных.   Объявление   переменной   (тип, имя, значение). Локальные и глобальные переменные. Работа с массивами (заполнение, считывание, поиск, и др.) Структурирование задачи при ее решении для использования вспомогательного   алгоритма.   Вспомогательные   алгоритмы: функции и процедуры. 1.2 1.3 Основы логики 1.3.1 1.3.2 1.3.3 Алгебра логики. Логические выражения и их преобразование. Построение таблиц истинности логических выражений. 1.4 Моделирование и компьютерный эксперимент 1.4.1 1.4.2 1.4.3 1.4.4 Общая структура деятельности по созданию компьютерных моделей. Представление   и   считывание   данных   в   разных   типах информационных моделей (схемы, карты, таблицы, графики и формулы). Математические модели (графики, исследование функций). Построение   и   использование   информационных   моделей реальных химических, биологических, экономических). (физических,   процессов     1.5 Социальная информатика 1.5.1 1.5.2 История развития вычислительной техники. Нормы   информационной   этики   (почта,   публикации   в Интернете и др.). Правовые нормы в области информатики. 1.5.3 2 2.1 2.2 2.3 2.4 18 ИКТ   (ИНФОРМАЦИОННЫЕ   И   КОММУНИКАЦИОННЫЕ ТЕХНОЛОГИИ) Основные устройства ИКТ 2.1.1 Типы компьютеров, их основные характеристики и области использования.  Основные периферийные устройства (ввода — вывода, для соединения компьютеров, и др.). Обеспечение   надежного   функционирования   средств   ИКТ, устранение простейших неисправностей, требования техники безопасности, гигиены, и др. при работе со средствами ИКТ. 2.1.2 2.1.3 Программные средства ИКТ 2.2.1 2.2.2 ОС: назначение и функциональные возможности. Графический   интерфейс   (основные   типы   элементов управления). Файлы и файловая системы (архиваторы). Оперирование   использованием знаний о возможностях ИКТ. Технологии   и   средства   защиты   информации   от несанкционированного доступа (антивирусные программы, и др.) информационными объектами     с 2.2.3 2.2.4 2.2.5 Технологии обработки текстовой информации 2.3.1 2.3.2 Ввод, редактирование и форматирование текста. Внедрение   в   текстовый   документ   различных   объектов (таблиц, диаграмм, рисунков, формул) и их форматирование. Автоматизация   процесса   подготовки   издания.   Верстка документа. Проверка орфографии и грамматики. 2.3.3 Технология обработки графической и звуковой информации 2.4.1 Растровая   графика.  Графические   объекты   и   операции   над ними. Векторная графика. Графические объекты и операции над ними. Компьютерное черчение. Основные операции над чертежом. Создание и редактирование цифровых звукозаписей. 2.4.2 2.4.3 2.4.4 19 Компьютерные презентации. 2.4.5 Технология обработки информации в электронных таблицах 2.5.1 Ввод и редактирование данных в электронных таблицах,  операции над данными. Экспорт и импорт данных. Типы и формат данных. Работа с формулами. Абсолютная и  относительная ссылки. Использование функций. Визуализация данных с помощью диаграмм и графиков.  Построение графиков элементарных функций. 2.5.2 2.5.3 Технология хранения, поиска и сортировки информации в базах  данных 2.6.1 2.6.2 2.6.3 2.6.4 Структура БД (записи и поля). Табличное и картотечное представление БД. Сортировка и отбор записей. Использование различных способов формирования запросов к БД. Телекоммуникационные технологии 2.7.1 Базовые   принципы   организации   и   функционирования компьютерных   сетей.   Локальные   и   глобальные   сети. Адресация в сети. Услуги   компьютерных   сетей:  World  Wide  Web  (WWW), электронная почта, файловые архивы, поисковые системы, и т.д. Поиск информации в Интернете. Методы и средства создания и сопровождения сайта (основы HTML). Чтение   короткой   (30   ­   50   строк)   простой   программы   на алгоритмическом языке (языке программирования). Поиск и исправление ошибок в небольшом фрагменте (10­20 строк) программы Создание собственной программы (30­50 строк) для решения простых задач. Примеры возможных задач: суммирование массива; проверка Технологии программирования 2.8.1 2.5 2.6 2.7 2.8  2.7.2 2.7.3 2.7.4 2.8.2 2.8.3 20 упорядоченности   массива;   слияние   двух   упорядоченных массивов;   сортировка   (например,   вставками);   умножение двух многочленов; разложение целого числа на множители (простейший алгоритм); поиск корня делением пополам; и т.д. 21 ГЛАВА 2. ТЕОРЕТИЧЕСКИЙ АНАЛИЗ РАЗДЕЛА  «ОСНОВЫ ЛОГИКИ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА» Для   успешного   выполнения   заданий   ЕГЭ   по   разделу   «Основы   логики   и логические   основы   компьютеры»,   учащиеся   должны   твердо   усвоить теоретические   основы   данной   темы,   которые   представлены   в   данной   главе, следующим   образом:   понятия   форм   мышления   (понятие,   суждение, умозаключение, алгебра высказываний); алгебра логики (логические операции: инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность). Кроме того, необходимо знать и уметь  применять при работе с логическими выражениями основные   законы   логики   и   правила   преобразования   логических   выражений (правило построения таблицы истинности). Немало   важным   является   и   знание   логических   основ   устройств компьютера,   каковыми   являются   базовые   логические   элементы   (инвертор, конъюнктор,   дизъюнктор)   и   типовые   логические   устройства   компьютера (сумматор, триггер, регистр).  В  данной главе рассмотрены и проструктурированы теоретические основы, связанные с логикой. Для этого были изучены и проанализированы следующие пособия:   Лыскова   В.Ю.,   Ракитина   Е.А.   Логика   в   информатике   —   М.: Лаборатория   Базовых   Знаний,   2001;   Угринович   Н.Д.     Информатика   и   ИКТ. Профильный уровень: учебник для 10 класса —   М.: БИНОМ. Лаборатория знаний, 2008. 2.1. ФОРМЫ МЫШЛЕНИЯ Формальной   логикой   принято   называть   античную   логику,   основанную Аристотелем.   Это   название   происходит   от   основного   принципа   логики   как науки,   который   гласит,   что   правильность   рассуждения   (умозаключения) определяется только его логической формой, или структурой, и не зависит от 22 конкретного содержания входящих в него суждений [7]. Логика — наука о формах и способах мышления. Мышление всегда осуществляется в каких­то формах. Основными формами мышления являются: понятие, суждение (высказывание), умозаключение. Понятие.  Понятие   —   форма   мышления,   отражающая   наиболее существенные   свойства   и   признаки   предмета,   отличающие   его   от   других предметов. Характеризуется содержанием и объемом. Содержание понятия — совокупность существенных признаков предмета. Чтобы раскрыть содержание понятия,   следует   выделить   признаки,   необходимые   и   достаточные   для выделения   данного   объекта   по   отношению   к   другим   объектам.     Например, понятие «компьютер» объединяет множество электронных устройств, которые предназначены   для   обработки   информации   и   обладает   монитором   и клавиатурой. Объем   понятия  —   совокупность   предметов,   на   которую   понятие распространяется.   Объем   понятия   «компьютер»   выражает   всю   совокупность существовавших,   существующих   и   могущих   существовать   в   будущем компьютеров. Объем и содержание понятия связаны между собой, и эта связь выражается следующим   законом:   чем   больше   объем   понятия,   тем   меньше   его   объем. Например, понятие «карманный компьютер» охватывает меньший объем, чем понятие «компьютер», но обладает большим содержанием. Для   наглядной   геометрической   иллюстрации   объемов   понятий   и соотношений   между   ними   используются  диаграммы   Эйлера­Венна,  как представлено на рисунке 1: Рис.1. Представление объемов понятий с использованием диаграммы Эйлера­Венна 23 Если имеются какие­либо понятия А, В, С и т. д., то объем каждого понятия (множество)   можно   представить   в   виде   круга,   а   отношения   между   этими объемами   (множествами)   —   в   виде   пересекающихся   кругов.   Например, отобразим   с   помощью   диаграммы   соотношение   между   объемами   понятий «натуральные числа» и «четные числа». Объем понятия «натуральные числа» включает в себя множество целых положительных чисел  А, а объем понятия «четные числа» включают в себя множество отрицательных и положительных четных чисел  В. Эти множества пересекаются, так как оба включают в себя множество положительных четных чисел С (рис.1).  Суждение.  Суждение (высказывание) — форма мышления, выраженная с помощью понятий, посредством которой что­либо утверждают или отрицают о предметах, их свойствах и отношениях между ними. О предметах можно судить верно,   или   неверно,   т. е.   высказывание   может   быть   истинным   или   ложным. Истинным  будет высказывание, в котором связь понятий правильно отражает свойства и отношения, реальных вещей.  Ложным  высказывание будет в том случае, когда связь понятий искажает объективные отношения, не соответствует реальной действительности. Высказывания могут быть выражены не только с помощью естественных языков,   но   и   с   помощью   формальных   языков.   Из   двух   числовых   выражений можно составить высказывания, соединив их знаками равенства или неравенства. Например, высказывание на естественном языке имеет вид «Два умножить на два равно четырем», а на формальном, математическом языке оно записывается в виде «2 x 2 =4». Высказывание   называется  простым,   если   никакая   его   часть   сама   не является высказыванием. Высказывание, состоящее из простых высказываний, называются составным (сложным). Умозаключение. Умозаключение — форма мышления, в которой из одного 24 или нескольких суждений (называемых посылками) по определенным правилам логического   вывода   получается   новое   знание   о   предметах   реального   мира (вывод, или заключение). Умозаключения бывают дедуктивные, индуктивные и по аналогии.  В  дедуктивных  умозаключениях   рассуждения   ведутся   от   общего     к частному.   Например,   из   двух   суждений:   «Все   металлы   электропроводны»   и «Ртуть является металлом»    —    путем умозаключения можно сделать вывод: «Ртуть электропроводна». В  индуктивных  умозаключениях   рассуждения   ведутся   от   частного   к общему.   Например,   установив,   что   отдельные   металлы  —  железо,   медь, алюминий, и т. д.  — обладают свойством электропроводности, можно сделать вывод, что все металлы электропроводны. Умозаключение  по   аналогии  представляют   собой   движение   мысли   от общности одних свойств и отношений у сравниваемых предметов или процессов к общности других свойств и отношений. Например, химический состав Солнца и Земли сходен по многим показателям, поэтому, когда на Солнце обнаружили неизвестный еще на Земле химический элемент гелий, то по аналогии заключили: такой элемент есть и на Земле. Доказательство.  Доказательство   есть   мыслительный   процесс, направленный   на   подтверждение   или   опровержение   какого­либо   положения посредством других несомненных, ранее обоснованных доводов. Доказательство по логической форме не отличается от умозаключения.  Примером   умозаключений   могут   быть   геометрические   доказательства. Например,  если  мы  имеем  суждение  «Все  углы  треугольника  равны»,  то  мы можем путем умозаключения доказать, что в этом случае справедливо суждение «Этот треугольник равносторонний» [12, с. 155]. 25 2.2. АЛГЕБРА ЛОГИКИ В своем развитии логика прошла ряд этапов. Современную логику называют математической.  Алгебра   высказываний   (алгебра   логики)  ­   раздел математической логики [7]. Алгебра  в   широком   смысле   слова   —   наука   об   общих   операциях, аналогичных   сложению   и   умножению,   которые   могут   выполняться   над различными   математическими   объектами   (алгебра   переменных   и   функций, алгебра   векторов,   алгебра   множеств   и   т. д.).   Объектами   алгебры   логики являются высказывания. Алгебра   логики   отвлекается   от   смысловой   содержательности высказываний. Для нее важен только один факт — истинно или ложно данное высказывание,   что   дает   возможность   определять   истинность   или   ложность составных высказываний алгебраическими методами. 2.2.1. ЛОГИЧЕСКИЕ ОПЕРАЦИИ Над высказываниями в алгебре логики определяются следующие основные логические   операции,   в   результате   которых   получаются   новые,   составные высказывания: Логическое   отрицание   (инверсия)  —   это   логическая   операция применяемая   к   одному   высказыванию.   Высказывание,   Ā   есть   высказывание, которое   ложно,   когда   А   истинно,   и   истинно,   когда   А   ложно.   Высказывание называется отрицанием А. Возможные обозначения отрицания: ¬А, not А, Ā, не А. Логическое   умножение   (конъюнкция)  —   это   логическая   операция, ставящая   в   соответствие   каждым   двум   простым   высказываниям   составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Возможные обозначения конъюнкции: А И В, А& В, А AND B, А∙В, А\/В. 26 27 Логическое   сложение   (дизъюнкция)  —   это   логическая   операция, ставящая   в   соответствие   каждым   двум   простым   высказываниям   составное высказывание, являющееся истинным тогда и только тогда, когда истинно хотя бы одно из высказываний. Возможные обозначения дизъюнкции: А ИЛИ В, А/\В, А OR В, А + В, А||В.  Дополнительными логическими операциями являются:  Логическое   следование   (импликация)  —   высказывание   ложно   тогда   и только тогда, когда А истинно, а В ложно. Возможные обозначения импликации: А→ В, А => В. Эквивалентность  —   это   высказывание   истинно   тогда   и   только   тогда, когда А и В оба истинны или оба ложны. Возможные обозначения эквивалентности: А ~ В, А <=> В, А≡В.  Значения   логических   операций   задаются   с   помощью   таблиц   истинности. Таблица истинности показывает, какие значения дает логическая операция при всех возможных наборах ее аргументов (табл.5). Таблица 5. Основные и дополнительные логические операции Отрицание А Ā Конъюнкция А Дизъюнкция В А&В А В А\/В Следование А В А→В Эквивалентность А А~ В В 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 28 2.2.2. ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ФУНКЦИИ Всякое   сложное   высказывание,   составленное   из   некоторых   исходных высказываний   посредством   логических   операций,   называют  логическим выражением (формулой алгеброй логики). Исходные   высказывания   могут   быть  логическими   константами  (если имеют   постоянное   значение   «истина»   или   «ложь»)   или  логическими переменными. Переменные высказывания — это такие переменные, значениями которых могут быть любые наперед заданные простые высказывания — константы. Логические операции позволяют каждой формуле при заданных значениях входящих в нее высказываний приписать одно из двух значений: 0 или 1. Тем самым каждая формула может рассматриваться как некоторый способ задания или реализации функции алгебры логики.  Логическая функция  — функция, определенная на множестве значений (истина, ложь) и принимающая значение из того же множества [7]. Например, F1=A&B, F2=A\/B. Функцию   можно   задавать   как   в   виде   формулы,   так   и   в   виде   таблицы, которая содержит все наборы значений переменных и значения функции на этих наборах. Такая таблица называется таблицей истинности. Таблица  истинности  логического  выражения  —  таблица,   содержащая значения  логического   выражения,  полученные   на  всех   значениях   входящих   в него логических переменных. При   построении   таблиц   истинности   целесообразно   руководствоваться определенной последовательностью действий.  Правило построения таблицы истинности: Построим   таблицу   истинности   для   логического   выражения   —   (А\/В)   & (¬А\/¬В). 29 Во­первых,   необходимо   определить   количество   строк   в   таблице истинности,   которое   равно   количеству   возможных   комбинаций   значений логических переменных, входящих в логическое выражение. Если количество логических переменных n, то: Количество строк = 2ⁿ. В   нашем   случае   логическое   выражение   (А\/В)   &   (¬А\/¬В)   имеет   две переменные и, следовательно, количество строк в таблице истинности должно быть равно:  Количество строк = 2ⁿ = 2² =4. Во­вторых,  необходимо   определить   количество   столбцов   в   таблице истинности, которое равно количеству логических переменных плюс количество логических операций.  В   нашем   случае   количество   переменных   равно   двум,   а   количество логических операций равно пяти, т. е. количество столбцов  таблицы истинности равно: Количество столбцов = 2 + 5 = 7. В­третьих,  необходимо   построить   таблицу   истинности   с   указанным количеством   строк   и   столбцов,   обозначить   столбцы   и   ввести   все   возможные наборы   значений   логических   переменных.   Наборы   входных   переменных,   во избежание ошибок, рекомендуют вводить следующим образом: 1) разделить столбец значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами; 2) разделить   столбец   значений   второй   переменной   на   четыре   части   и заполнить четверти чередующимися группами нулей и единиц, начиная с группы нулей; 3) продолжать деление столбцов значений последующих переменных на 8, 16, и т. д. частей  и заполнение их группами нулей или единиц до тех пор, пока группа нулей (единиц) не будет состоять из одного символа. 30 В­четвертых,    необходимо   заполнить   таблицу   истинности   по   столбцам, выполняя   базовые   логические   операции   в   необходимой   последовательности (инверсия,   конъюнкция,   дизъюнкция,   следование,   эквивалентность)   и   в соответствии с их таблицами истинности.  Построим таблицу истинности для рассмотренного логического выражения (табл.6). Таблица 6. Таблица истинности логического выражения   (А\/В) & (¬А\/¬В) А \/ В ¬А \/ ¬В (А\/В) & (¬А\/¬В) 0 1 1 1 1 1 1 0 0 1 1 0 А 0 0 1 1 В 0 1 0 1 ¬А 1 1 0 0 ¬В 1 0 1 0 Рассмотрим   логическое   выражение   А&(В\/¬В&¬С)   с   тремя   логическими переменными, то количество строк в таблице истинности должно быть:  Количество строк = 2  ⁿ =2³ =8 Количество  логических операций равно пяти, следовательно, количество столбцов в таблице истинности: Количество столбцов = 3+5=8 Построим таблицу истинности: Таблица 7. Таблица истинности логического выражения  А&(В\/¬В&¬С) А В 0 0 0 0 1 0 0 1 0 1 С 0 1 0 1 0 ¬В 1 1 0 0 1 ¬С 1 0 1 0 1 ¬В & ¬С В \/ (¬В&¬С) А&(В\/¬В&¬С) 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 Логические выражения и их преобразование Будем   называть   две   функции  F1  и  F2  равносильными,   или тождественными, если при любых значениях всех переменных, входящих в F1 и 31 0 1 1 F2, эти функции принимают одинаковые значения. Равносильность обозначается знаком равенства (=). Например: А ~ В = (А\/¬B) & (¬А\/В) Посредством   приведенных   операций   над   высказываниями   могут   быть образованы другие, сколько угодно сложные высказывания. В   итоге,   исходя   из   выше   изложенного   следует,   что   любое   логическое выражение можно рассматривать как логическую функцию   F(X1,  X2, … ,  Xn), аргументами которой являются логические переменные   X1,  X2, … ,  Xn.  Сама функция  и аргументы  могут  принимать   только  два  значения: «истина» (1)  и «ложь» (0). Каждая   логическая   функция   двух   аргументов   имеет   четыре   возможных значения.   Каждая   функция   несет   4   бита   информации   и   тогда   количество различных логических функций двух аргументов может существовать: N=2ⁿ (где n=4) =16 Таким   образом,   существует   16   различных   логических   функций   двух аргументов,   каждая   из   которых   задается   собственной   таблицей   истинности (табл.8). Аргумен ты Таблица 8. Таблицы истинности логических функций  двух аргументов Логические функции А В F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F1 1 F1 2 F1 3 F1 4 F1 5 F16 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 32 1 1 1 1 F2  –   функция   логического   умножения;  F8  –   функция   логического сложения; F10 – функция эквивалентности; F14 — функция импликации. 2.2.3. ЛОГИЧЕСКИЕ ЗАКОНЫ В  алгебре  логики  законы  логики  записываются  в  виде  формул,  которые позволяют проводить равносильные преобразования логических выражений [12, с.174 ­с. 176]. 33 Закон   непротиворечия.  Высказывание   не   может   быть   одновременно истинным и ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно: А & Ā = 0 Закон исключенного третьего. Высказывание может быть либо истинным, либо   ложным,   третьего   не   дано.   Это   означает,   что   результат   логического сложения высказывания и его отрицания всегда принимает значение истина: Закон   двойного   отрицания.  Если   дважды   отрицать   некоторое А \/ Ā = 1 высказывание, то в результате мы получим исходное высказывание: ¬ (¬А) = А        Законы де Моргана (законы общей инверсии для логического сложения (1) и логического умножения (2). 1)   Отрицание   дизъюнкции   переменных   равно   конъюнкции   отрицаний переменных: 2)   Отрицание   конъюнкции   переменных   равно   дизъюнкции   отрицаний ¬ (А \/ В) = ¬А & ¬В переменных: ¬ (А & В) = ¬А \/ ¬В Законы поглощения: 1) для логического сложения:   2) для логического умножения: А \/ (А & В) = А А & (А \/ В) = А Закон исключения (склеивания): 1) для логического сложения: 2) для логического умножения: (А&В) \/ (¬А & В) = В (А\/В) & (¬А\/В) = В Кроме   логических   законов   важное   значение   для   выполнения 34 преобразований   логических   выражений   имеют   правила   алгебраических преобразований.  Правило коммутативности (переместительности). В алгебре переменных и функций слагаемые и множители можно менять местами. В алгебре логики можно   менять   местами   логические   переменные   при   операциях   логического умножения и логического сложения. 1) для логического умножения: 2) для логического сложения:  А & В = В & А  А \/ В = В \/ А Правило   ассоциативности   (сочетательности).  Если   в   логическом выражении используется только операция логического умножения или только операция логического сложения, то скобки можно расставлять произвольно. 1) для логического умножения: (А & В) & С = А & (В & С) 2) для логического сложения:  (А \/ В)\/С = А\/ (В \/ С) Правило   дистрибутивности   (распределительности).    В   отличие   от алгебры переменных и функций, где за скобки можно выносить только общие множители, в алгебре логики за скобки можно выносить как общие множители, так и общие слагаемые: 1)  дистрибутивность умножения относительно сложения: (А&В) \/ (А&С) = А& (В \/ С) 2) дистрибутивность сложения относительно умножения: (А\/В) & (А \/ С) = А \/ (В&С) Правила равносильности. Это правила отсутствия показателей степени у  результатов логического сложения и умножения переменных. 1) для  логического сложения: 2) для логического умножения: А \/ А = А А & А = А Правила исключения констант. 1) для логического сложения:  2) для логического умножения:  А \/ 1 = 1 А \/ 0 = А А & 1 = А А & 0 = 0 35 36 2.3. ЛОГИЧЕСКИЕ ОСНОВЫ УСТРОЙСТВА КОМПЬЮТЕРА Работа   компьютера   состоит   в   операциях   над   двоичными   кодами   и пересылке этой информации по линиям связи. Средством обработки двоичных сигналов в компьютере являются логические элементы.  Логический   элемент   —  электронная   схема   с   одним   или   несколькими входами   и   одним   выходом,   через   которые   проходят   электрические   сигналы, представляющие цифры 1 и 0; на выходе логический элемент выдает значение логического произведения, логической суммы или отрицания. Для реализации любых логических операций над двоичными сигналами достаточно элементов трех типов, реализующих три основные логические операции — И, ИЛИ, НЕ. 2.3.1. БАЗОВЫЕ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ Базовые логические элементы реализуют три базовые логические операции [12, c. 180­ c. 182]: 1) логический элемент «И» (конъюнктор) — логическое умножение; 2) логический элемент «ИЛИ» (дизъюнктор) — логическое сложение; 3) логический элемент «НЕ» (инвертор) — логическая инверсия. Любая логическая операция может быть представлена в виде комбинации трех базовых, поэтому любые устройства компьютера, производящее обработку или   хранение   информации   (сумматоры   в   процессоре,   ячейки   памяти   в оперативной   памяти   и   др.),   могут   быть   собраны   из   базовых   логических элементов. Логические   элементы   компьютера   оперируют   с   сигналами, представляющими собой электрические импульсы. Есть импульс — логическое значение сигнала 1, нет импульса — значение 0. На вход логического элемента поступают сигналы­элементы, на выходе появляется сигнал­функция. Преобразование   сигнала   логическим   элементом   задается   таблицей 37 состояния,   которая   является   логической функции.   таблицей   истинности,   соответствующей Логический   элемент   «И».  На   входы   А   и   В   логического   элемента последовательно   подаются   4   пары   сигналов,   а   на   выходе   получается последовательность   из   4­х   сигналов,   значения   которых   определяются   в соответствии   с   таблицей   истинности   операции   логического   умножения.   На рисунке 2 изображена логическая схема элемента «И»: Рис.2. Логический элемент «И» Простейшей моделью логического элемента «И» может быть электрическая схема, состоящая из источника тока, лампочки и двух выключателей. Данная схема представлена на рисунке 3:  Рис.3. Электрическая схема модели логического элемента «И» Из схемы видно, что если оба выключателя замкнуты (на обоих входах 1), по   цепи   идет   ток   и   лампочка   горит   (на   выходе   1).   Если   хотя   бы   один выключатель разомкнут (на одном из выходов 0), то тока нет, и лампочка не горит (на выходе 0). Логический   элемент   «ИЛИ»  (рис.4).   На   входы   А   и   В   логического элемента последовательно подаются 4 пары сигналов, а на выходе получается последовательность   из   4­х   сигналов,   значения   которых   определяются   в соответствии с таблицей истинности операции логического сложения.