Студопедия — ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
Студопедия Главная Случайная страница Обратная связь

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

ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ






 

4.1. Вибір варіанта індивідуального завдання

Введемо позначення: DN – день народження

MN – місяць народження

А1 – ASCII-код першої літери прізвища – велика латинська літера

№ варіанта = (DN + MN + А1) % 25+ 1

4.2. Варіанти завдань

Загальна частина:

Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування.

 

Провести дослідження побудованого методу за схемою:

1) Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний).

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

3) Дослідити метод cортування на стійкість.

4) Дослідити метод cортування на економність використання пам’яті.

5) Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).

6) Дослідити ефективність методу. Для цього програмно визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому () і в найгіршому () випадках. Середні значення кількості порівнянь () і кількості перестановок () визначити, як середнє арифметичне для кожної величини від великої кількості спроб сортування випадкових послідовностей. Побудувати графіки залежностей , , , від кількості елементів n, де n змінюється від 1 до 100 000.

7) Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості.

Індивідуальні завдання:

1. Сортування методом простої вставки.

2. Сортування просіюванням з барьером.

3. Сортування бінарною вставкою.

4. Сортування методом простого вибору.

5. Сортування методом простого обміну.

6. Шейкер-сортування.

7. Сортування Шелла, що використовує кроки 9, 5, 3 і 1

8. Сортування Шелла, що обчислює послідовність приростів по першій формулі.

9. Сортування Шелла, що обчислює послідовність приростів по другій формулі.

10. Пірамідальне сортування.

11. Швидке сортування.

12. Сортування злиттям.

13. Порозрядне сортування.

14. Бітове сортування.

15. Сортування методом підрахунку порівнянь [1, 94-97 c.].

16. Сортування методом підрахунку розпреділення [1, 97-98 c.].

17. Сортування з обчисленням адреси [1, 118-121 c.], [2, 469-472 c.].

18. Обмінне сортування зі злиттям [1, 131-133 c.].

19. Обмінне порозрядне сортування [1, 144-150 c.].

20. Сортування методом двохшляхового злиття [1, 181-182 c.].

21. Сортування методом природного двохшляхового злиття [1, 183-185 c.].

22. Сортування методом простого двохшляхового злиття [1, 186-187 c.].

23. Сортування методом злиття списків [1, 187-189 c.].

24. Порозрядне сортування списку [1, 195-200 с.]

25. Сортування за допомогою вставок і злиття [1, 208-210 c.].

 

5. ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТУ

I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта.

II. В звіті мають бути відображені наступні пункти:

1. Мета роботи.

2. Постановка задачі.

2.1. Загальна частина

2.2. Індивідуальне завдання

3. Опис алгоритму.

4. Дослідження методу.

4.1. Обґрунтування вибору структури даних.

4.2. Схема алгоритму cортування на прикладі послідовності чисел.

4.3. Дослідження методу cортування на стійкість.

4.4. Дослідження методу cортування на економність використання пам’яті.

4.5. Дослідження методу на специфіку вхідної послідовності.

4.6. Дослідження ефективності методу.

1) Програмні дослідження.

а) Кількість порівнянь в найкращому, в найгіршому та в середньому випадках.

б) Кількість перестановок в найкращому, в найгіршому та в середньому випадках.

2) Чисельні дослідження.

а) Визначення класу (підкласу) алгоритму по його трудомісткості.

б) Обчислення функції трудомісткості алгоритму.

3) Асимптотичні дослідження.

а) Знаходження часової складності алгоритму (за нотацією Ландау).

б) Визначення назви асимптотичного класу ефективності алгоритму.

5. Результати виконання програми.

Висновки.

Додатки (тексти програм з коментарями).

6. КОНТРОЛЬНІ ЗАВДАННЯ

1. Промоделюйте вручну, показуючи всі проміжні результати, роботу алгоритму сортування методом простої вставки наступної послідовності: 55, 3, 20, 88, 1, 66, 9.  
2. Промоделювати вручну, показуючи всі проміжні кроки, роботу алгоритму швидкого сортування наступної послідовності: 15, 23, 47, 54, 10, 5, 19.  
3. Дослідити на стійкість метод cортування простим вибором, програмна реалізація якого має такий вигляд:   procedure SelectionSort(var a:VectType); var i,j,k: integer; min: KeyType; Begin for i:=1 to n-1 do begin k:=i; min:=a[i]; for j:=i+1 to n do if a[j] < = min then begin k:=j; min:=a[k]; end; a[k]:=a[i]; a[i]:=min; end; End;

 

СПИСОК ЛІТЕРАТУРИ

1. Кнут Д. Искусство програмирования, том 3. Сортировка и поиск. – М.: Изд.дом ”Вильямс”, 2001. – 832 с.

2. Вирт Н. Алгоритмы + структуры данных = програмы. –М.:Мир,1985 - 406 с.

3. Ленгсам Й., Огенстайн М., Тененбаум А. Структура данных для персональных ЭВМ. –М.:Мир, 1989 - 560 с.

4. Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі. –К:Либідь, 1993 - 224 с.

5. Семакин И.Г., Шестаков А.П. Лекции по программированию. Пермь: изд-во ПГУ, 1998.

 







Дата добавления: 2015-10-02; просмотров: 511. Нарушение авторских прав; Мы поможем в написании вашей работы!



Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

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

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

Конституционно-правовые нормы, их особенности и виды Характеристика отрасли права немыслима без уяснения особенностей составляющих ее норм...

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

Меры безопасности при обращении с оружием и боеприпасами 64. Получение (сдача) оружия и боеприпасов для проведения стрельб осуществляется в установленном порядке[1]. 65. Безопасность при проведении стрельб обеспечивается...

Весы настольные циферблатные Весы настольные циферблатные РН-10Ц13 (рис.3.1) выпускаются с наибольшими пределами взвешивания 2...

Хронометражно-табличная методика определения суточного расхода энергии студента Цель: познакомиться с хронометражно-табличным методом опреде­ления суточного расхода энергии...

Studopedia.info - Студопедия - 2014-2024 год . (0.012 сек.) русская версия | украинская версия