История, предмет, структура информатики
Представление и измерение информации. Типы информации, единицы измерения информации.
Представление и измерение информации. Формула Хартли. Формула Шеннона. Методы получения информации.
Кодирование и шифрование информации. Криптология, криптография, кодирование.
Кодирование и шифрование информации. Стеганография. Типы шифров.
Кодирование и шифрование информации. Принцип Кирхгоффа. Электронная цифровая подпись.
Типы вирусов.
Системы счисления и действия в них.
Особенности систем счисления Китая, Японии, Индии и России
Высказывания и предикаты. Предикаты, логические функции, таблицы истинности.
Тавтологии, силлогизмы и парадоксы
Исполнители алгоритмов - человек и автомат. Примеры автоматов.
Устройство компьютера. Память, регистры. Принципы фон-Неймана, архитектура фон-Неймана.
Устройство компьютера. Системная плата, процессор. Классификация компьютеров.
Программное и техническое обеспечение. Структура ПО.
Программное и техническое обеспечение. Операционная система, файловая система.
Программное и техническое обеспечение. Прикладное ПО. Автономные программы, библиотеки программ, пакеты прикладных программ.
История вычислительных машин до XX века (Шиккард, Лейбниц, Паскаль, Бэббидж)
История компьютеров в XX веке, поколения компьютеров
Интернет
Кибернетика
Искусственный интеллект
Информационное общество
Нужно уметь решать следующие виды задач:
1. Перевод единиц измерения информации. Решение систем уравнений.
2. Перевод из 2,8 и 16 систем счисления в 10. Обратный перевод, промежуточные переводы.
3. Алгебра логики
4. Решение информационно-логических задач.
5. Программы для роботов
Ответы:
1) Информатика - фундаментальная научная и образовательная область, которая не может ограничиться рамками инженерных, пользовательских трактовок, рамками процедурного программирования, имея мощный формальный аппарат для глубокого изучения явлений и систем, их практической интерпретации, усиления междисдисциплинарных связей.
Предпосылки: информатика – наука об информации
История
- предмет для ведения счета
-речь
-знаковые системы
-письменность
Термин возник в 1980 гг. во Франции для названия области, занимающейся автоматизированной обработкой информации с помощью ЭВМ: информатика=информация+автоматика
Информатика – методологическая наука об информационных процессах, о моделях, алгоритмах, о программах программирования, об исполнителях алгоритмов и различным исполняющих системах об их использовании в обществе, в природе, в познании.
Структура
-теоретическая информатика(языковое)
-прикладная(практическая)
-техническая
Предметная информатика: медицинская, физическая, компьютерная физика, химическая
Роли: мировоззренческая(вникать в суть явления), воспитательная (выработка подходов), культурная речь (повышение информационной и компьютерной культуры), эстетическая роль.
3) Представление и измерение информации. Формула Хартли. Формула Шеннона. Методы получения информации.
Информация – некоторая упорядоченная последовательность сообщений, отражающих, передающих и увеличивающих наши знания.
Формула Хартли
H=log2N (бит)
Пусть известны N состояний системы S. Каждое состояние - двоичный код длины d. 2d>=N. d>=log2N
Формула Шеннона
I = -SUMni=2 pi log2pi
n- число состояний системы
pi – вероятность перехода системы в i-е состояние, а сумма всех pi должна =1
Методы получения информации
-эмпирические (получение эмп. данных)
-теоретические (построение теорий)
-смешанные (построение теорий на основе полученных эмпирических данных об объекте, процессе, явлении)
2)
Информация – некоторая упорядоченная последовательность сообщений, отражающих, передающих и увеличивающих наши знания.
Типы информации:
К источнику (Входная, Выходная, внутренняя)
К конечному результату (исходная, промежуточная, результирующая)
По изменчивости(постоянная, переменная, смешанная)
По стадии использования(первичная,вторичная)
По полноте(избыточная,достаточная,недостаточная)
По доступу к ней(открытая,закрытая)
Единиц
1 бит – 0 или 1
1 байт 8
1 килобайт 213
1 мегабайт 223
1 гигабайт 233
1 терабайт 243
4) Кодирование – процесс преобразования букв(слов) алфавита Х в буквы(слова) алфавита У.
Шифрование – процесс преобразования открытого сообщения.
Если А – открытое сообщение; В – закрытое(шифр), f- правило шифрования
f(A)=B
Криптология – наука о тайне. Вопросы сокрытия и защиты информации
Криптография – построение и исследование математических методов преобразования информации (тайнопись)
Кодирование – процесс преобразования букв(слов) одного алфавита в другой
5) Кодирование и шифрование информации. Стеганография. Типы шифров.
Кодирование – процесс преобразования букв(слов) алфавита Х в буквы(слова) алфавита У.
Шифрование – процесс преобразования открытого сообщения.
Если А – открытое сообщение; В – закрытое(шифр), f- правило шифрования
f(A)=B
Стеганография – тайнопись, письмо условными шифрованными знаками
Типы шифров:
-шифр перестановки – изменится только порядок символов исходного сообщения
-шифр замены – заменяет каждый символ на другой, текст не меняет
6) Кодирование – процесс преобразования букв(слов) алфавита Х в буквы(слова) алфавита У.
Шифрование – процесс преобразования открытого сообщения.
Если А – открытое сообщение; В – закрытое(шифр), f- правило шифрования
f(A)=B
Принцип Кирхгоффа
Секретность зашифрованных сообщений определяется секретностью ключа
-даже если известен алгоритм, нужен ключ
-только полный перебор
-в российских шрифтах 256-битовый ключ
Электронная цифровая подпись – присоединяемое к тексту его криптографическое преобразование, которое позволяет при получении текста др пользователями проверить авторство и подлинность.
7) Типы вирусов
-загрузочные
-аппаратно-вредные
-программные
-стелс-вирусы (маскируют)
-макровирусы
-многоцелевые
-полиморфные
Широкое распространение компьютеров, а так же бурное развитие сети Интернет способствовало к появлению и распространению маленьких вредоносных программ – вирусов. Вирусы порой делают работу на компьютере невозможной. Они, в зависимости от ситуации могут нанести значительный ущерб как информации, так и даже самому компьютеру.
Что такое вирус
Компьютерный вирус – это специальная программа, как правило, очень маленького размера, способная внедряться в тело другой программы, перехватывать управление этой программой, саморазмножаться (распространяться) и внедряться в другие программы с задачей дестабилизации работы компьютера и порче информации.
Как вирус проникает в компьютер
Вирусы попадают на жесткий диск компьютера или его оперативную память (загрузочные вирусы) через носимые хранилища данных – гибкие дискеты (fdd), CD(DVD)-диски, карты флэш-памяти, но больше всего вирусов приходит из всемирной паутины. Вирусы пишут как энтузиасты одиночки, так и целые организации (группы хакеров). Они могут преследовать различные цели, но результат почти всегда одинаков – потерянные (испорченные, и даже украденные) данные. В некоторых случаях, после воздействия вирусов, несутся огромные денежные убытки. И хотя вирусописание и вирусораспространение во многих странах считается преступлением, это не спасает ситуацию в целом и с каждым годом вредоносных программ становиться все больше и больше.
Чаще всего вирусы поражают загрузочный сектор диска (как жесткого, так и гибкого) и исполняемые файлы с расширением exe, com, sys, bat.
Классификация вирусов
Сегодня число известных вирусов уже перевалило пятитысячную отметку. Вирусы принято классифицировать:
1. По среде обитания:
- сетевые вирусы (они распространяются по разным компьютерным сетям);
- файловые вирусы (заражают исполняемые файлы программ – com, exe, bat.);
- загрузочные вирусы (заражают загрузочный сектор диска (boot-sector) или сектор, содержащий программу загрузки системного диска – Master Boot Record);
- файлово-загрузочные (действуют так же как и загрузочные вирусы)
2. По способу заражения:
- резидентные (такой вирус при инфицировании ПК оставляет в оперативке свою резидентную часть, которая потом перехватывает обращение ОС к объектам заражения и поражает их. Резидентные вирусы живут до первой перезагрузки ПК);
- нерезидентные (не заражают оперативную память и могут быть активными ограниченное время)
3. По результату воздействия:
- неопасные (как правило эти вирусы забивают память компьютера путем своего размножения и могут организовывать мелкие пакости – проигрывать заложенную в них мелодию или показывать картинку);
- опасные (эти вирусы способны создать некоторые нарушения в функционировании ПК – сбои, перезагрузки, глюки, медленная работа компьютера и т.д.);
- очень опасные (опасные вирусы могут уничтожить программы, стереть важные данные, убить загрузочные и системные области жесткого диска, который потом можно выбросить)
4. По алгоритму работы:
- паразитические (меняют содержимое файлов и секторов диска. Такие вирусы легко вычисляются и удаляются);
- мутанты (их очень тяжело обнаружить из-за применения в них алгоритмов шифрования. Каждая следующая копия размножающегося вируса не будет похожа на предыдущую);
- репликаторы (вирусы-репликаторы, они же сетевые черви, проникают через компьютерные сети, они находят адреса компьютеров в сети и заражают их);
- троянский конь (один из самых опасных вирусов, так как трояны не размножаются, а воруют ценную (порой очень дорогую) информацию – пароли, банковские счета, электронные деньги и т.д.);
- невидимки (это трудно обнаружимые вирусы, которые перехватывают обращения ОС к зараженным файлам и секторам дисков и подставляют вместо своего незараженные участки.
8) Системы счисления и действия в них
Система счисления – это правило записи чисел. Символы, при помощи которых записываются числа в данной системе счисления, называются цифрами. Совокупность всех цифр называется алфавитом системы счисления.
Множество символов, используемых для такого представления, называют цифрами.
На данный момент самой популярной является десятичная система счисления. Она к нам пришла из Индии. Возникла не позднее 6 века нашей эры.
Ещё существует шестидесятеричная система счисления. Но она была неудобна в использовании и поэтому не широко распространилась.
Наиболее распространенными являются позиционные системы счисления.
Определение. Система счисления называется позиционной, если значение каждой цифры в записи числа определяется ее положением (позицией) в данной записи.
В привычной нам десятичной с/с значение числа образуется умножением значения каждой цифры на вес соответствующего разряда и последующим суммированием всех таких произведений. Например, 32710 = 3×102+23×101+3×100.
Определение. Последовательность чисел, задающая веса соответствующих разрядов цифр в с/с, называется базисом данной системы.
Определение. Позиционная с/с называется традиционной, если ее базисом является геометрическая последовательность с знаменателем p Î N. Знаменатель прогрессии p называется основанием системы счисления. Систему счисления с основанием p будем называть p -ричной.
-Алфавит Х из Р символов и правила записи (изображения) и обработки числе с помощью символов этого алфавита
-Число Х в системе с основанием Р обозначается как ХР
-Система кодирования величин
-Р - основание системы; Х – число
-Хn=XnPn+Xn-1Pn-1…X1P1+X0P0
-Двоичная над алфавитом Х={0;1}
-Восьмеричная Х={0;1;2;3;4;5;6;7}
-Шестнадцатеричная Х={0;1;2;3;4;5;6;7;8;9;A;B;C;D;E;F}
Действия:
Из десятичной – отдельно целую, отдельно дробную
Перевод целой части: делить целую часть Х10 потом частное на Р, пока частное не меньше Р
Перевод мантиссы: последовательно умножать на число Р
Умножать до тех пор, пока не получим мантиссу 0 или нужное Хр
ХР приписывается к целой части первого произведения второй такой же цифры.
Обратный код: 10011 --- 01100
Дополнительный код: обратный код+единица в младшем разряде
10) Высказывания и предикаты. Предикаты, логические функции, таблицы истинности
Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать истинно оно или ложно.
Предикаты – Высказывательная форма с логическими переменными, имеющая смысл при любых допустимых значениях этих переменных; Кол-во переменных называется его местностью; простые высказывания или предикаты не зависят от др высказываний или предикатов; сложное зависит хотя бы от 2 простых.
Логическая функция (булевая) – f(x) функциональная зависимость, в которой
Аргумент х– логическая переменная с заданным множеством изменений арг.
а значения функции f(x) берутся из двухэлементного множества R(f)={0,1}
Таблица истинности
| x | y | -x | x A y | x V y |
20) Internet является глобальной информационной сетью, объединяющей множество сетей. Internet не однородная сеть, это - группа из многих тысяч индивидуальных, корпоративных, региональных и т.п. сетей, объединенных для свободной передачи информации любому пользователю сети. Поток документов, войдя в Internet через индивидуальную сеть, проходит через ряд корпоративных и региональных сетей и достигает адресата.
В 1961 году Advanced Research Agensy (DARPA) по заданию министерства обороны США приступила к проекту по созданию экспериментальной сети передачи пакетов данных. Эта сеть, названная ARPANET, предназначалась первоначально для изучения методов обеспечения надежной связи между компьютерами различных типов.В 1969 году министерство обороны утвердило ARPANET в качестве ведущей организации для исследований в области компьютерных сетей. В 1970 году хосты ARPANET стали использовать для обмена NCP(Network Control Protocol).В начале 1971 года в сети было уже 15 узловПервые международные подключения к ARPANET были осуществлены в 1973 году, когда к сети подключились машины из Англии и Норвегии. В 1975 году ARPANET превратилась из экспериментальной сети в рабочую сеть В 1976 году в ATT Bell Labs был разработан протокол UUCP, а в 1979 году запущена USENET, которая работала на основе UUCP. В 1983 году министерство обороны США объявило TCP/IP своим стандартом. Было объявлено, что ARPANET закончила исследовательскую стадию. Из ARPANET выделилась MILNET, которая стала относиться к Defence Data Network(DDN) министерства обороны США. Термин Internet стал использоваться для обозначения единой сети: MILNET плюс ARPANET. В 1987 году число хостов превысило 10000. В 1988 году сеть NSFNET стала использовать канал T1(1,544 Мбит/с.). B 1999 году вошла в строй новая глобальная сеть - Internet 2 Internet Assigned Numbers Authority(IANA), оказывающая основное воздействие на организацию технической базы функционирования глобальной Сети, одобрила вариант перехода на новую систему IP-адресов
11) Тавтологии, парадоксы и силлогизмы с точки зрения алгебры логики
Определение. Формула алгебры высказываний F (X1, X2,..., Xn) называется
тавтологией, или тождественно истинной, если она превращается в истинное
высказывание при всякой подстановке вместо переменных конкретных высказываний
A1, A2,..., An, т.е. если λ(F (A1, A2,..., An)) = 1 для любого набора высказываний
A1, A2,..., An.
Обозначение. |= F (X1, X2,..., Xn) — формула F (X1, X2,..., Xn) является
тавтологией.
Пример тавтологии:
((X → Y) ∧ (X → Y)) → X
Проверка
Теорема. Следующие формулы алгебры высказываний являются тавтологиями:
(1) закон исключенного третьего P ∨ P;
(2) закон отрицания противоречия (P ∧ P);
(3) закон двойного отрицания P ↔ P;
(4) закон тождества P → P
(5) закон контрапозиции (P → Q) ↔ (Q → P);
(6) закон силлогизма (правило цепного заключения) ((P → Q) ∧ (Q → R)) → (P → R);
(7) закон противоположности (P ↔ Q) ↔ (P ↔ Q);
(8) правило добавления антецедента P → (Q → P);
(9) правило "из ложного что угодно" P → (P → Q);
(10) правило "modus ponens" (P ∧ (P → Q)) → Q;
(11) правило "modus tollens" ((P → Q) ∧ Q) → P;
(12) правило перестановки посылок (P → (Q → R)) ↔ (Q → (P → R));
(13) правило объединения посылок (P → (Q → R)) ↔ ((P ∧ Q) → R);
(14) правило разбора случаев ((P → R) ∧ (Q → R)) ↔ ((P ∨ Q) → R);
(15) правило приведения к абсурду ((P → Q) ∧ (P → Q)) → P;
(16) законы поглощения (P ∧ (P ∨ Q)) ↔ P, (P ∨ (P ∧ Q)) ↔ P;
(17) законы де Моргана (P ∧ Q) ↔ (P ∨ Q), (P ∨ Q) ↔ (P ∧ Q);
Правила получения тавтологий
1. Правило заключения.
Теорема. Если формулы F и F → H являются тавтологиями, то формула H
также является тавтологией.
2. Правило подстановки.
Определение. Пусть в формуле F содержится пропозициональная переменная X
и H — произвольная формула. Если в формулу F везде вместо символа X вставить
формулу H, то получим новую формулу, которая называется формулой, полученной из
F в результате подстановки в нее формулы H вместо переменной X.
В широком смысле парадокс — это положение, резко расходящееся с общепринятыми, устоявшимися, ортодоксальными мнениями.
Парадокс в более узком и специальном значении — это два противоположных, несовместимых утверждения, для каждого из которых имеются кажущиеся убедительнымиаргументы.
Наиболее резкая форма парадокса — антиномия, рассуждение, доказывающее эквивалентность двух утверждений, одно из которых является отрицанием другого.
Особой известностью пользуются парадоксы в самых строгих и точных науках — математике и логике.
Варианты парадокса «Лжеца»
Наиболее известным и, пожалуй, самым интересным из всех логических парадоксов является парадокс «Лжец».
Имеются варианты этого парадокса, или антиномии, многие из которых являются только по видимости парадоксальными.
В простейшем варианте «Лжеца» человек произносит всего одну фразу: «Я лгу». Или говорит: «Высказывание, которое я сейчас произношу, является ложным». Или: «Это высказывание ложно».
Если высказывание ложно, то говорящий сказал правду, и значит, сказанное им не является ложью. Если же высказывание не является ложным, а говорящий утверждает, что оно ложно, то это его высказывание ложно. Оказывается, таким образом, что, если говорящий лжет, он говорит правду, и наоборот.
В средние века распространенной была такая формулировка:
— Сказанное Платоном — ложно, — говорит Сократ.
— То, что сказал Сократ, — истина, — говорит Платон.
Возникает вопрос, кто из них высказывает истину, а кто ложь?
Ходит даже легенда, что некий Филит Косский, отчаявшись разрешить этот парадокс, покончил с собой. Говорят также, что один из известных древнегреческих логиков, Диодор Кронос, уже на склоне лет дал обет не принимать пищу до тех пор, пока не найдет решение «Лжеца», и вскоре умер, так ничего и не добившись.
Теперь «Лжец» — этот типичный бывший софизм — нередко именуется королем логических парадоксов. Ему посвящена обширная научная литература.
Простой категорический силлоги́зм — рассуждение, состоящее из трёх простых атрибутивных высказываний: двух посылок и одного заключения. Посылки силлогизма разделяются на бо́льшую (которая содержит предикат заключения) и меньшую (которая содержит субъект заключения). По положению среднего термина силлогизмы делятся на фигуры, а последние по логической форме посылок и заключения — на модусы.
Пример силлогизма:
Всякий человек смертен (бо́льшая посылка)
Сократ — человек (меньшая посылка)
Сократ смертен (заключение)
Структура простого категорического силлогизма
В силлогизм входит ровно три термина:
§ S — меньший термин; P — больший термин; M — средний термин.
Подлежащие S (субъект) — то, относительно чего мы высказываем (делится на два вида):
1. Определенное: Единичное, Частное, Множественное
§ Единичные [суждения] — в которых подлежащее является индивидуальным понятием. Прим: «Ньютон открыл закон тяготения»
§ Частное суждение — в котором подлежащим суждения является понятие, взятое в части своего объема. Прим: «Некоторые S суть P»
§ Множественное суждение — это те, в которых несколько подлежащих классовых понятий. Прим: «насекомые, пауки, раки есть членистоногие»
2. Неопределенное. Прим: «светает», «больно» и т. п.
Сказуемое P (предикат) — то, что мы высказываем (2 вида суждений):
§ Повествовательные — это суждение относительно событий, состояний, процессов или деятельности скоропроходящих. Прим: «Роза в саду цветет».
§ Описательные — когда одному или многим предметам приписывается какое-нибудь свойство. Субъектом всегда является определенная вещь. Прим: «Огонь горяч», «снег бел».
