Основная статья: Идиома copy-and-swap

Обмен значениями (swap)

Основная статья: Идиома copy-and-swap

Бесконечный цикл

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

for (;;) {

do_something();

}

5)Выборка из ассоциативного массива: Во многих языках имеется реализация ассоциативного массива, т. е. хеш-таблица.

Критика: Автор книги «Learn Ruby The Hard Way» Зед Шоу отмечает, что отношение к идиомам в сообществах разработчиков говорит о том, что применение идиом следует отнести к категории нравов, так как при письме на естественном языке, требующем чёткости изложения, идиом следует избегать.

 

3.Привести пример метода, вычисляющего среднее арифметическое от одномерного массива.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace tester

{

class Program

{

public static double sred (double[] arr)

{

int n = arr.Length;

double sum=0;

for (int i=0;i<n;i++)

sum+=arr[i];

return sum / n;

}

static void Main(string[] args)

{

double[] arrtest = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

Console.WriteLine("Среднее значение массива = "+ sred(arrtest));

Console.ReadKey(); }

}

}

Алгоритмы поиска: последовательный, двоичный, метод золотого сечения, интерполяционный.

а)Последовательный

1)i=1

2)Смотрим i-й элемент. То, что нужно?

3)Если нет то i=i+1 и возвращаемся к пунтку 2

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

б)Двоичный:

Проверяем средний элемент, если не подходит, то отбрасываем половину массива..

Проверяем средний элемент в оставшейся половине, если не подходит то отбрасываем половину от оставшихся…

в)Метод золотого сечения:

f(x):[a;b]→min, f(x)ϵC([a;b])

Делим отрезорк двумя симметричными точками и вычисляем в них функцию.

Отбрасываем тот отрезок Где значение функции максимально по модулю

На оставшемся отрезке нужно добавить только одну точку

Продолжаем…

 

 

 

г) Интерполирующий

Public int interpolationSearch (int [] SortedArray, int toFind) {

//Возвращает индекс элемента со значением toFind

//иначе возвращает -1

Int mid;

Int low=0;

Int high = SortedArray.Length-1;

While (sortedArray[low]<toFind && sortedArray[high]>toFind) {

Mid = low + ((toFind – sortedArray[low])*(high-low))/(sortedArray[high]-sortedArray[low])

If (sortedArray[mid]<toFind)

Low =mid+1;

Else if(sortedArray[mid>toFind])

High=mid-1;

Else return mid;

}

If (sortedArray[low]==toFind)

Return low;

Else if (sortedArray[high]==toFind)

Return high;

Else return -1;

}

 

Алгоритмическая сложность в среднем O(log(log N))

В худшем случае O(N)

Вообщем принцип работы такой, в цикле мы проверяем нахождения нашего элемента с значением toFind, но рассматриваем не весь массив а только массив лежащий в границах low и high постепенно мы сужаем эти границы и так доходим до этого элемента, но в основном цикле мы не рассматриваем элемента которые лежат на границе массива, поэтого после его завершения если ничего мы не нашли то мы проверяем самый первый и самый последние элемента, если находим то возвращаем его индекс, если не находим то возвращаем -1

 

Сортировка расчёской

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

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

 

Void sort (data* array, dword size) {

Dword jump = size;

Bool swapped = =true;

While (jump>1 || swapped)

{

If(jump > 1)

Jump = (dword)(jump/1.25);

Swapped = false;

For (dword i =0; i+jump < size; i++)

If (array[i] > array[i+jump])

Swap(array,i,i+jump), swapped = true }

}

 

 

 

Сортировка слиянием.

Для решения задачи сортировки эти три этапа выглядят так:

Сортируемый массив разбивается на две части примерно одинакового размера;

Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;

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

 

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

 

2.1 Cоединение двух упорядоченных массивов в один.

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

2.2. Слияние двух подмассивов в третий результирующий массив.

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

2.3. "Прицепление" остатка.

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

 

Быстрая сортировка.

Быстрая сортировка часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Краткое описание алгоритма:

1)выбрать элемент, называемый опорным.

2)сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.

3)повторить рекурсивно для «меньших» и «больших».

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

/* сортирует v[0]..v[n-1] по возрастанию */

Void quicksort (int v[], int n)

{

Int i, last;

If (n <= 1) //ничего не делать

Return;

Swap (v,0,rand()%n);//разделить

Last=0;

For (i=1; i<n; i++)

If (v[i] < v[0])

Swap(v,++last,i);

Swap(v,0,last) //сохранить разделитель

Quicksort (v,last); //рекурсивно отсортировать

Quicksort (v+last+1,n-last-1)//каждую часть}

Двоичное дерево поиска:

1)Оба поддерева - левое и правое, являются двоичными деревьями поиска.

2)У всех узлов левого поддерева произвольного узла Х значения ключей данных меньше, нежели значение ключа данных узла Х.

3)У всех узлов правого поддерева произвольного узла Х значение ключей данных больше, нежели значение ключа данных узла Х.

Красно-чёрное дерево (англ. Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих:

1) Логарифмический рост высоты дерева от числа узлов.

2) Быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла.

Свойства красно-чёрного дерева:

1. Узел либо красный, либо чёрный.
2. Корень всегда чёрный
3. Все листья (NIL) — черные.
4. Оба потомка каждого красного узла — черные.
5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.
6. Путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа.

Вставка нового элемента:

1)Добавление узла как и в обычном BST

2)Окрашивание его в красный

Далее N- текущий красный узел, P - предок N, G - дедушка N, U - дядя N.

Вставка нового элемента(продолжение) Сценарий 1: N - корень дерева. Решение: перекрасить его в чёрный.

void

insert_case1(struct node *n)

{ if (n->parent == NULL)

n-> color = BLACK;

else insert_case2(n);}

 

Вставка нового элемента(продолжение) Сценарий 2: предок P - черный. Решение: дерево действительно.

void

insert_case2(struct node *n)

{ if (n->parent-color == BLACK)

return;

else insert_case3(n);}

 

Вставка нового элемента(продолжение) Сценарий 3: родитель -P и дядя U- красные,а дедушка G-черный. Решение: перекрасить родителей в черный,а дедушку в красный.

Вставка нового элемента(продолжение) Сценарий 4: родитель P - красный, но дядя U-черный.N-правый/левый потомок Р,а Р в свою очередь - левый/правый потомок своего предка G. Решение: поворот дерева на Р, и запуск сценария 5 для Р.

Вставка нового элемента(продолжение) Сценарий 5: родитель P - красный, но дядя U-черный.N-левый/правый потомок Р,а Р в свою очередь - правый/левый потомок своего предка G. Решение: поворот дерева на G, замена цветов Р и G.

 

RSA

RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи.

В качестве открытых параметров системы были использованы числа n=1143816...6879541 (129 десятичных знаков, 425 бит, также известно как RSA-129 и e=9007

Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:

• Если известно , то вычислить относительно просто
• Если известно , то для вычисления нет простого (эффективного) пути.

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

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

 

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

Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема.

 

Служб.

Обычное приложение

Основной код подключаемые библиотеки

Приложение с web-service

Клиентская часть Серверная часть (подключаемые библиотеки)

^internet

 

Web служба - это... 1)Идентифицируемая web-адресом программная система со стандартизованными интерфейсом.

2)Web-службы могут быть использованы практически в любом сценарии, так как они не ограничены конкретной технологией (безопасности, управления или транспортировки)

 

Для чего нужны web-службы? 1)В2В-транзакции, соединение внутренних систем отдельных компаний.

2)Готовые модули для разработчиков.

3)компонентные библиотеки DLL для многократного использования кода.

4)Защита от пиратского копирования ПО.

XML: Расширяемый язык разметки, предназначенный для хранения и передачи структурированных данных;

SOAP: Протокол обмена сообщениями на базе XML;

WSDL: Язык описания внешних интерфейсов веб-службы на базе XML;

UDDI: Универсальный интерфейс распознавания, описания и интеграции (Universal Discovery, Description and Integration). Каталог веб-служб и сведений о компаниях, предоставляющих веб-службы во всеобщее пользование или конкретным компаниям.

Пример использования Web-служб: создание настраиваемой веб-службы ASP.NET

В этой задаче программирования представлен обзор создания пользовательской веб-службы, действующей в контексте Microsoft SharePoint Foundation. Рассматривается процесс создания простой веб-службы "Hello World" в Microsoft Visual Studio 2010 и показывается, как можно изменить эту веб-службу для внедрения объектной модели SharePoint Foundation на стороне сервера для возвращения данных сайта и списка.

 

 

Обмен значениями (swap)

Основная статья: Идиома copy-and-swap

Бесконечный цикл

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

for (;;) {

do_something();

}

5)Выборка из ассоциативного массива: Во многих языках имеется реализация ассоциативного массива, т. е. хеш-таблица.

Критика: Автор книги «Learn Ruby The Hard Way» Зед Шоу отмечает, что отношение к идиомам в сообществах разработчиков говорит о том, что применение идиом следует отнести к категории нравов, так как при письме на естественном языке, требующем чёткости изложения, идиом следует избегать.

 

3.Привести пример метода, вычисляющего среднее арифметическое от одномерного массива.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace tester

{

class Program

{

public static double sred (double[] arr)

{

int n = arr.Length;

double sum=0;

for (int i=0;i<n;i++)

sum+=arr[i];

return sum / n;

}

static void Main(string[] args)

{

double[] arrtest = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

Console.WriteLine("Среднее значение массива = "+ sred(arrtest));

Console.ReadKey(); }

}

}