Множество.

Множество — это любой набор (коллекция, совокупность) любых объектов, выбранных по некоторому правилу. Объекты, составляющие множество, называются элементами множества.

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

Множество называется пустым, если в нём нет ни одного элемента.

Множества одинаковые (равные между собой) — они состоят из одних и тех же элементов.

Все пустые множества одинаковые.

Будем говорить, что А — подмножество В, если каждый элемент множества А является элементом множества В.

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

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

Последовательность.

Последовательность – набор объектов с заданным порядком следования — какой- то объект ставится первым, затем выбирается второй объект, и так объекты выстраиваются друг за другом.

Объекты, выстроенные в последовательность, называются членами этой последовательности.

В последовательности могут встречаться одинаковые элементы.

Слово ‑ любая последовательность букв.

Последовательность может быть пустой. Длина такой последовательности — 0.

Последовательность и цепочка — это одно и то же.

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

Все пустые последовательности — одинаковые.

Последовательности разные, если среди них нет двух одинаковых.

Элементы разные, если среди этих элементов нет двух одинаковых. Так, в любом множестве все элементы разные.

Все множества разные, если среди данных множеств нет двух одинаковых.

Истинные и ложные утверждения.

Значения «это утверждение истинно», «это утверждение ложно» мы будем называть истинностными значениями утверждений.

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

Площадь многоугольника на сетке.

Единичный квадрат — это самый маленький квадрат, который можно нарисовать на сетке.

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

Площади одинаковых многоугольников равны.

Площадь прямоугольного треугольника на сетке.

Треугольник, в котором есть прямой угол, называется прямоугольным.

Треугольник на сетке, две стороны которого идут вдоль линий сетки, является прямоугольным.

Разрезав единичный квадрат по диагонали, получим два равных треугольника площадь каждого из которых, равна половине площади единичного квадрата.

Пересечение и объединение множеств.

Пересечением множеств называется множество, состоящее из всех их общих элементов.

Объединением множеств называется множество всех элементов, которые есть хотя бы в одном из этих множеств.

Сортировка: упорядочение и группировка.

В информатике сортировкой называется наведение порядка в некотором наборе объектов.

Упорядочение ‑ расположение всех объектов в последовательность по определённому, удобному для нас правилу.

Группировка ‑ объединение объектов по определённому правилу.

При составлении словарей обычно слова располагают в словарном (лексикографическом) порядке. Общее правило словарного порядка выглядит так:

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

2. Если у двух слов первые буквы одинаковые, то сравним вторые буквы: если эти буквы разные, то раньше будет идти то слово, вторая буква которого идёт раньше в алфавите.

3. Если и вторые буквы у двух слов одинаковые, то сравним третьи буквы: если эти буквы разные, то раньше будет идти то слово, третья буква которого идёт раньше в алфавите.

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

Словари.

Словарь — это справочная книга, которая содержит слова, расположенные в определённом порядке.

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

Словари — не просто сборники слов, а собрания каких-то специальных сведений о словах.

Дерево.

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

Элементы в дереве называются вершинами. В дереве за одной вершиной может следовать сразу несколько вершин. Но каждая вершина дерева имеет не больше одной предыдущей вершины.

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

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

Путь дерева

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

Родители и дети.

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

Уровень вершины.

Будем говорить, что корневые вершины дерева — это вершины нулевого уровня. Дети корневых вершин — это вершины первого уровня, дети вершин первого уровня — это вершины второго уровня и так далее.

Для любого натурального числа K дети вершин уровня K — это вершины уровня K+1.

Число уровней дерева мы будем называть высотой дерева. Высота дерева равна самой большой длине пути этого дерева.

Дерево перебора вариантов

Деревья перебора вариантов ‑ построение множества всех возможных вариантов какого-либо процесса, не потеряв ни одного из вариантов и не добавив лишних.

Поиск кратчайшего пути.

Графом называется набор точек (вершин графа), некоторые из которых соединены линиями (рёбрами графа).

Каждое дерево является графом — ведь в дереве тоже есть вершины, и они соединены линиями. Эти линии в дереве тоже называются рёбрами.

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

Игры с полной информацией.

Игроки — это участники игры.

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

Ход игры изменяет позицию. Игроки делают ходы поочерёдно. Первый ход всегда делает Первый.

Начальная позиция — это позиция, которая имеется перед началом игры.

Заключительная позиция — такая ситуация в игре, после которой игра продолжаться не может.

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

Правила игры:

1.     описывают начальную позицию;

2.     определяют, какие ходы возможны в игре;

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

Дерево игры.

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

Каждый путь дерева игры является последовательностью одной из возможных партий игры. Множество всех путей дерева — это множество всех возможных в данной игре партий.

Выигрышная стратегия.

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

Выигрышные и проигрышные позиции.

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

Назовём позицию проигрышной, если любой ход из неё оставляет противнику выигрышную позицию.

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

Если начальная позиция выигрышная, то выигрышную стратегию имеет Первый, если проигрышная — Второй.

Равновесные выигрышные стратегии.

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

Биоинформатика.

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

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

Звенья белковых цепей называют аминокислотными остатками.

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

Все молекулы ДНК, как и молекулы белков, — это цепочки, но звенья в молекулах ДНК отличаются от звеньев белков.

Звенья ДНК называются нуклеотидами. В молекулах ДНК встречается всего 4 вида нуклеотидов. Молекулы ДНК в клетках живых организмов гораздо длиннее молекул белков. Нуклеотиды обозначаются латинскими буквами А, С, G и Т.

Молекулы ДНК каждого живого организма полностью определяют, какие белки будут в этом организме.

Замена каждой буквы её кодом называется шифрованием. Обратная замена каждого кода на соответствующую ему букву называется расшифровкой.

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

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

Каждый из двадцати возможных остатков имеет своё название и обозначается одной латинской буквой.

Все молекулы ДНК построены только из четырёх видов нуклеотидов. Вот их русские и английские назва­ния и буквы, которыми они обозначаются: аденин (Adenine, А), цитозин (Cytosine, С), гуанин (Guanine, G), тимин (Thymine, Т).

Не вся молекула ДНК кодирует белки, а только некоторые её участки, которые называются генами.

В гене (как и в наших шифровках) каждый остаток белка кодируется тройкой нуклеотидов. Такие тройки биологи называют кодонами. Например, тройка AAG (аденин—аденин‑гуанин) кодирует остаток лизин.

Генетический код един для всех известных живых организмов!

Первая тройка в любом гене — ATG (она называется старт-кодоном). Кодон ATG — это кодон остатка метионина (этот остаток обозначается буквой М), поэтому этот кодон встречается и внутри генов. Последняя тройка в каждом гене — это ТАА, TAG или TGA. Эти кодоны называются стоп-кодонами, они играют такую же роль, как точки в предложении. Стоп-кодоны не кодируют никакого остатка, внутри генов они не встречаются.

Таблица генетического кода.

Обратная таблица генетического кода.