Информационные модели на графах

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

Алгоритм построения графа в виде дерева

1. Нарисовать главную вершину - корень, которая не зависит  ни от одной другой вершины.
2. Добавить вершины 2-го уровня. Их может быть сколько угодно, и все они обязательно связаны с корнем, но не связаны между собой.
3. Добавить вершины 3-го уровня. Каждая из них должна быть связана ровно с одной вершиной 2-го уровня.
4. На каждом шаге добавляем вершины очередного уровня, каждая из которых будет связана ровно с одной вершиной предыдущего уровня и не будет иметь никаких иных связей.

Моделирование и формализация - тест

Классификация моделей

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

Посмотреть, повторить, решить задачи, ответить на вопросы.

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

Диаграммы Венна

Упростите логические выражения

Домашнее задание по теме "Законы и тождества алгебры логики"

1. Упростить выражения:

•     1) не(не А или В или С) или А и не (В и С)
•     2). не(А и В или не (А и В)) и не( не А и не В или А и не В)
•     3). (А либо В) и (В либо С)

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

F(x, y, z) = (xy + xz + yz) х

Космическое путешествие

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

Онлайн-игра 

Постройте таблицы истинности - тренинг

Отношения между понятиями

Домашнее задание:
1. Прочитать теоретический материал.
2. Электронная тетрадь Отношения между понятиями, множествами
3. Являются ли следующие понятия совместимыми: 

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

4. Определите вид отношения между следующими понятиями и изобразите его с помощью кругов Эйлера: 

• а)  школа, образовательное учреждение; 
• б) Ю. Гагарин; первый человек, полетевший в космос;
• в) русский писатель, автор поэмы "Мертвые души", писатель;
• г) президент, президент России, глава государства;
• д) художественная литература, литература, драматургия;
• е) отец, сын, мужчина, дедушка.

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

• а) А — ученый, В — писатель, С — общественный деятель;
• б) А — участник отечественной войны 1812 года, В — генерал, С — гусар; 
• в) А — автор романа "Мастер и Маргарита", В — писатель, С — русский писатель;
• д) А — еженедельник, В — периодическое издание, С — газета "Ведомости".

Для определения вида отношений между понятиями по объему нужно: 

1) соотнести представление об объеме понятия с кругами Эйлера; 

2) если дано несколько понятий, определить сначала отношение между двумя, а затем присоединять по-одному остальные.

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

Сложные высказывания

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

ПРОСТОЕ  высказывание (логическая переменная)  - высказывание, в котором ни одна  его часть сама не является высказыванием.

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

Мы часто используем сложные высказывания в речи, например:

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

Какие связки мы используем при построении сложных высказываний?

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

• Конъюнкция – И, логическое умножение.
• Дизъюнкция – ИЛИ, логическое сложение
• Отрицание   - НЕ
• Импликация – логическое следование
• Эквиваленция – логическое тождество

Любое сложное высказывание можно записать с помощью основных логических операций И, ИЛИ, НЕ.

Порядок выполнения логических операций

 1) операции в скобках;

 2) отрицание;

 3) логическое умножение;

 4) логическое сложение;

 5) импликация;

 6) эквиваленция.

Формы и законы мышления

Скульптура головы Аристотеля

1. Выучить определения

• Формы и законы мышления

2. Ответить на вопрос письменно в тетрадях: 

• как  и в каких сферах применяются законы логики в информатике.

Способы решения содержательных логических задач

Отношения между понятиями

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

Всякое понятие имеет содержание и объем. Содержанием понятия называется совокупность существенных признаков одноэлементного класса или класса однородных предметов, отраженных в этом понятии. Содержанием понятия “квадрат” является совокупность двух существенных признаков: “быть прямоугольником” и “иметь равные стороны”.

Объемом понятия называют совокупность (класс) предме­тов, которая мыслится в понятии. Объективно, т. е. вне созна­ния человека, существуют различные предметы, например, школьники. Под объемом понятия “школьник” подразумевает­ся множество всех школьников, которые существуют сейчас, су­ществовали ранее и будут существовать в будущем. Класс (или множество) состоит из отдельных объектов, которые называ­ются его элементами. В зависимости от их числа множества делятся на конечные и бесконечные. Например, множество сто­лиц государств конечно, а множество натуральных чисел беско­нечно. Множество (класс) А называется подмножеством (под­классом) множества (класса) В, если каждый элемент А является элементом В. Такое отношение между подмножеством А и множеством В называется отношением включения класса А в класс В и записывается так: А c В. Читается: класс А входит в класс В. Это отношение вида и рода (например, класс “стол” входит в класс “мебель”).

Отношение принадлежности элемента а классу А записыва­ется так: а є А. Читается: элемент а принадлежит классу А. Например, а - “Нева” и А - “река”.

Классы А и В являются тождественными (совпадающими), если А c В и В c А, что записывается как А=В.

Закон обратного отношения между объемами и содержаниями понятий

В этом законе речь идет о понятиях, находящихся в родо­видовых отношениях. Объем одного понятия может входить в объем другого понятия и составлять при этом лишь его часть. Например, объем понятия “хищная рыба” целиком входит в объ­ем другого, более широкого по объему понятия “рыба” (состав­ляет часть объема понятия “рыба”). При этом содержание пер­вого понятия оказывается шире, богаче (содержит больше при­знаков), чем содержание второго. 

На основе обобщения такого рода примеров можно сформулировать следующий закон: чем шире объем понятия, тем уже его содержание, и наоборот. Этот закон называется законом обратного отношения между объе­мом и содержанием понятия. Он указывает на то, что чем меньше информации о предметах, заключенной в понятии, тем шире класс предметов и неопределеннее его состав (например, “водопад”), и наоборот, чем больше информации в понятии (например, “крупный водопад” или “крупный водопад в Канаде”), тем уже и определеннее круг его предметов, или даже мыслится только один предмет.

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

Сравнимые понятия делятся по объему на совместимые (объемы этих понятий совпадают полностью или частично) и несовместимые (их объемы не имеют общих элементов).

Типы совместимости:

равнозначность (тождество), перекрещивание,

подчинение (отношение рода и вида)

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

Решение логических задач с помощью графов

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

Если нужно представить, что к-тый участник соревнования занял n-е место ( или, что то же самое, n-е место занял к-тым участником), это можно изобразить так:

Задача N1

Марина, Лариса, Жанна и Катя умеют играть на разных инструментах( пианино, виолончели, гитаре, скрипке), но каждая только на одном. Они же знают иностранные языки (английский, французский, немецкий и испанский), но каждая только один. Известно:

1. Девушка, которая играет на гитаре говорит по-испански.
2. Лариса не играет ни на скрипке ни на виолончели и не знает английского языка.
3. Марина не играет ни на скрипке, ни на виолончели и не знает ни немецкого, ни английского.
4. Девушка, которая говорит по-немецки, не играет на виолончели.
5. Жанна знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Решение:

Из пятого условия, что Жанна знает французский язык, рисуем стрелку. Из третьего условия, что Марина не знает ни немецкого, ни английского, а французский знает Жанна, то Марина знает испанский и рассматривая первое условие, определяем, что она играет на гитаре. Из условия N2 видим, что Лариса играет на пианино, т.к. Марина играет на гитаре, а на других инструментах она играть не умеет, и значит, она говорит по-немецки.


Т.к. Жанна не играет на скрипке, то остается один инструмент, на котором она может играть это виолончель. Тогда Катя играет на скрипке, и знает английский язык.

Источник (ссылка)

Кодирование звука

Тест

Книжная полка

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

Играть...

Цикл while. Вариант 1

Основы алгоритмизации и программирования

Вариант 1

№ 1. Определите, что будет напечатано в результате выполнения программы, записанной ниже на языке программирования Pascal:

var k, s: integer;

begin

   k:=9; s:=43;

   while s >= 0 do begin

      k:= k – 1;

      s:= s – 2 * k

   end;

   writeln(k);

end.

№ 2. Определите, что будет напечатано в результате выполнения программы, записанной ниже на языке программирования Pascal:

var k, s: integer;

begin

   k:=5; s:=4;

   while s >= 0 do begin

      k:= k – 1;

      s:= s + k;

   end;

   writeln(k);

end.

№ 3. Определите, что будет напечатано в результате выполнения программы, записанной ниже на языке программирования Pascal:

var n, s: integer;

begin

   n:=0;

   s:=50;

   while s >= 15 do begin

      s:= s – 3;

      n:= n + 1;

   end;

   writeln(n)

end.

№ 4. Определите, что будет напечатано в результате выполнения программы, записанной ниже на языке программирования Pascal:

var n, s: integer;

begin

   n:=1;

   s:=1;

   while s < 20 do begin

      s:= s * 2;

      n:= n + 3;

   end;

   writeln(n)

end.

№ 5. Определите значение переменной Х после выполнения фрагмента программы:

x:=1; y:= -20;

while x + y < 0 do begin

   x:= x * 2;

   y:= y + 2

end;

№ 6. Определите значение переменной Y после выполнения фрагмента программы:

x:=100; y:=1;

while x - y > 0 do begin

   x:= x - y;

   y:= y * 2

end;

№ 7. Определите значение переменной Y после выполнения фрагмента программы, записанной на языке программирования Pascal:

x:=25; y:= -20;

while x * y < 0 do begin

   x:= x – 5;

   y:= y + 2

end;

№ 8. Определите значение переменной Y после выполнения фрагмента программы, записанной на языке программирования Pascal:

x:= -25; y:= -20;

while x * y > 0 do begin

   x:= x + 5;

   y:= y + 3

end;

№ 9. Определите, что будет записано в результате работы следующего фрагмента программы:

s:=0; x:=3; k:=1;

while s < 100 do begin

   s:= s + x * k;

   k:= k + 1

end;

writeln(k);

№ 10. Определите, что будет напечатано в результате работы следующего фрагмента программы:

s:= 0; x:= 1; k:= 1;

while s < 100 do begin

   s:= s + x * k;

   k:= 2 * k

end;

writeln(s);

Ответы: №1 – 5, №2 – (-5), №3 – 12, №4 – 16, №5 – 16, №6 – 64, №7 – (-10), №8 – (-5), №9 – 9, №10 – 127.

Файлы и файловая система

Файлы и файловая система

Измерение и кодирование информации

Домашнее задание "Измерение информационного объема текстового сообщения"