Главная » Все файлы » Просмотр файлов из архивов » Документы » Темы выносимые на зачет (САОД)

Темы выносимые на зачет (САОД)

2017-07-08СтудИзба

Описание файла

Документ из архива "Темы выносимые на зачет (САОД)", который расположен в категории "". Всё это находится в предмете "введение в специальность" из 1 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "к экзамену/зачёту", в предмете "введение в специальность" в общих файлах.

Онлайн просмотр документа "Темы выносимые на зачет (САОД)"

Текст из документа "Темы выносимые на зачет (САОД)"

САОД, семестр 1

Темы выносимые на зачет в 1 семестре:

Абстрактный тип данных

1.1. Типы, структуры данных и АТД

1.2. Время выполнения программы

1.3. Асимптотическое соотношение

1.4. О - символика

1.5. О и W - обозначения

1.6. Ограниченность показателя функции роста

1.7. Анализ программы на псевдоязыке

Абстрактный тип данных в списках

2.1. Реализация АТД. Линейный список

2.2. Сравнение последовательного и связанного распределения

Структура данных на основе линейных списков

3.1. Стек, очередь, дек

3.2. Реализация стека, дека и очереди на основе ЛСС (Линейного связанного списка)

3.3. Реализация Дека

Не линейная структура данных

4.1. АТД дерево

4.2. Порядок узлов

4.3. Прямой, обратный и симметричный обход

4.4. Помеченные деревья или деревья выражений

4.5. Префиксные коды. Код Хаффмана.

Сортировки

5.1. Классификация алгоритма сортировки

5.2. Постановка, задача сортировки

5.3. Методы сортировок

5.4. Типы сортировок

5.5. Критерии оценки сортировок

5.6. Простые схемы сортировок

5.7. Простая вставка

5.8. Алгоритм Шелла

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

5.10. Оценка эффективности быстрой сортировки

5.11. Пирамидальная сортировка. Выбор из дерева

5.12. Сортировка подсчетом

5.13. Распределяющий подсчет

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

6.1. ЕДС - единственное двухпутевое слияние

6.2. ФДС - фиксированное двухпутевое слияние

7. Хеширование: открытое и закрытое. Оценка эффективности и трудоемкости. Коллизии и методы их разрешения при закрытом хешировании.

Абстрактные типы данных

«Математика» САОД Программирование

Абстрактный тип данных – это математическая модель с совокупностью операторов или операций определенных в рамках данной модели. Абстрактным типам данных соответствует понятие класса в объектно-ориентированном программирование. К АТД применимы понятия инкапсуляции, абстрагирования (обобщение), наследования:

1. Абстракция или обобщение в том смысле, что АТД можно рассматривать как обобщение типа данных.

2. Наследование применимо в том смысле, что одни абстрактные типы данных могут быть реализованы новые АТД, реализация которых уже осуществлена в базовых АТД.

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

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

Типы, структуры данных и АТД

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

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

1) массив

2) структура данных. (struct, record)

3) Файл

Заметим, что 1 и 2 механизм реализует произвольный доступ к ячейкам (модель с произвольным доступом данных), а файлы – последовательный доступ.

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

Время выполнения программы

С точки зрения жизненного цикла ПО можно выделить следующие временные отрезки:

1. Разработка

2. Тестирование, отладка

3. Эксплуатация

4. Сопровождение

Из этих четырех этапов наиболее дорогостоящие являются этапы 1,2,3, которые выполняют программисты, так как время работы программиста стоит намного дороже себестоимости выполнения программы на компьютере. Кроме того время работы программы намного меньше времени работы программиста над программой. Из двух программ программист выберет ту, которая наиболее проще для понимая, сопровождения, зачастую не обращая внимания на эффективность реализации. В теории сложности алгоритма рассматривают методы анализа и способы построения алгоритмов время выполнения, которых может заранее определено (в том числе и на основе исходного текста программ). Например, можно определить множество задач, которые на одном исходном наборе работают за исходное время, а на другом наборе данных по длине время год, день и события. Поэтому при выборе алгоритма кроме себестоимости разработки и поддержки необходимо обращать внимание на сложность в смысле вычислительной трудоемкости алгоритмов.

  1. Время ввода исходных данных, эффективность кода.

  2. Оптимизация кода компилятора с учетом ОС и архитектуры ЭВМ.

  3. Архитектура ЭВМ машинного кода (инструкция), аппаратно ускоряющее время выполнения кода.

  4. Временная сложность алгоритма, соответствующей программы.

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

Время выполнения программы…

Время выполнения алгоритма…

Число инструкций определяется как исходными данными, так и структурой алгоритма. Однако набор исходных данных программиста – аналитика остается неизвестным, поэтому мы имеем время алгоритма как функцию от исходных данных. Причем эту зависимость можно разделить на количественную и качественную. Например, алгоритм количество инструкций переменной N от конкретного его значения, т.е. f(N) от одной переменной.

(3(3 +1)) + (2(3 + 1)) + (1(3 + 1)) = 24 операции

Увеличим длину последовательности на 1 элемент, тогда число операций будет равно:

(4(3 +1)) + (3(3 + 1)) + (2(3 + 1)) + (1(3 +1)) = 40, таким образом, увеличивая число элементов на один, число операций увеличилось в несколько раз. Это показывает, что число операций выполнения время зависит от длины исходной последовательности количества элементов, задаваемые пользователем, т.е. в обоих примерах определяется значение числа N, которое объединяет эти примеры. Поэтому в общем случае говорят, что время выполнения алгоритма зависит от длины исходной последовательности. Вкладывая тот смысл, что он зависит как от количества элементов (массива), так и от количества переменных подобных 1 первому примера.

Говорят, что время выполнения программы имеет порядок T(n) от входных данных порядка (длины) n. Например, T(n) = C * n² определенно так, где С – некоторая константа, которая не зависит от входных данных, а определяет некоторое количество операторов, выполняемых в не зависимости от конкретного значения n. Например, быстродействие выполнения отдельной операции на данном компьютере.

C = (T(n))/n² , на данный коэффициент влияет ОС, архитектура ЭВМ, качество оператора и т.д. И физически представляет собой эффективность перехода от алгоритма его реализации (к фактическому).

Асимптотические отношения

Введем понятия функции роста числа трудоемкости выполнения алгоритма f(N), тогда: пусть все функции времени выполнения определенны на множестве не отрицательных целых чисел ≥ 0.

Время выполнения T(N) имеет порядок O(f(N)), если существует const C и такое Nо > 0 при любом N≥ nо величина C*f(N) ≥ T(n), т.е. для алгоритмов имеет порядок O(f(N)) вследствие того, что они имеют порядок или степень роста f(N).

«O(f(N))» запись представлена в «О» символике, в которой показываются характер изменения функции роста.

Пример: пусть мы смогли определить T(0) = 1, Т(1) = 4 величины или в общем случае T(n) = (n + 1)². Требуется найти асимптотическую оценку, т.е. некоторую функцию вида C(f).

T(n) = (n + 1)² = n² + 2n + 1

В качестве f(n) можно взять функцию вида f ’(N) = n³.

2n² ≥ n² + 2n + 1

C = 2 → nо = 3; C = 3 → nо = 2; C = 4 → nо = 1

В качестве асимптотической оценки, т.е. функции расположенной над T(n) можно взять функцию f(n) = n² однако тем самым мы ухудшим «мнение» эксперта о алгоритме (он работает быстрее). Если предположить что f(N) = n², то T(n) ≤ n² * C будет выполняться при С = 2, начиная с nо = 3, исключая коды длиной 1-2, более правильно положить С = 4, тогда nо = 1, тогда “O(f(n))” = n².

О – символика

Вообще в общем случае T(n) как функцию времени задать нельзя аналитически. Единственный выход – найти верхнюю и нижнюю асимптотическую оценку характера изменения T(n). Для чего вводиться функция Ω(f(n)) – омега, которая представляет нижнюю асимптотику. Можно подобрать такое значение функции роста для О и Ω, что они совпадут, тогда получим точную асимптотическую оценку функции T(n). Функция y(n) = Ө(g(n)), то говорят что g(n) является точной асимптотической оценкой для функции y(n). Если y(n) = Ө(g(n)) → g(n) = Ө(y(n)). Запись y(n) включает в себя 2 оценки верхнюю и нижнюю, т.е. C1f(n) ≤ Ө(n) ≤ C2f(n). Для нашего случая n², C1*n² ≤ n² + 2n + 1 ≤ C2 * n² на всем интервале n>no. Следовательно, f(n) = n² есть асимптотически точная оценка T(n) = Ө(n²). Говорят y(n) = Ω(g(n)), если найдется такая константа С > 0 и no, что О ≤ С*g(n) ≤ y(n) для всех n ≥ 0 теорема: для любых двух функций y(n) и g(n) свойства y(n) = Ө(g(n)) выполняется тогда и только тогда, когда следует, что y(n) = О(g(n)), g(n) = Ω (y(n)) следует, что любые две функции y(n) и g(n) по свойствам равносильны.

Обозначение - Ө, Ω, О: часто используются в формулах. Например, T(n + 1) = T(n) + Ө(n²) в рекуррентной формуле это обозначение означает, что время увеличивается при изменение длины аргумента пропорционально n², а в алгоритме этому члену выражения соответствует фрагмент асимптотическим выражениям, которые имеют n².

O и W – обозначения

y(n) = О(g(n)) означает, что отношение с ростом n является ограниченным, к тому же если

lim n→∞(y(n))/(g(n)) = 0, то записывается y(n) = О(g(n)), т.е. y(n) и g(n), если для всякого ε найдется такое no, О ≤ y(n) ≤ ε*g(n).

2n = O(n²), но 2n² ≠ О(n²)

lim n→∞(2n)/ n² = 0 lim n→∞(2n)/ n² = 2 ≠ 0

Найдется такое no, что O ≤ C*g(n) ≤ y(n), n²/2 = W(n) W/2 = W(n²) выполняются следующие свойства:

1. Транзитивный

y(n) = Ө(g(n)) и g(n) = Ө(h(n)), то y(n) = Ө(h(n))

O O O

Ω Ω Ω

O O O

W W W

2. Рефлексивность (отражение)

y(n) = Ө(y(n))

y(n) = O(y(n))

y(n) = Ω(y(n))

3. Симметричность

y(n) = (g(n)) ↔ g(n ) = Ө(y(n))

4. Обратимость(обращение)

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее