0: Добрый день, дорогие участники олимпиады газпром, мы очень рады, что вы выбрали наше мероприятие и надеетесь выступить хорошо и повысить свои шансы на зачисление в желаемый вуз.
1: Это замечательно. Мы очень старались подготовить разнообразные интересные вопросы, и сейчас я кратко объясню, какую теорию и какие методы вам желательно повторить перед тем, как
2: Начать приступить к решению задач очного этапа. 1 тема это математическая логика. Здесь приведены портреты людей, благодаря которым у нас появилась мате.
3: Mothica, логика и факты, которые нужно повторить, это что такое высказывание? Это что такое элементарные функции, это функции не более чем
4: 2 переменных. Вот здесь они все перечислены, здесь перечислены примеры, как, как и чем они отличаются. И приведены законы алгебры, логики, которые тут
5: Тоже можете использовать.
6: Также здесь приведён пример построения таблицы истинности то, что вам тоже может пригодиться.
7: Следующая тематика это позиционные системы счисления, которыми мы, собственно, и пользуемся, когда значение цифры зависит от её места или позиции, в числе даны основные определения позиционных систем.
8: Счисления дана основная формула числа в пичной системе счисления. Если вы знаете и понимаете её, вы знаете все и можете решить любую задачу. И на этой формуле основаны алгоритм.
9: Перевода чисел из пичной в десятичную и обратно на этой же формуле основан перевод из десятичной в двоичную систему как частный случай, поскольку здесь коэффициенты принимают
10: Значение только 0 либо единица. И на этой же формуле основан прямой перевод между системами счисления. Например, мы можем перевести число из двоичной системы в восьмиричную или в шестнадцатиричную ми.
11: Десятичную систему.
12: Мы уже затронули двоичную систему, и поэтому нам понадобится двоичный код. И, как известно, в цифровой технике вся информация хранится в двоичном виде. Убито только 2 состояния 0 и 1, и основной.
13: Что нам нужно? Это формула хартли, это как определить длину двоичного кода. Она основана на том, что число двоичных последовательностей длины кк равно 2 в степени к поэтому, например, чтобы
14: Нам закодировать 6 символов. Мы взяли длину коода. Равно 3 таких. Последовательность длины 3 это 8. И на каждый символ мы имеем свой уникальный код.
15: Далее мы переходим не просто к кодированию, а к помехоустойчивому кодированию, потому что когда мы пересылаем и отправляем информацию с 1 устройства на другое, возможны ошибки, то есть некоторые биты могут случайно.
16: И независимо друг от друга инвертироваться, то есть превратиться из нуля в 1 из единицы в 0, и корректирующий код или помехоустойчивый код предназначен как раз для обнаружения исправления подобных.
17: Ошибок и общий метод. Общий принцип этого это введение дополнительной информации. То есть мы кодируем уже не кодом минимальной длины, а мы добавляем какую-то
18: Дополнительную информацию, по которой мы будем судить, ошибка была или нет здесь мы выделили из этих кодов cod бергера, когда
19: Мы вводим контрольные разряды и в контрольных разрядах мы представляем в двоичном виде количество нулей в информационных разрядах нашего слова, которое мы пересылаем. Здесь приведён пример и
20: Приведены примеры сообщения с ошибкой и без ошибки.
21: Далее точно также с двоичным кодом кодом связано хранение изображений, потому что любое изображение растровое хранится попиксельно, а пиксель это код пикселя код.
22: Цвета пикселя это тоже двоичный код и здесь описана хорошо известная техника как хранить растровые изображения и как посчитать необходимое количество бит байт, килобайт для этого хранения.
23: Также нам понадобятся графы, графы это прекрасные модели для того, чтобы описывать объекты и их связи между ними. Здесь приведены основные определения, что такое граф, что такое.
24: Ориентированный граф. И вот здесь, чтобы для понимания картинки, которые показывают применение теории Графов в различных областях, то есть карты, блок, схемы алгоритмов, социальные
25: Thirty можно представить в виде Графов и, конечно, не только это далее также приведены основные определения, приведены способы задания графа как вы можете, граф, хранить, когда вы программируе?
26: Какие-либо алгоритмы на них. То есть это списки смежности, матрица смежности и списки вершин рёбер.
27: Также бывают взвешенные графы, так, секунду взвешенные графы, когда ребра обладают каким-то весом и как модель. Это любые наши перемещения, вес ребра из Москвы в том,
28: Это, например, стоимость билета на самолёт. Далее нужно знать, что такое маршрут в графе, что такое путь, и понимать, что такое минималь.
29: Путь в графи это путь суммарно наименьшей суммы весов, здесь приведены примеры.
30: Вот он. Пример. Особый вид графа. Это дерево. Дерево это связный граф, то есть между любыми 2 вершинами. У нас существует цепь из любой. В любую вершину мы можем пройти и
31: Хорошо известной является задача о кратчайшем соединении городов. Тут у меня не города, тут дома и задача. Стоит как соединить дома с минимальной суммарной длиной путей. То есть представим, что вот эту
32: Деревню завалило снегом, но жители тем не менее, хотят общаться и ходить друг к другу в гости. Но чистить все дорожки это тяжело, как им расчистить минимально дорожки минимальной длины, чтобы все-таки ходить друг к другу в гости. И вот реше
33: Этой задачи называется кратчайшим остовом графа в графах ещё много всего интересного, все не изложишь, много различных задач.
34: Далее в каких-то задачах вам может понадобиться концепция динамического программирования. Это не совсем программирование, это техника оптимизации, не программирование в плане кодинг.
35: Как мы понимаем сейчас это техника решения сложных задач путём разбиения их на более простые задачи. Если мы можем так сделать, если мы можем вот как тут сказано, выделить
36: В большой задаче подзадачи аналогичной структуры, но с меньшим размером, если среди выделенных подзадач есть тривиальные задачи, то есть которые решить очень легко, если оптимальное решение
37: Под задачи большой размерности может быть построена из маленьких. И если мы можем заполнить решение в какие-то Разумных размеров массивы, динамическое программирование нам в этом очень поможет как правило, можно посчитать максимум
38: Минимум. Количество способов. Сумму, например, подсчёт суммы это динамическое программирование. Чтобы просуммировать 5 чисел, нам надо просуммировать 2, потом к ним прибавить 3, 4 и так дальше.
39: Здесь приведены примеры на одномерную динамику, когда задача зависит от 1 параметра. И вот как её можно вычислять и на двумерную динамику, когда задача зависит от 2 параметров.
40: Далее предлагаем вам вспомнить базы данных. Собственно, что такое база данных? Это какой-то структурированный набор данных, хранящийся в виде таблиц.
41: И цель базы данных, чтобы мы могли оптимально, эффективно хранить информацию, её извлекать, её преобразовывать и так далее. Поэтому в базах данных у нас приведены-таки
42: И у нас разработаны нормальные формы, которые помогают прийти к оптимальной структуре базы данных. И тут у нас приведены примеры этих нормальных форм, и как при
43: И описаны проблемы, которые решаются с помощью нормальных форм. Здесь рассмотрена 1, 2 и 3 нормальная форма. Вот 1 приведение таблицы к нормальной форме. Далее мы её же привели.
44: Ко 2 и далее к 3 таблице в нормальной форме. В результате у нас получается из 1 таблицы несколько, но этими несколькими таблицами гораздо удобнее управлять и работать с ними.
45: Вот краткая шпаргалка.
46: Наша следующая тема это комбинаторика. Для нас это означает подсчёт количества различных комбинаций, которые можно составить из некоторого множества объектов, когда мы выби.
47: Из некоторого дискретного множества. То есть получается в нашем множестве есть какой-то набор отделимых объектов. Например, это могут быть цифры 1, 2, 3 или вот как здесь приведены примеры.
48: Далее с фруктами, с уроками. И так дальше здесь работают. Главное это 2 правила, правило суммы. Когда мы выбираем объект а н способами, а б м способами, то если мы выбираем
49: Объект а. Или б. То есть какой-то 1 из данных объектов, мы выбираем его n плюс m. Способами выборы не должны пересекаться и правило произведения, если объект, а можно выбрать н.
50: Способами и после каждого такого выбора объект б можно выбрать м способами, то для пары а и б есть н умножить на м способов выбора. Вот тут пример нам из столовой, если у нас 4/1 и 3/2 блю.
51: Когда мы берём 1 блюдо, у нас 7 вариантов, а когда 2 блюда, 1 и 2, то 4 * 3, 12 вариантов. И вот основные комбинаторные объекты, это у нас их 3, это
52: Перестановки с повторениями и без повторений перестановки как следует из названия, мы переставляем наши объекты, как представлено на рисунке перестановки с повторе.
53: Если, допустим, вот такой пример сколько различных последовательностей можно получить, переставляя буквы в слове молоко, если я тут переставляю буквы о красную, жёлтую, зелёную, слово моё не меняет.
54: Это надо учитывать при подсчёте данных комбинаций. Здесь есть общие формулы, желательно их, конечно, не только запомнить, но и понимать, как они работают и когда, какую применить.
55: Размещение, например, сколькими способами можно разместить 3 человек из 5 на пьедестале почёта здесь нам важны только первые 3 человека, которые выиграли медали, а остальные могут стоять в любом порядке.
56: Размещения тоже могут быть с повторениями и без вот это размещение без повторений, потому что 1 человек занимает Ровно 1 место.
57: А вот у нас размещение с повторениями, если мы составляем расписание уроков, у нас 7 уроков, но уроки могут, быть может, могут повторяться.
58: И сочетание. В сочетаниях. Нам не важен порядок, а важен состав набора. Например, сколькими способами можно выбрать 3 фрукта из 7 на завтрак. Тут не важен порядок выбора. Они в результате лежат все на 1 тарелочке и
59: Есть также сочетания с повторениями, которые тоже тут разобраны. Ну и вот такой вопрос на задуматься, чего больше размещений, перестановок или сочетаний, чего меньше?
60: Ну и следующая тема последняя у нас это электронные таблицы. Здесь я затруднилась изложить теорию кратко, зато нашла несколько ссылок. В принципе, что нужно понимать при работе, как её открыть, электронную таблицу.
61: Как там обработать данные, то есть вычислить какие-то функции, как вставить функции, что такое абсолютная относительная адресация, как можно упорядочить, да?
62: Как можно построить диаграмму, ну и прочие вещи, которые, в общем то, являются базовыми для работы в таблицах. Но если вы не захотите работать с электронными таблицами, вы можете, конечно же, написать
63: Программу. И для этого файл из электронной таблицы вам нужно просто сохранить. В текстовом формате. Эта возможность имеется во всех электронных таблицах. В целом это очень кратко, та
64: Теория, которая может вам пригодиться. Возможно вам пригодится что-то ещё. Возможно что-то из этого вы не будете использовать, но это та база, которая в общем то нужна, если вы хотите знать.