ДС17о01-введение (Лекции Северов Часть 1)

Carnegie MellonВведениеАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция1,05 сентября,2017Лектор:ДмитрийСеверов,кафедраинформатики608КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=607712Алгоритмыиструктурыданных(1/2)¢¢ЧастьI Теоретическиеосновыинформатики§ Формализацияпонятияалгоритм§ МашинаТьюринга§ Алгорифмы МарковаЧастьII Структурыданных§ ОдиалектахСи§ Составныетипыданных§ Абстрактныетипыданных3Алгоритмыиструктурыданных(2/2)¢¢ЧастьIII Основытеорииалгоритмов§ Анализэффективностиалгоритмов§ РекурсияЧастьIV Основные(базовые)алгоритмы§ Задачисортировки§ Задачипоиска§ Поискнаграфах4Предусловие– умения…алгоритмическимыслитьМожнопроверитьспомощьюhttp://lightbot.comформальноизлагатьрешениезадачиМожнопроверитьспомощьюhttps://drakon-editor.com5Извикипедии (1/2)¢Программи́рование§ процесссозданиякомпьютерныхпрограмм¢Компью́тернаяпрогра́мма1.

комбинациякомпьютерныхинструкцийиданных,позволяющаяаппаратномуобеспечениювычислительнойсистемывыполнятьвычисленияилифункцииуправления(стандартISO/IEC/IEEE24765:2010)[1];2. синтаксическаяединица,котораясоответствуетправиламопределённогоязыкапрограммирования,состоящаяизопределенийиоператоровилиинструкций,необходимыхдляопределённойфункции,задачиилирешенияпроблемы(стандартISO/IEC2382-1:1993)[2].6Извикипедии (2/2)¢Програ́мма (отгреч.προ —пред,греч.γράμμα —запись)термин,впереводеозначающий«предписание»,тоестьпредварительноеописаниепредстоящихсобытийилидействий.Данноепонятиенепосредственносвязаноспонятиемалгоритм.…¢Алгори́тмнаборинструкций,описывающихпорядокдействийисполнителядлядостижениянекоторогорезультата.<…>Независимыеинструкциимогутвыполнятьсявпроизвольномпорядке,параллельно,еслиэтопозволяютиспользуемыеисполнители¢Инструќ цияилиопера́тор(англ.

statement)наименьшаяавтономнаячастьязыкапрограммирования;командаилинаборкоманд.Программаобычнопредставляетсобойпоследовательностьинструкций.7ПонятияпрограммированияПрограммаопределённый наборпредписанийпрограммистДанныенеопределённый наборинформацииПрограммаПроцессожидаемый набор событийДанныеПрограммируемаясистема(исполнитель)ПроцессРесурсыВремя работы¢§§Ресурсы¢¢ПрограммистаСистемыЭнергияПространство8ИзопределенийГОСТ33707 (1/3)¢Программа§ Данные,предназначенныедляуправленияконкретнымикомпонентамисистемыобработкиинформациивцеляхреализацииопределенногоалгоритма.¢Языкпрограммирования§ Искусственныйязыкдляизложениятекстовпрограмм9ИзопределенийГОСТ33707 (2/3)¢Алгоритм§ 2015:Конечноеупорядоченноемножествоточноопределенныхправилдлярешенияконкретнойзадачи§ 1984:Конечныйнаборпредписаний,определяющийрешениезадачипосредствомконечногоколичестваопераций¢Алгоритмическийязык§ Искусственныйязык,предназначенныйдлявыраженияалгоритмов10ИзопределенийГОСТ33707 (3/3)¢Языкспецификаций§ Языкприкладногохарактера,который,1.2.3.4.5.частоявляясьориентированнымнакомпьютерысинтезоместественногоязыкаиискусственногоязыка,используютсядлявыражениятребованийксистемеиликомпоненте,дляописанияихконструкции,аиногдаипротоколовпроверки,дляпроектирования,исследованияидокументированияуказанныххарактеристик.11[Около]компьютерныеявления¢¢¢Модель– упрощённоепредставлениезаконовповедениячастейиотношенийсистемыЯзыкмодели- знаковаяподсистемафиксации,переработкиипередачиинформацииМашина– модельныйисполнитель,которомунаправленыпредписаниянаязыкемоделиРынки¢ Потребители¢ Задачи¢Алгоритмы¢ Программы¢ Система/Аппаратура¢ Цифровыесхемы¢ Аналоговыесхемы¢Физическиеявленияв[не]линейныхструктурах¢12Некоторые[около]компьютерныеязыки¢Задачи¢Языкиспецификаций¢Языкипроектирования¢Алгоритмы¢Алгоритмическиеязыки¢Программы¢Языкипрограммирования¢Архитектура«системы»¢Языкиобращенийк«системе»¢Архитектурааппаратуры¢Языкикомандаппаратуры¢Блокиархитектуры¢Языкимикрокоманд¢Цифровыесхемы¢Языкицифровыхсхем¢Аналоговыесхемы¢Языкианалоговыхсхем¢Языкифизическихмоделей¢Физическиеявленияв[не]линейныхструктурах13АлгоритминтуитивноПоискНОД(a,b),гдеa,b >0,a<b§ Перебор:1– подходит,2- ?,3- ,…а-?§ АлгоритмЭвклида1.

Разделитьпервоенавтороеиполучитьостаток2. Еслиостатокравеннулю,товторое–результат3. Иначе:заменитьпервоенавторое,второе– наостатокиперейтикшагу114СвойстваалгоритмаДискретность данныхидействийнаднимиПонятность: доступностьиоднозначностьправилКонечность: решение задачи законечноечислошаговОпределённость: воспроизводимость результатаМассовость:применимостькразличнымданным15Алгоритмформально:отступлениекфункцииИсходныеданныеРезультаты16Алгоритмформально:отступлениекмножествам(1/2)1.

Элементмножестваа2. МножествоА3. Элементпринадлежитмножеству аÎ А4. НепринадлежитаÏА5. А={a,b,c}6. Æ7. Подмножество AÌBÛ " aÎ A:aÎ B8. A=B Û AÌ Bи BÌ A17Алгоритмформально:отступлениекмножествам(1/2)9. ОбъединениеАÈВ10.ПересечениеAÇB={aÎA:aÎB}11.РазностьA\ B={aÎA:aÏB}12.Декартово(прямое)произведение Aх BА={0,1},B={a,b,c}, AxB={0a,0b,0c,1a,1b,1c}A1 xA2 xA3 x…xAnA0=Æ,A1=A,A2=A x A,An =AxAxAx…xAn18Алгоритмформально:функцияформально¢МножествоFестьфункцияизмножестваАвB тогдаитолькотогда, когдаверноследующее.1.

FÍ AxB,2. если…1. aÎA,2. b,cÎB3. abÎF,4. acÎF,… тоb=c.10,1515,256,914,2119Алгоритмформально:итог§A={a1,a2,…,ap} - алфавит§A* = A0 È A1 È A2 È …È An –множествовсехслов,состоящихнеболеечемизn символов.§F:A*® A*20АланТьюрингЭмиль ПостНорбертВинерАлонзоЧёрчАндрейМарков21ПрограммаРеализацияалгоритманаязыкепрограммирования,определяющем…§ Действия: операциииоператоры§ Данные: типыиэкземпляры§ Организация: конструкции сложных данныхидействий§ Окружение: взаимодействие со средой22Масштабысобытийвашейпрограммы¢ВашисполнительЯдропроцессораПамятьУBBУBBУBBУBBКрупнее:§ Средаразработк觧§§СоединительРедактированиеТрансляцияСвязывание…§ СредаисполненияЗагрузка§Выделениересурсов§Нормированиеработыиреагированиеназапросы§Освобождениересурсов§…Мельче– зарамкамисеместра§¢Вашпроцесс§§¢ВыполнениеоперацийИзменениесостоянияДругиепроцессы23СозданиепрограммыРедактирование⇓ ТекстпрограммыТрансляция⇓ ОбъектныйкодКомпоновка⇓ ЗагрузочныйкодЗагрузка⇓ ИсполняемыйкодВыполнение, отладка⇓ Результат24СозданиепрограммывместеРедактирование⇓ Текстпрограммы⇐ ВашиизменениявручнуюТрансляция⇓ Объектныйкод⇐ БиблиотечныйисходныйтекстКомпоновка⇓ Загрузочныйкод⇐ БиблиотечныймашинныйкодЗагрузка⇓ Исполняемыйкод⇐ РешениясредыисполненияВыполнение, отладка⇓ Результат⇐ Внешниеданные,коды,события25СозданиепрограммывокруженииРедактированиеG Предписанияредактору⇓ Текстпрограммы⇐ ВашиизменениявручнуюТрансляцияE Предписаниятрансляции⇓ Объектныйкод⇐ БиблиотечныйисходныйтекстКомпоновкаE Предписаниякомпоновки⇓ Загрузочныйкод⇐ БиблиотечныймашинныйкодЗагрузкаE Предписаниязагрузки⇓ Исполняемыйкод⇐ РешениясредыисполненияВыполнение, отладка E Предписанияисполнения⇓ Результат⇐ Внешниеданные,коды,события26Carnegie Mellon(Само)обман¢Чтоесть(само)обман?§§§§§¢Братьчужойкод:копируя,перенабирая,подглядывая,принимаяфайлыПересказывать:устноеописаниекодаоднимчеловекомдругомуНатаскивание:помощьдругувпострочномнаписаниизаданийПоискрешениявсетиКопированиекодапредыдущихкусовиэкзаменовЧтоНЕесть(само)обман?§ Объяснятькакиспользоватьинструментыилисистемы§ Помогатьдругимввопросахконструкцииверхнегоуровня27.