Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Затверджено на методичній нараді кафедри

Читайте также:
  1. Зав. кафедри
  2. Зав. кафедри
  3. Зав. кафедри
  4. Зав. кафедри
  5. Зав. кафедри
  6. Завідувач кафедри
  7. Завідувач кафедри інформатики та ТЗН
  8. Завідувач кафедри Т.О. Андрєєва
  9. Завідувач кафедри теорії і
  10. ЗАВІДУЮЧИЙ КАФЕДРИ

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

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

Каждый базовый алгоритм, как и метод сведения к нему содержит широкий круг разнообразных методов, связанных собственной “иерархией”. Ниже приводится их краткая характеристика.

Алгоритмы поиска. Любой алгоритм нахождения решения c` уравнения

Ф(c)=y

представляет собой последовательность действий на основе системы тестов и может быть описан как алгоритм поиска элемента c` в массиве К. В криптографической литературе под алгоритмами поиска нередко понимают узкий класс алгоритмов поиска - метод последовательного перебора (метод тотального опробования), в соответствии с которым опробуются поочередно в некотором порядке элементы c множества К. Для каждого опробуемого варианта c вычисляется yc=Ф(c) и сравнивается c y по критерию на совпадение. При принятии решения о несовпадении yc с y опробуемый вариант c отбраковывается. При известной структуре (частичной структуре) множества К применяют “упорядоченный”, “направленный” перебор элементов из К. Так, например, при структуре множества “больше - меньше”:

у12<...<у|К|

для нахождения номера заданного элемента y сравнивают y с со средней точкой у[|W|/2] массива и выбирают ту половину его, в которой лежит y, затем сравнивают y со “средней точкой” выбранного “половинного массива” и так далее до идентификации элемента y. Число операций такого способа оценивается величиной log2К. Иногда удается сгруппировать элементы массива в “легко различимые” между собой группы и вначале определять номер группы, в которой лежит y, а затем определять номер y, ведя поиск y в этой выделенной группе. Сократить число операций при структуре ключей «больше – меньше» возможно, если использовать предварительную кодировку у-ов и «удобно» расположить у-ки в соответствии с их адресами (см. Зубков А.М., Клыкова Н.В. Построение баз данных с ограниченным временем поиска. Симпозиум по прикладной и промышленной математике. Тезисы доклада. 2001г. стр. 185-186).

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

Алгоритмы решения систем линейных и нелинейных уравнений над различными алгебраическими структурами (поля, кольца и т.д.). Для решения систем линейных уравнений в этих структурах существует широкий круг известных “стандартных” алгоритмов, таких как - алгоритмы Гаусса, Штрассена, Коновальцева для решения общих систем линейных уравнений над конечными полями и кольцами; - алгоритмы решения некоторых специальных систем линейных уравнений, например, ганкелевых систем или систем с разреженной матрицей. Из алгоритмов решения систем нелинейных уравнений отметим алгоритм Лазера.

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

Методы частичного опробования. В методах этого класса пытаются «разбить» ключ c на две части c1,c2 и представить его в виде c=(c1,c2) таким образом, чтобы при каждом варианте c1 уравнение Ф(c1,c2)=y относительно c2 решалось достаточно «просто», например, с трудоемкостью меньшей чем полный перебор возможных значений c2. При выполнении этих условий решают уравнение Ф(c1,c2)=y перебором возможных вариантов c`1 с последующим решением уравнения Ф(c`1,c2)=y для каждого опробуемого варианта c`1. Примером такого метода служит метод решения нелинейных булевых уравнений путем линеаризации за счет опробования части переменных.

Методы последовательного опробования. Этот метод является развитием метода частичного опробования. В этом методе так же пытаются «разбить» ключ c на две части c1,c2 и представить его в виде c=(c1,c2) таким образом, чтобы при каждом варианте c1 для уравнения Ф(c1,c2)=y относительно c2 достаточно «просто», устанавливалось разрешимо оно или нет. Если при варианте c`1 оно неразрешимо относительно c2, то вариант c`1 отбраковывается и опробуется следующий вариант. В случае же положительного ответа уравнение Ф(c`1,c2)=y пытаются решить всеми возможными средствами, например, пытаются применить метод частичного опробования для части c2, всего ключа c. В последнем случае и говорят о применении метода последовательного опробования.

Методы сведения к базовым алгоритмам основаны:

- на преобразовании как уравнений, так и множества неизвестных; на использовании различных моделей алгебраических структур (гомоморфные образы автоматов, алгебр, их приближенные модели и т.д.);

- на использовании частичного и последовательного опробования.

Неизвестные параметры c1,c2,…,cn - части ключа c, относительно которых решается уравнение, могут быть заданы в различной форме, влияющей как на выбор способов решения уравнения так и на их сложность. Так, например, подстановка может быть задана в обычной двухстрочной форме, или в матричной форме; двоичная функция может быть задана таблично, в виде многочлена Жегалкина, в виде вектора ее коэффициентов Фурье по любому базису n-мерного векторного пространства над полем вещественных чисел или над конечным полем и т.д. Собственно сам метод сведения к базовым алгоритмам и состоит в выборе способа представления, «кодирования» частей ключа.

Преобразования уравнений шифрования. Многие методы преобразования системы уравнений шифрования нацелены на получение уравнений – следствий, которые могут быть решены известными способами. Например, подбирают множество У` совместно с отображением j: Y®Y`, так чтобы новое уравнение - следствие

j(Ф(c))=j(y)

решалось достаточно просто. Найдя все множество М решений этого уравнения, решают, относительно cÎМ, начальное уравнение Ф(c)=y, например, опробуя элементы множества М. К таким методам относятся так называемые “методы сведения”: выделение из системы уравнений

Фt(c1,c 2,…,c n)=yt, tÎ{1,…,T}

«хороших уравнений», например линейных, или выделение уравнений, из которых можно составить систему уравнений «треугольного типа» и т.д.

Преобразование неизвестных. Один из способов преобразования неизвестных состоит в поиске нового множества К` и отображений j: К®К`, y: К`®Y, так чтобы Ф(c)=y(j(c)). В этом случае задача поиска решения уравнения Ф(c)=y сводится к решению двух уравнений

y(c`)=y,

j(c)=c`.

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

Методы использования гомоморфизмов. Итак, мы изучаем возможности

определения прообраза c отображения Ф: К®У по известному образу у=Ф(c).

Ищутся такие подходящие множества К` и У` и отображения j: К®К`, y:Y®Y`, f:К`®Y`, чтобы была коммутативна следующая диаграмма:

Ф

К ® У

 

j ¯ ¯ y

 

К` ® Y`

f

Сначала решается уравнение f(c`)=y`, относительно c`ÎК` при у`=y(y). Это уравнение называют гомоморфным образом уравнения Ф(c)=y.

Затем для каждого найденного решения c` решается уравнение j(c)=c`. Обозначим через М все найденные таким образом решения (объединение всех решений уравнения j(c)=c` по всем решениям c` уравнения f(c`)=y`). Далее решают начальное уравнение Ф(c)=y относительно cÎM.

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

Наряду с использование базисных алгоритмов и методов сведения к ним при решении задачи определения ключа нередко используют и дополнительные предположения, облегчающие расчет параметров эффективности используемого метода решения. Например, предполагают, что решение уравнения Ф(c)=y единственно, в частности, используемый шифр не имеет эквивалентных ключей, объем T материала больше расстояния единственности шифра.

Затверджено на методичній нараді кафедри

пропедевтики внутрішньої медицини № 1

«26» серпня 2014 р., протокол № 1/14

 

ТЕМАТИЧНИЙ ПЛАН ЛЕКЦIЙ

з пропедевтики внутрiшньої медицини

для студентів III курсу медичного факультету № 2

на осiнньо – зимовий семестр 2014/2015 року

 

(тривалість лекції – 2 академічні години)

 

N п/п Тема лекцiї Групи 1–17, 36–37 Групи 18–35 Лектор
Модуль 1. «Основні методи обстеження хворих в клініці внутрішніх хвороб»
1. Пропедевтика внутрішньої медицини як введення у клініку внутрішніх хвороб. Основні методи обстеження хворих. Анамнестична частина історії хвороби 02.09.2014 03.09.2014 проф. Нетяженко В.З. доц. Плєнова О.М.
2. Огляд хворого та його значення в діагностичному процесі 09.09.2014 12.09.2014 проф. Нетяженко В.З. доц. Плєнова О.М.
3. Симптоми при захворюваннях органів дихання на підставі розпитування хворого, огляду хворого та пальпації грудної клітки 16.09.2014 17.09.2014 проф. Нетяженко В.З. проф. Мальчевська Т.Й.
4. Симптоми при захворюваннях органів дихання на підставі перкусії грудної клітки та аускультації легень 23.09.2014 26.09.2014 проф. Нетяженко В.З. проф. Мальчевська Т.Й.
5. Симптоми та синдроми на підставі дослідження пульсу та артеріального тиску 30.09.2014 01.10.2014 проф. Нетяженко В.З. доц. Дідківська Л.А.
6. Основні симптоми на підставі розпитування та огляду хворого із серцево-судинною патологією 07.10.2014 10.10.2014 проф. Нетяженко В.З. доц. Плєнова О.М.
7. Аускультація серця: основні симптоми при вислуховуванні нормальних та патологічних тонів серця. 14.10.2014 15.10.2014 проф. Нетяженко В.З. доц. Дідківська Л.А.
8. Аускультація серця: органічні та функціональні серцеві шуми 21.10.2014 24.10.2014 проф. Нетяженко В.З. доц. Плєнова О.М.
9. Основні синдроми при захворюваннях органів дихання 28.10.2014 29.10.2014 проф. Нетяженко В.З. проф. Мальчевська Т.Й.
10. Основні синдроми при захворюваннях та функціональних розладах травного тракту 04.11.2014 07.11.2014 проф. Нетяженко В.З. проф. Шкала Л.В.
11. ЕКГ-метод обстеження в діагностиці патології серця. ЕКГ ознаки порушень збудливості серця. 11.11.2014 12.11.2014 проф. Нетяженко В.З. доц. Плєнова О.М.
12. Комбіновані порушення серцевого ритму Клінічні та ЕКГ-ознаки миготіння та тріпотіння передсердь і шлуночків 18.11.2014 21.11.2014 проф. Нетяженко В.З. доц. Дідківська Л.А.
13. Інструментальні методи дослідження серцево-судинної системи 25.11.2014 26.11.2014 проф. Нетяженко В.З. асист. Горач Н.В.
Модуль 2: „Симптоми та синдроми при захворюваннях внутрішніх органів”
14. Мітральні вади серця: основні симптоми та синдроми на підставі фізикального та інструментального дослідження хворого 02.12.2014 05.12.2014 проф. Нетяженко В.З. проф. Мальчевська Т.Й.
15. Аортальні вади серця: основні симптоми та синдроми на підставі фізикального та інструментального дослідження хворого 09.12.2014 10.12.2014 проф. Нетяженко В.З. проф. Мальчевська Т.Й.
16. Основні симптоми та синдроми при артеріальній гіпертензії. Сучасні підходи до класифікації та діагностики артеріальної гіпертензії 16.12.2014 19.12.2014 проф. Нетяженко В.З. доц. Плєнова О.М.
17. Ішемічна хвороба серця: основні клінічні симптоми та синдроми при стенокардії та інфаркті міокарда 23.12.2014 24.12.2014 проф. Нетяженко В.З. асист. Нетяженко Н.В.
18. Основні клінічні прояви синдромів серцевої та судинної недостатності 13.01.2014 09.01.2014 проф. Нетяженко В.З. доц. Мальчевська Т.Й.
  Всього годин      
Час проведення лекції 8.20–10.00 8.20–10.00

 

 

Місце проведення лекцій: 1–17, 36–37 групи – фізико-хімічний корпус, аудиторія № 3

18–35 групи – фізико-хімічний корпус, аудиторія № 2

 

 

Завідувач кафедри пропедевтики

внутрiшньої медицини №1,

член-кор. НАМН України, професор В.З.Нетяженко




Дата добавления: 2014-12-20; просмотров: 35 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав