Информа́тика (фр. informatiqueангл. computer science) — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений[1].

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

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

Литература

Алгоритмы — это сердце и душа computer science. Без них не обойтись, они есть везде — от сетевой маршрутизации и расчетов по геномике до криптографии и машинного обучения. «Совершенный алгоритм» превратит вас в настоящего профи, который будет ставить задачи и мастерски их решать как в жизни, так и на собеседовании при приеме на работу в любую IT-компанию. В этой книге Тим Рафгарден — гуру алгоритмов — расскажет об асимптотическом анализе, нотации большое-О, алгоритмах «разделяй и властвуй», рандомизации, сортировки и отбора. Книга «Совершенный алгоритм» адресована тем, у кого уже есть опыт программирования. Вы перейдете на новый уровень, чтобы увидеть общую картину, разобраться в низкоуровневых концепциях и математических нюансах.
Познакомиться с дополнительными материалами и видеороликами автора (на английском языке) можно на сайте www.algorithmsilluminated.org.

  • Умножение Карацубы.

KARATSUBA
Вход: два n-значных положительных целых числа, x и y.
Выход: произведение x × y.
Допущение: n является степенью числа 2.
if n = 1 then // базовый случай
вычислить x × y за один шаг и выдать результат
else // рекурсивный случай
a, b := первая и вторая половины x
c, d := первая и вторая половины y
вычислить p := a + b и q := c + d, используя арифметическое сложение,
рекурсивно вычислить ac := a × c, bd := b · d и pq := p × q
вычислить adbc := pq – ac − bd, используя арифметическое сложение,
вычислить 10^n × ac + 10^n/2 × adbc + bd, используя арифметическое сложение, и выдать результат.

  • Алгоритм MergeSort

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

MERGESORT
Вход: массив A из n разных целых чисел.
Выход: массив с теми же самыми целыми числами, отсортированными от наименьшего до наибольшего.
// базовые случаи проигнорированы
C := рекурсивно отсортировать первую половину A
D := рекурсивно отсортировать вторую половину A
вернуть Merge (C, D)

MERGE
Вход: отсортированные массивы C и D (длиной n/2 каждый).
Выход: отсортированный массив B (длиной n).
Упрощающее допущение: n — четное.
1 i := 1
2 j := 1
3 for k := 1 to n do
4 if C[i] < D[j] then
5 B[k] := C[i] // заполнить выходной массив
6 i := i + 1 // прирастить i
7 else // D[j] < C[i]
8 B[k] := D[j]
9 j := j + 1

Оценка времени исполнения алгоритма MergeSort

Для каждого входного массива длиной n ≥ 1 алгоритм MergeSort выполняет не более 6n log2 n + 6n операций, где log2 обозначает логарифм по основанию 2.

Асимптотические обозначения (Asymptotic Notation). Суть - устранить постоянные коэффициенты и члены низших порядков.

T(n)  - предел худшего времени исполнения алгоритма как функцию длины n входных данных

Определение O(n)

T(n) = О (f(n)), тогда и только тогда, когда T (n) в конечном итоге ограничена сверху постоянной, кратной функции f(n)
T(n) = О (f(n)), тогда и только тогда, когда существуют положительные константы c и n0, такие что T(n) ≤ с × f(n) для всех n ≥ n0

Алгоритм QuickSort

QUICKSORT (ВЫСОКОУРОВНЕВОЕ ОПИСАНИЕ)
Вход: массив A из n разных целых чисел.
Выход: элементы массива A отсортированы от наименьшего до наибольшего.
if n ≤ 1 then // базовый случай – уже отсортирован
return
выбрать опорный элемент p // предстоит реализовать
разделить A вокруг p // предстоит реализовать
рекурсивно отсортировать первую часть A
рекурсивно отсортировать вторую часть A

QuickSort (High-Level Description)
Input: array A of n distinct integers.
Postcondition: elements of A are sorted from smallest to largest.
if n ≤ 1 then // base case-already sorted
return
choose a pivot element p // to-be-implemented
partition A around p // to-be-implemented
recursively sort first part of A
recursively sort second part of A

QUICKSORT
Вход: массив A из n разных целых чисел, левая и правая конечные точки, ℓ, r ∈ {1, 2, …, n}.
Постусловие: элементы подмассива A[ℓ], A[ℓ + 1], …, A[r] отсортированы от наименьшего до наибольшего.
if ℓ ≥ r then // 0- или 1-элементный подмассив
return
i := ChoosePivot(A, ℓ, r) // предстоит реализовать
обменять A[ℓ] с A[i] // сделать опорный первым
j := Partition(A, ℓ, r) // j = новая опорная позиция
QuickSort(A, ℓ, j − 1) // рекурсивно вызвать с первой частью
QuickSort(A, j + 1, r) // рекурсивно вызвать со второй частью

  • Рафгарден Тим Р26 Совершенный алгоритм. Графовые алгоритмы и структуры данных. — СПб.: Питер, 2019. — 256 с.: ил. — (Серия «Библиотека программиста»). ISBN 978-5-4461-1272-2

 

 

Добавить комментарий