ответы к экзамену по информатике



1. Информатика — наука о способах получения, накопления, хранения, преобразования, передачи, защиты и использования информации. Она включает дисциплины, относящиеся к обработке информации в вычислительных машинах и вычислительных сетях: как абстрактные, вроде анализа алгоритмов, так и довольно конкретные, например, разработка языков программирования.

Главная функция информатики заключается в разработке методов и средств преобразования информации и их использовании в организации технологического процесса переработки информации.

Задачи информатики состоят в следующем:

исследование информационных процессов любой природы;

разработка информационной техники и создание новейшей технологии переработки информации на базе полученных результатов исследования информационных процессов;

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

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

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

2. Понятие множества является одним из наиболее общих и наиболее важных математических понятий. Оно было введено в математику немецким ученым Георгом Кантором (1845-1918).

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

Другая формулировка принадлежит Бертрану Расселу:

«Множество есть совокупность различных элементов, мыслимая как единое целое».

Виды множеств:

Пустое множество — множество, не содержащее ни одного элемента.

Конечное множество — множество, состоящее из конечного числа элементов.

Бесконечное множество — непустое множество, не являющееся конечным.

Упорядоченное множество — множество, каждому элементу которого поставлено в соответствие некоторое число от 1 до n, где n — число элементов множества, так что различным элементам соответствуют различные числа.

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

3. Операции над множествами:

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

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

Объединение — множество, содержащее в себе все элементы исходных множеств.

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

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

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

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

Абсолютное дополнение

Мощность множества, или кардинальное число множества — это обобщение понятия количества (числа) элементов множества, которое имеет смысл для всех множеств, включая бесконечные.

Множество всех подмножеств (булеан).

4. Свойства операций над множествами:

Объединение и пересечение:

=коммутативность.

=коммутативность.

ассоциативность.

ассоциативность.

дистрибутивность.

дистрибутивность.

идемпотентность.

идемпотентность.

свойство дополнения.

свойство дополнения.

закон де Моргана.

закон де Моргана.

свойство нуля.

свойство нуля.

Дополнение:

инволютивность.

Разность, симметрическая разность:

5. В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

Граф — непустое множество вершин и набор неупорядоченных и упорядоченных пар вершин. Обычно граф обозначают как G(V,E); количество вершин и ребер обозначается, соответственно, n(G) и m(G).

Неупорядоченная пара вершин называется ребром, упорядоченная пара – дугой.

Граф, содержащий только ребра, называется неориентированным. Граф, содержащий только дуги — ориентированным (или орграфом).

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

Граф без кратных рёбер и петель называется простым графом.

Граф, все n вершин которого являются изолированными, называется нулевым (пустым).

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



6. Известно несколько способов представлений графа G=(V, Е) в памяти компьютера.

Матрица смежности — это матрица размером n×n, в которой cij=1, если существует ребро из i в j и cij=0 в противном случае.

Для неориентированного графа справедливо cij=cji и матрица называется симметрической.

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

Основным преимуществом матрицы смежности является тот факт, что за один шаг можно получить ответ на вопрос «существует ли ребро из v в w?».

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

Массив ребер – это массив, в котором ребра хранятся парами вершин, которые они соединяют.

Это наиболее понятный, но достаточно неудобный способ хранения графа. Однако у него есть один большой плюс — при таком способе представления легко вводить дополнительные характеристики ребер. Например, чтобы сохранить веса ребер, достаточно сделать массив размером Mx3 и в дополнительную ячейку для каждого ребра записать его вес.

Если априорно известно, что граф не ориентированный, то включая описание (v, w) не включается описание (w, v).

списки инцидентности.

Для каждой вершины графа создаются три списка:

ü v 0: только неориентированные ребра, инцидентные вершине;

ü v +: исходящие ребра;

ü v -: входящие ребра.

Ели граф ориентирован, то для каждой вершины v достаточно списков v + и v -. Если граф неориентированный, то достаточно списков v 0.

списки смежности.

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



Список смежности более эффективен по сравнению с матрицей смежности, так как исключает хранение нулевых элементов.

7. Большинство задач решается с помощью правила суммы и правила произведения.

Часто удается разбить все изучаемые комбинации на несколько классов, причем каждая комбинация входит в один и только один класс. Ясно, что в этом случае общее число комбинаций равно сумме чисел комбинаций во всех классах. Это утверждение и называется правилом суммы.

Правило суммы: если объект можно выбрать способами, а объект другими способами, то выбор «либо , либо » может быть осуществлен способами.

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

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

8. Размещения с повторениями или выборка с возвращением — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. Комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать.

формула для нахождения количества размещений с повторениями:

Anm=nm

9. Размещения без повторений — комбинаторные соединения, составленные из n элементов по m. При этом два соединения считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

формула для нахождения количества размещений без повторений:

Anm=n!/(n-m)!

10. Перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки.

В теории групп под перестановкой (подстановкой) произвольного множества подразумевается биекция этого множества на себя.

Биекция — это отображение, которое является одновременно и сюръективным(каждый элемент множества Y является образом хотя бы одного элемента множества X) и инъективным(разные элементы множества X переводятся в разные элементы множества Y).

Свойства:

Число всех перестановок порядка n равно числу размещений из n по n, т.е. факториалу:

Pn=Ann=n!=1*2*…*n

Композиция определяет операцию произведения на перестановках одного порядка:

(П*Q)*(k)=П(Q(k))

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

Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент a сопоставляется с перестановкой πa, задаваемой тождеством где g — произвольный элемент группы G, а — групповая операция.

11. Сочетания без повторений — комбинаторные соединения из n элементов по m, составленные из этих элементов и отличающиеся друг от друга только составом.

формула для нахождения количества сочетаний без повторений:

Cnm=n!/m!(n-m)!

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

формула для нахождения количества сочетаний с повторениями:

Cnm=

12. Случа́йное собы́тие — подмножество множества исходов случайного эксперимента; при многократном повторении случайного эксперимента частота наступления события служит оценкой его вероятности.

Случайное событие, которое никогда не реализуется в результате случайного эксперимента, называется невозможным и обозначается символом (о зачеркнутая). Случайное событие, которое всегда реализуется в результате случайного эксперимента, называется достоверным и обозначается символом Ω.

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

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

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

Основным интуитивным понятием классической теории вероятностей является случайное событие.

События, которые могут произойти в результате опыта, можно подразделить на три вида:

Достоверное событие – событие, которое всегда происходит при проведении опыта;

Невозможное событие – событие, которое в результате опыта произойти не может;

Случайное событие – событие, которое может либо произойти, либо не произойти. Например, при броске игральной кости достоверным событием является выпадение числа очков, не превышающего 6, невозможным – выпадение 10 очков, а случайным – выпадение 3 очков.

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

14. Относительной частотой появления случайного события A — называется отношение числа m появлений события A в n испытаниях к общему числу проведенных испытаний:

VA=m/n

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

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

15. С каждым случайным событием A связан случайный эксперимент (опыт). Каждый результат такого эксперимента представляет собой элементарный исход ωi.

Совокупность всех элементарных исходов образует пространство элементарных исходов

Ω={ ωi }.Случайное событие A является подмножеством этого пространства A ⊂ Ω.

Все исходы, входящие в это подмножество являются исходами, благоприятствующими событию A.

Согласно классическому определению, вероятность события A равна отно-

шению числа исходов, благоприятствующих событию A к общему числу исходов:

P(A)=nA/n

Где nA — число исходов, благоприятствующих событию A;

n — общее число исходов.

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

16. Теорема сложения вероятностей: вероятность проявления одного события из нескольких несовместимых событий равна сумме их вероятностей. Вероятность осуществления одного из двух несовместимых событий А и Б:

Р(А или Б)=Р(А)+Р(Б)

Теорема умножения вероятностей: вероятность совместного проявления независимых событий равна произведению их вероятностей. Вероятность двух событий будет:

Р(А и Б)= Р(А) *Р(Б)

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

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

18. Закон распределения в теории вероятностей — собирательный термин, заменяющий такие понятия как распределение вероятностей, функция распределения, плотность распределения, или плотность вероятности.

Законы распределения:

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

В теории вероятностей случайная величина имеет дискретное равномерное распределение, если она принимает конечное число значений с равными вероятностями.

Нормальное распределение (распределение Гаусса) — величина подчиняется нормальному распределению, когда она подвержена влиянию огромного числа случайных помех. Ясно, что такая ситуация крайне распространена, поэтому можно сказать, что из всех распределений, в природе чаще всего встречается именно нормальное распределение — отсюда и произошло одно из его названий.

19. Числовые характеристики, полученные при обработке результатов эксперимента, называются статистическими числовыми характеристиками, или статистическими оценками, или просто оценками.

20. Данные — это представление фактов и идей в формализованном виде, пригодном для передачи и обработки в некотором информационном процессе.

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

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

Информация (от лат. informatio, разъяснение, изложение, осведомленность) — сведения о чем-либо, независимо от формы их представления.

В современной науке рассматриваются два вида информации:

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

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

Информацию можно разделить на виды по разным критериям:

по истинности:

истинная

ложная

по способу восприятия:

Визуальная — воспринимаемая органами зрения.

Аудиальная — воспринимаемая органами слуха.

Тактильная — воспринимаемая тактильными рецепторами.

Обонятельная — воспринимаемая обонятельными рецепторами.

Вкусовая — воспринимаемая вкусовыми рецепторами.

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

Текстовая — передаваемая в виде символов, предназначенных обозначать лексемы языка.

Числовая — в виде цифр и знаков, обозначающих математические действия.

Графическая — в виде изображений, предметов, графиков.

Звуковая — устная или в виде записи передача лексем языка аудиальным путём.

по назначению:

Массовая — содержит тривиальные сведения и оперирует набором понятий, понятным большей части социума.

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

Секретная — передаваемая узкому кругу лиц и по закрытым (защищённым) каналам.

Личная (приватная) — набор сведений о какой-либо личности, определяющий социальное положение и типы социальных взаимодействий внутри популяции.

21.

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

Определение информационных технологий – ИТ, принятое ЮНЕСКО

Согласно определению, принятому ЮНЕСКО, ИТ — это комплекс взаимосвязанных, научных, технологических, инженерных дисциплин, изучающих методы эффективной организации труда людей, занятых обработкой и хранением информации; вычислительную технику и методы организации и взаимодействия с людьми и производственным оборудованием, их практические приложения, а также связанные со всем этим социальные, экономические и культурные проблемы. Сами ИТ требуют сложной подготовки, больших первоначальных затрат и наукоемкой техники. Их введение должно начинаться с создания математического обеспечения, формирования информационных потоков в системах подготовки специалистов.

Информационная система (ИС) – это организационно-упорядоченная взаимосвязанная совокупность средств, и методов ИТ, а также используемых для хранения, обработки и выдачи информации в интересах достижения поставленной цели. Такое понимание информационной системы предполагает использование в качестве основного технического средства переработки информации ЭВМ и средств связи, реализующих информационные процессы и выдачу информации, необходимой в процессе принятия решений задач из любой области.

ИС является средой, составляющими элементами которой являются компьютеры, компьютерные сети, программные продукты, БД, люди, различного рода технические и программные средства связи и т.д. Хотя сама идея ИС и некоторые принципы их организации возникли задолго до появления компьютеров, однако компьютеризация в десятки и сотни раз повысила эффективность ИС и расширила сферы их применения.

Реализация функций ИС невозможна без знания ориентированной на нее ИТ. ИТ может существовать и вне сферы ИС. Таким образом, ИТ является более емким понятием, отражающим современное представление о процессах преобразования информации в информационном обществе. В зависимости от конкретной области применения ИС могут очень сильно различаться по своим функциям, архитектуре, реализации.

Информационный процесс — процесс получения, создания, сбора, обработки, накопления, хранения, поиска, распространения и использования информации.

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

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

22.

Система счисления – это способ представления чисел и соответствующие ему правила действий над числами.

Система счисления – это знаковая система, в которой числа записываются по определенным правилам с помощью символов некоторого алфавита, называемых цифрами.

Система счисления — символический метод записи чисел, представление чисел с помощью письменных знаков.

Система счисления:

даёт представления множества чисел (целых и/или вещественных);

даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление);

отражает алгебраическую и арифметическую структуру чисел.

Системы счисления подразделяются на:

Позиционные — система счисления, в которой значение каждого числового знака (цифры) в записи числа зависит от его позиции (разряда).

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



Страницы: Первая | 1 | 2 | 3 | ... | Вперед → | Последняя | Весь текст




sitemap
sitemap