44. Алгоритмы сортировки данных. Сортировка подсчетом.

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза.

procedure CountiongSort( var ar: array of integer; min, max: integer);

var

counter: array [0..100000] of integer; i, j, index: Integer;

begin

// заполняем массив нулями

for i:=0 to high(counter) do tmpA[i]:=0; а

for i:=min to max do begin

counter[ar[i]]:=counter[ar[i]]+1;

end;

// устанавливаем значение в правильную позицию

index:=min;

for i:=min to high(counter)-1 do begin

for j:=0 to counter[i]-1 do begin

ar[index]:=i

index:=index+1;

end;

end;

end;

45. Моделирование алгоритмов программ с помощью блок-схем.

46. История развития математической логики.

Ло́гика (др.-греч. λογική — «наука о рассуждении», «искусство рассуждения» от λόγος — «речь», «рассуждение», «мысль») — наука о формах, методах и законах интеллектуальной познавательной деятельности, формализуемых с помощью логического языка. Поскольку это знание получено разумом, логика также определяется как наука о правильном мышлении. Поскольку мышление оформляется в языке в виде рассуждения, частным случаем которого являются доказательство и опровержение, логика иногда определяется как наука о способах рассуждения или наука о способах доказательств и опровержений. Логика как наука изучает способы достижения истины в процессе познания опосредованным путём, не из чувственного опыта, а из знаний, полученных ранее, поэтому её также можно определить как науку о способах получения выводного знания.

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

Одна из главных задач логики — определить, как прийти к выводу из предпосылок (правильное рассуждение) и получить истинное знание о предмете размышления, чтобы глубже разобраться в нюансах изучаемого предмета мысли и его соотношениях с другими аспектами рассматриваемого явления.

Логика служит одним из инструментов почти любой науки.

Хотя многие культуры выработали сложные системы рассуждения, логика как эксплицитный анализ методов рассуждения получила основательное развитие изначально только в трёх традициях: в китайской, индийской и греческой. Хотя точные даты не слишком достоверны (особенно в случае Индии), скорее всего, логика возникла во всех трёх культурах в IV веке до н. э.. Современная логика, разработанная формально изощрённо, происходит в конечном счёте из греческой традиции (аристотелевской логики), которая, однако, была воспринята не напрямую, а при посредничестве и комментаторской деятельности арабо-мусульманских философов и средневековых европейских логиков. Можно выделить следующие исторические и региональные формы логики (приведены также их имена, исторически существовавшие и принятые в литературе по истории формальной логики):

• Древнекитайская логика:

• Индийская логика

• Европейская и ближневосточная логика: традиционная логика (в широком смысле)

  • Античная и раннесредневековая логика: диалектика

  • Средневековая логика

    • Арабская и еврейская средневековая логика

    • Восточнохристианская (византийская, грузинская, армянская) средневековая логика

    • Западноевропейская средневековая логика: схоластическая логика, диалектика

  • Логика европейского Возрождения; диалектика

  • Логика Нового времени: традиционная логика (в узком смысле), формальная логика

• Современная логика (общемировая, со второй половины XIX века): математическая логика, символическая логика, логистика (последнее — как правило, в западной литературе).

Логика в своём развитии прошла три порога:

• порог формализации рассуждений (во всех трёх традициях)

• введение условных (символических, буквенных и числовых) обозначений (только европейская традиционная логика)

• научная революция, с которой началась современная логика, — математизация (внесение в логику математических методов).