Сұрыптау және іздеу алгоритмдері

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 2

Сұрыптау және іздеу алгоритмдері

Сызықтық іздеу. Екілік іздеу Көпіршікті сұрыптау. Кірістіру бойынша сұрыптау. Таңдау бойынша сұрыптау. Есеп сұрыптау. Түбір сұрыптау. Біріктіру сұрыптау алгоритмі. Жылдам сұрыптау. Пирамидалық сұрыптау.

A

В

Алгоритмді бағалау

Тұрақты күрделілік. Сызықтық күрделілік. Логарифмдік күрделілік. Сызықтық логарифмдік күрделілік. Квадраттық күрделілік. Текше күрделілігі. Экспоненциалды күрделілік.

Факторлық күрделілігі

А

В

С

Сызықтық мәліметтер құрылымы

Массивтер, стектер, кезектер, тізімдер, байланысқан және қосарланған тізімдер

В

C

Хэш кестелері және хэш функциялары

Хэш кестесінің өнімділігі. Хэш функцияларын жобалау. Соқтығуды шешудің схемалары: бір тізбекті, ашық адресация, сызықты зондтау, квадраттық зондтау, қос хэш

B

С

Ағаш және екілік үйінділер.

Аңғал екілік ағаш. Теңдестірілген ағаштар. Өрнек ағашы. BST (екілік іздеу ағашы). AVL ағаштары. Қызыл-қара ағаш. Екілік үйінді.

B

С

Графтар және графтар алгоритмдер

Графтар туралы түсінік. Графтармен жұмыс. Терең ізденіс (BFS). Кең ізденіс (DFS). Беллман-Форд алгоритмі. Дихстстраның алгоритмі. Флойдтың алгоритмі. Примнің алгоритмі. Крускал алгоритмі.

B

С

Бір тест нұсқасы үшін тапсырмалардың саны

4. Жұмыс мазмұнын сипаттау:

«Алгоритмдер және деректер құрылымы» пәні бойынша емтиханға келесі тақырыптар бойынша 30 сұрақ кіреді:

Функциялар (C бағдарлама тiлi); Циклдар; С бағдарлама тiлi типтері; Рәсімдер; Деректер форматтары; Тіркеушілер; Операндалар; Бірыңғай операторлар; Екілік операторлар; Ауысым операторлары; Жадты басқару; Көрсеткіштер; С құрылымдары; Стек; Кезек; Басымдық кезегі; Байланыстырылған тізімдер; Қосарланған тізімдер; Тұрақты тіркестер; Токендер; Үлкен O белгілеуі; Алгоритмнің күрделілігін бағалау; Бірөлшемді массивтер; Көпөлшемді массивтер; Сұрыптау алгоритмдері: блокты сұрыптау, сұрыптауды санау, біртекті сұрыптау алгоритмі; Екілік үйінді; Хэш кестелері; Хэш функциялары; Хэш кестесінің өнімділігі; Хэш функцияларды жобалау; Соқтығуды шешудің схемалары: бөлек тізбек, ашық адресация, сызықты зондтау, квадраттық зондтау, қос хэш; Графикалық алгоритмдер; Терең ізденіс (BFS); Кең ізденіс (DFS); Беллман-Форд алгоритмі; Дихстстраның алгоритмі; Флойдтың алгоритмі; Примнің алгоритмі; Крускал алгоритмі; Қапшық проблемасы (динамикалық бағдарламалау); Мемлекеттік машиналар; ағаштар; Аңғал екілік ағаш; Теңдестірілген ағаштар; Өрнек ағашы; BST (екілік іздеу ағашы); AVL ағаштары; Қызыл-қара ағаш.

5. Тапсырманы орындаудың орташа уақы:

Бір тапсырманың ұзақтығы - 2 минут.

Жалпы сынақ уақыты - 60 минут.

6. Тесттің бір нұсқасындағы тапсырмалардың саны:

Тесттің бір нұсқасында - 30 тапсырма.

Тест тапсырмаларын күрделілік деңгейі бойынша бөлу:

- жеңіл (A) - 9 тапсырма (30%);

- орташа (B) - 12 тапсырма(40%);

- күрделі (C) - 9 орташа (30%).

7. Тапсырма формасы:

Тест тапсырмалары жабық формада ұсынылады, ұсынылған бес нұсқадан бір дұрыс жауапты көрсетеді.

8. Тапсырманы бағалау:

Дұрыс жауапты таңдаған кезде, өтініш берушіге 1 (бір) балл, басқа жағдайларда - 0 (нөл) балл беріледі..

9. Ұсынылған әдебиеттер тізімі:

1. Дэйтл Х.М., Как программировать на C++,  Prentice Hall, , 10 издание. 2017.-1568 стр.

2. Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы = The Art of Computer Programming. Volume 1. Fundamental Algorithms / под ред. С. Г. Тригуб (гл. 1), Ю. Г. Гордиенко (гл. 2) и И. В. Красикова (разд. 2.5 и 2.6). — 3. — Москва: Вильямс, 2002. — Т. 1. — 720 с. — ISBN 5-8459-0080-8.

3. Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы = The Art of Computer Programming. Volume 2. Seminumerical Algorithms / под ред. Л. Ф. Козаченко (гл. 3, разд. 4.6.4 и 4.7), В. Т. Тертышного (гл. 4) и И. В. Красикова (разд. 4.6). — 3. — Москва: Вильямс, 2001. — Т. 2. — 832 с. — ISBN 5-8459-0081-6.

4. Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.

5.  Брюс Эккель, Thinking in C++, Volume 1, 2nd Edition, 2015.- 840 p.

6. Пащенко Г.Н. Tutorial on course “Algorithms, data structures and programming”, -Almaty, 2017.-202 p.

7. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман, Структуры данных и алгоритмы, Вильямс, 2016

8. Объектно-ориентированное программирование в С++, Лафоре Роберт – Питер 2018. – 928 стр.

9.  Структуры данных и алгоритмы в Java, Лафоре Роберт – Питер 2018, 704 стр.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману