Вступ до алгоритміки та Java - Завантажити PDF безкоштовно
з алгоритміки та з ліцензії Java 1 Курс MASS, SEMS та ESD на Java та з алгоритміки [email protected] www.i3s.unice.fr/ verel Команда ScoBi - Університет Ніцци, Софія Антиполіс 1 лютого 2013 р.
Привіт! Викладач з вересня 2006 р. Дослідження: Розробка та вивчення алгоритмів оптимізації натхненних біологією. алгоритми: див. подальшу оптимізацію: знайти найкращі можливі рішення проблеми (транспорт, графік руху, дизайн, налагодження протезів, дизайн когнітивної теорії.) біоінспірація: витягнути активні принципи з теорії еволюції біологічної системи, видобутку мурах, пересування птахів . дизайн: створити та протестувати нові алгоритми вивчити: зрозуміти та передбачити, чому це працює, або краще, чому це не вдається! У лабораторії I3S (університет/cnrs) в Софії-Антиполіс, команда DOLPHIN, INRIA Lille Nord Europe.
Привіт! Викладання: ти, пр. науковий. інформація, L2; вступ Сист. комплекси, інформація L3; мережі, L3; сист. мистецтво. комплекси, інформація М1; моделювання, М2 пси. Контакт: з усіх питань, що стосуються викладання (виправлення, відсутність, запит на пояснення, додаткова інформація, вказівки.) [email protected] www.i3s.unice.fr/ бюро verel 426, Petit Valrose тел. 04.94.92.07.69.83
Привіт! Мотивація цього викладання: навчити основам вирішення певних проблем алгоритмічним методом викладати інформатику як мову, здатну виражати обробку інформації, навчати студентів, основним викладанням яких є не лише інформатика
Інформація про мету, завдання тощо. пор .: www.i3s.unice.fr/ verel
Курс курсу 1 Презентація досягнення в обробці: Після надсилання одного зі своїх досягнень електронною поштою (публікація на веб-сторінці) Коротка усна презентація в СМ (1 слайд) х студентів 2 Серце курсу 3 Усний та письмовий узагальнення: На кінець курсу усне резюме важливих моментів Написання цього резюме на етапі навчального форуму 3 студенти
Цілі сесії 1 1 Знання історичних алгоритмів 2 Знання визначення алгоритму 3 Знання середовища обробки 4 Редагування та коментування Java-коду з обробкою 5 Знання відображення тексту 6 Знання способу відображення простих графічних форм Основне питання дня: Що є- який алгоритм?
План 1 Приклади алгоритмів з історії та повсякденного життя 2 3 4 5
Алгоритм Евкліда (елементи, VII, -325/-265 до н. Е.) Завдання Знайти спільну одиницю виміру для двох довжин відрізків, тобто знайти gcd два цілих числа. Алгоритм GCD (a, b: ціле число): ціле число починається, якщо b = 0, тоді GCD = a, інакше c залишок від ділення a на b GCD = GCD (b, c) закінчується, якщо закінчується
Виконання алгоритму GCD (72, 34) Для a = 72 і b = 34 1. GCD (72, 34) 4. b 0 7. c = 4 8. GCD (34, 4) 4. b 0 7. c = 2 8. GCD (4, 2) 4. b 0 7. c = 0 8. GCD (2, 0) 4. b = 0 5. GCD = 2
Решето Ерастотена (3 до н. Е.) Завдання Визначте всі прості числа, менші від заданого числа. Алгоритм Ерастотена (N: ціле число): старт таблиці цілих чисел Запишіть у таблицю цілі числа від 2 до N. до тих пір, поки квадрат найменшого безсмугового і не позначеного числа менший за N, позначає найменше число в неперекресленому та не позначеному масиві з масиву всі кратні цього числа закінчуються простими числами, меншими N: числа, позначені або не перекреслені кінцем
Решето Ерастотена (III е. До н. Е.) Зауваження Можливість вдосконалення алгоритму: не пишіть кратні 2 і кратні 5. Перевага: швидше писати на початку, тому що менше місця використовується на аркуші Недолік: довше викреслювати: у вас є думати довше, щоб викреслити відповідні цифри! Сучасна версія алгоритму: Sieve d Atkin (1999) Посилання: A.O.L. Аткін, Д. Дж. Бернштейн, сита Prime з використанням двійкових квадратних форм, Math. Комп. 73 (1999), 1023-1030.
Задача на множення в Єгипті Обчислити добуток 2 цілих чисел Алгоритм Єгипетське множення (a, b: ціле число): почати ціле число Записати таблицю степенів 2 менше або дорівнює числу a Запишіть таблицю подвійних числа b до тих пір, поки число an не дорівнює нулю do Перевірте найбільшу потужність 2 a Відніміть цю кількість 2 від числа a end, доки додавання подвійного числа b відповідає степеням 2 перевірених раніше, отриманих a на b: сума, обчислена вище кінець
Фокус! Виберіть число від 1 до 15.
Фокус! 9 14 10 15 8 13 12 11
Фокус! 15 3 11 13 9 5 7 1
Фокус! 6 14 13 12 4 5 15 7
Фокус! 2 3 6 7 10 11 14 15
Фокус! Якого кольору ваш номер.
Шукати слово у словнику Ітеративно Алгоритм пошуку (ціль: слово): початок списку слів Прочитати перше слово у словнику, доки прочитане слово не є цільовим словом робити Прочитати кінець наступного слова як список слів: визначення слова lu end Знайдемо правильне слово, але алгоритм не дуже ефективний. в середньому N/2 слова, прочитані з N розмір словника Необхідно використовувати лексикографічний порядок словника та дихотомічний метод (розділяй і володарюй)
Пошук слова у словнику за роздвоєністю Алгоритм пошуку (ціль: слово): список слів починається перше перше слово словника останнє останнє слово словника Прочитайте середнє слово між першим та останнім, доки прочитане слово не є цільове слово робити, якщо цільове слово перед словом прочитане, то останнє прочитане слово, інакше перше слово прочитане закінчення, якщо Прочитати середнє слово між першим і останнім кінцем як список слів: визначення слова прочитаного кінця в середньому, журнал 2 (N) слова, прочитані з N розміром словника
Індекс маси тіла Проблема Наведіть ступінь повноти на основі індексу маси тіла Алгоритм маси тіла (t: дійсне число, M: дійсне число): початок i M/T 2, якщо i